Discovery Time and Finishing Time Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
//dfs using adjacency list in directed graph #include<iostream> using namespace std; int WHITE=1,GREY=2,BLACK=3,INF=310000,NIL=-1; int num_v,num_e,time=0; int adj[20][20],color[20],p[20],d[20],f[20]; void DFS_visit(int); void initialization() { int k,j; for(k=0; k<20; k++) { for(j=0; j<20; j++) { adj[k][j]=0; } } } void build_adj_matrix() { int i,a,b; cout<<"Enter number of vertices: "<<endl; cin>>num_v; cout<<"Enter number of edges: "<<endl; cin>>num_e; cout<<"Enter edges: "<<endl; for(i=1; i<=num_e; i++) { cin>>a>>b; adj[a][b]=1; } } void dfs() { int i,u; for(i=1; i<=num_v; i++) { color[i]=WHITE; p[i]=NIL; } for(u=1; u<=num_v; u++) { if(color[u]==WHITE) { DFS_visit(u); } } } void DFS_visit(int u) { int i,v; color[u]=GREY; time=time+1; d[u]=time; for(v=1; v<=num_v; v++) { if(adj[u][v]==1) { if(color[v]==WHITE) { p[v]=u; DFS_visit(v); } } } color[u]=BLACK; time=time+1; f[u]=time; } void distance_output() { int i; cout<<"Discovery time and finish time:\n"; for(i=1; i<=num_v; i++) { cout<<"Node "<<i<<" is "<<d[i]<<"/"<<f[i]<<" \n"; } } int main() { initialization(); build_adj_matrix(); dfs(); distance_output(); return 0; } |
input/output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Enter number of vertices: 4 Enter number of edges: 4 Enter edges: 2 3 2 1 1 4 3 4 Discovery time and finish time: Node 1 is 1/4 Node 2 is 5/8 Node 3 is 6/7 Node 4 is 2/3 |
pseudo:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void DFS_visit(int u){ int i,v; colour[u]=GREY; time=time+1; d[u]=time; for(v=1;v<=num_v;v++) { if(adj[u][v]==1){ if(color[v]==WHITE){ p[v]=u; DFS_visit(v); } } } color[u]=BLACK; time=time+1; f[u]=time; } |
Pseudocode from shafayet vai’s blog:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
procedure DFS(G, source): U ← source time ← time+1 d[u] ← time color[u] ← GREY for all edges from u to v in G.adjacentEdges(v) do if color[v] = WHITE DFS(G,v) end if end for color[u] ← BLACK time ← time+1 f[u] ← time return |
Reference:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
http://www.dotnetlovers.com/Article/182/implementation-of-depth-first-searchdfs
Another code to find the order of the node:
References:
One of my classmates blog link: http://programminghelpbd.blogspot.com/2014/06/breadth-first-search-dfs-in-java.html
and this ppt : https://drive.google.com/file/d/0B0sCkwd_qKgJZEJzS1pWeXNmNUE/edit
CLRS website: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
Shafayet Ashraf: http://www.shafaetsplanet.com/planetcoding/?p=973
saurabhschool youtube link : https://www.youtube.com/watch?v=gCNsAKkUHPM
Youtube video of Mifta Sintaha:
and here is also a good implementation:
http://electrofriends.com/source-codes/software-programs/cpp-programs/cpp-data-structure/c-programs-for-the-implementation-of-depth-first-searchdfs-for-a-given-graph/comment-page-1/#comments
Java array basics: http://www.tutorialspoint.com/java/java_arrays.htm
Another code to find the order of vertices:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<conio.h> #include<stdlib.h> using namespace std; int adj[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10]; main() { int m; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES \n"; for(k=1; k<=m; k++) { cin >>i>>j; adj[i][j]=1; } cout <<"enter initial vertex:"; cin >>v; cout <<"ORDER OF VISITED VERTICES: "; cout << v <<" "; visited[v]=1; k=1; while(k<n) { for(j=n; j>=1; j--) if(adj[v][j]!=0 && visited[j]!=1 && visit[j]!=1) { visit[j]=1; stk[top]=j; top++; } v=stk[--top]; cout<<v << " "; k++; visit[v]=0; visited[v]=1; } } |
