DFS.rar_dfs

/************************************************** h ***************************************************/ #include <iostream> using namespace std; #include<time.h> #include<math.h> /************************************************** struct ***************************************************/ struct Node { char color;//g-gray b-black w-white long pi;//parent long d;//gray time long f;//black time }; long timee=0; long *Degree; Node *NodeArray; long **Adj; long NumberOfNode=0; /************************************************** sub function ***************************************************/ void CreateAdjList() { long i,j,tmp; int flag=1; long DegreeUpperBound;//the biggest number of the neighbour if(NumberOfNode<=20000) DegreeUpperBound=static_cast<long>(sqrt((long double)NumberOfNode)); else DegreeUpperBound=static_cast<long>(log10((long double)NumberOfNode)); for(i=1;i<=NumberOfNode;i++) { Degree[i]=rand()%DegreeUpperBound+1; Adj[i]=new long[Degree[i]+1]; for(j=1;j<=Degree[i];j++) { Adj[i][j]=rand()%NumberOfNode+1; while(Adj[i][j]==i) { Adj[i][j]=rand()%NumberOfNode+1; } while(flag) { flag=0; for(tmp=1;tmp<j;tmp++) { if(Adj[i][j]==Adj[i][tmp]||Adj[i][j]==i) { Adj[i][j]++; if(Adj[i][j]==NumberOfNode+1) Adj[i][j]=1; flag=1; } } } flag=1; } }//each node have some neighbours now for(i=1;i<=NumberOfNode;i++) { NodeArray[i].color='w'; NodeArray[i].pi=0; NodeArray[i].d=0; NodeArray[i].f=0; } } void PrintGraph() { long i,j; cout<<"The adjacency-list representation of a directed graph:\n\n"; for(i=1;i<=NumberOfNode;i++) { cout<<i; for(j=1;j<=Degree[i];j++) { cout<<" -> "<<Adj[i][j]; } cout<<"\n"; } } void DFSVISIT(long u) { long i; timee++; NodeArray[u].d=timee; NodeArray[u].color='g'; for(i=1;i<=Degree[u];i++) { if(NodeArray[Adj[u][i]].color=='w') { NodeArray[Adj[u][i]].pi=u; DFSVISIT(Adj[u][i]); } } NodeArray[u].color='b'; timee++; NodeArray[u].f=timee; } void DFS() { long i; for(i=1;i<=NumberOfNode;i++) { if(NodeArray[i].color=='w') { DFSVISIT(i); } } } void PrintEdge() { long i; cout<<"\n\n\n\nThe edges of the tree:\n\n"; for(i=1;i<=NumberOfNode;i++) { if(NodeArray[i].pi!=0) { cout<<"("<<NodeArray[i].pi<<","<<i<<")"<<"\n"; } } } void PrintTime() { long i; cout<<"\n\n\n\nTime of the nodes:\n\n"; for(i=1;i<=NumberOfNode;i++) { cout<<"d["<<i<<"]="<<NodeArray[i].d<<" "; cout<<"f["<<i<<"]="<<NodeArray[i].f<<"\n"; } } /************************************************** main ***************************************************/ void main() { srand(time(0)); while(NumberOfNode<10) { cout<<"input the number of the nodes(at least 10):"; cin>>NumberOfNode; } Degree=new long[NumberOfNode+1]; NodeArray=new Node[NumberOfNode+1];//mark array Adj=new long*[NumberOfNode+1];//array of array CreateAdjList(); PrintGraph(); DFS(); PrintEdge(); PrintTime(); delete[]Degree; delete[]NodeArray; delete[]Adj; }