Need help implementing graphs!

I came up with the following code. Here, I assume that I already know the number of vertices on the graph and proceed accordingly with the standard Adjacency list representation. However, some questions that I “feel” can be solved using Graph Algorithms require me to construct the graph by knowing the number of edges at first. Now, I am having problems understanding how to implement this.

I can assume that there are a very large number of vertices (from the problem constraints) but that is not the way it should be implemented I guess.

Also, can someone guide me to an easy resource to learn the C++ STL? My code is extremely complicated right now.

class graph
{

private:
    bool *color;
    int vertices;
    void addVertex(int u, int v)
    {
        node *temp=&ptr[u];
        while(temp->next!=NULL)
            temp=temp->next;
        temp->next=new node(v);
    }
public:

    int V()
    {
        return vertices;
    }
    class node
    {
    public:
        node(int name)
        {
            label=name;
            next=NULL;
        };

        node(){next=NULL;};

        int label;

        node *next;
    };

    class edge
    {
    public:
        edge(int u, int v)
        {
            U=u;
            V=v;
            next=NULL;
        }

        int U,V;

        edge *next;
    };

    node *ptr;
    bool *marked;
    edge *edgeList;
    edge *edgeTemp;
    graph(int v)
    {
        ptr=new node[v+1];
        vertices=v;
        for(int i=1;i<=v;++i)
            ptr[i].label=i;

        marked=new bool[V()+1];

        for(int i=1;i<=V();++i)
            marked[i]=false;

        edgeList=NULL;
    }

    void addEdge(int u, int v)
    {
        addVertex(u,v);
        //addVertex(v,u);       For undirected graphs only

        if(!edgeList)
        {
            edgeList=new edge(u,v);
            edgeTemp=edgeList;
        }

        else
        {
            edgeTemp->next=new edge(u,v);
            edgeTemp=edgeTemp->next;
        }

    }

    void printEdges()
    {
        edge *temp=edgeList;


        while(temp)
        {
            cout<<temp->U<<"-"<<temp->V<<endl;
            temp=temp->next;
        }
    }


    int *id=new int[V()+1];
    int *arrival=new int[V()+1];
    int *departure=new int[V()+1];
    int time=1;
    int count=1;

    void dfs(int vertex)
    {
        marked[vertex]=1;
        id[vertex]=count;

        arrival[vertex]=time++;

        node *temp=&ptr[vertex];
        int v=vertex;

        while(temp->next)
        {
            temp=temp->next;
            vertex=temp->label;
            if(!marked[vertex])
                dfs(vertex);
        }

        departure[v]=time++;    //cannot use departure[vertex] as value of 'vertex' has changed
    }

    void connectedComponent()
    {


        for(int v=1;v<=V();v++)
        {
            if(!marked[v])
            {
                dfs(v);
                count++;
            }
        }

        for(int v=1;v<=V();v++)
            cout<<id[v]<<" ";
    }

    void topologicalSort()
    {
        int *topSortArray=new int[V()];

        for(int i=1;i<=V();++i)
            topSortArray[i]=departure[i];

        for(int i=1;i<=V();++i)
            cout<<topSortArray[i]<<" ";

        heapsort(topSortArray,V()+1);

        cout<<endl<<V()<<endl;

        int j=V();
        int i=1;
        while(i<j)
            swap(topSortArray[i++],topSortArray[j--]);

        for(int i=1;i<=V();++i)
        {
            for(int j=1;j<=V();++j)
            {
                if(departure[j]==topSortArray[i])
                {
                    topSortArray[i]=j;
                }
            }
        }
        cout<<endl;
        for(int i=1;i<=V();++i)
            cout<<topSortArray[i]<<" ";
    }

};
1 Like

first lets try to remove unnecessary things.

->‘label’ in node is not needed.
->no need to have ‘edgelist’ as you can transverse ptr[] to print all the edges.

read about stl container ‘vector’ here http://www.cplusplus.com/reference/vector/vector/

now we can use vector to maintain edges in the graph.
let edges[v] be an array of vectors and ‘v’ be no of vertices.
if you want to add an edge between ‘a’ and ‘b’ u can do it this way

void add_edge(int a,int b){
edge[a].push_back(b)
edge[b].push_back(a);
}

void dfs(int vertex)
{
int i,j;
marked[vertex]=1;
arrival[vertex]=time++;
for(i=0; i<edge[vertex].size() ; i++) {
j=edge[vertex][i];
if(!marked[j])
dfs(j);
}

    departure[vertex]=time++;    
}

->i could not understand what u meant by “some questions that I feel can be solved using Graph Algorithms require me to construct the graph by knowing the number of edges at first”.
you will always be given no of vertices in the graph first .if you can give me an example about your above statement that would be easy to help you.

->if u understood how to implement graph algorithms then try to solve this question

2 Likes

#include
#include

using namespace std;

class Graph
{

public:

	vector< vector<int> > edge;
	bool *marked;

	Graph(int V)
	{
		edge.resize(V+1);
		marked=new bool[V+1];
	}

	void add_Edge(int a, int b)
	{
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	void dfs(int vertex)
	{
		marked[vertex]=1;

		cout<<vertex<<" ";

		for(int i=0;i<edge[vertex].size();++i)
		{
			int j=edge[vertex][i];

			if(!marked[j])
				dfs(j);
		}
	}

};

The above code works I think! Thanks a lot @abhinav1234 .

I had come across a question having no. of edges as input on the Coursera course “Design and Analysis of Algorithms”. It was the third question of the programming assignments on min cuts. I encountered another such question on the website Codinggame. But, those were a couple of months ago and I was rather new to Algorithms. So, I guess I messed up my thinking.

I shall try to solve the question mentioned ASAP.