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]<<" ";
}
};