fork(1) download
copy 
  1. #include<stdio.h>
  2.  
  3. struct node
  4. {
  5.  
  6. 	int val;
  7. 	struct node* next;
  8.  
  9. };
  10.  
  11. struct graph
  12. {
  13.  
  14. 	int V;
  15. 	struct node **array;	
  16.  
  17. };
  18.  
  19. struct graph *createGraph(int v)
  20. {
  21.  
  22. 	struct graph *G= (struct graph*)malloc(sizeof(struct graph));
  23.  
  24. 	G->V=v;
  25. 	G->array = (struct node **)malloc(v*sizeof(struct node*));
  26.  
  27. 	int i=0;
  28. 	for(i=0;i<v;i++)
  29. 	{
  30. 		G->array[i]=NULL;
  31. 	}
  32.  
  33. 	return G;	
  34.  
  35. }
  36. void insertEdge(struct graph *G, int v1, int v2)
  37. {
  38.  
  39. 	struct node *temp = G->array[v1];
  40.  
  41. 	struct node *newNode = (struct node*)malloc(sizeof(struct node));
  42. 	newNode->val=v2;
  43. 	newNode->next=temp;
  44.  
  45. 	G->array[v1]= newNode;
  46.  
  47.  
  48. }
  49. void printAdjacencyList(struct graph *G)
  50. {
  51.  
  52. 	int i;
  53. 	struct node *temp;
  54. 	for(i=0;i<G->V;i++)
  55. 	{
  56. 		printf("%d : ",i);
  57. 		temp=G->array[i];
  58. 		while(temp)
  59. 		{
  60. 			printf("%d ",temp->val);
  61. 			temp=temp->next;
  62. 		}
  63. 		printf("\n");
  64. 	}
  65.  
  66. }
  67.  
  68. void dfsEdges(struct graph*G, int v, int *visited, int *arrTime, int *depTime)
  69. {
  70. 	static int time=0;
  71.  
  72.  
  73. 	visited[v]=1;
  74. 	arrTime[v]=time++;
  75. 	//printf("%d ",v);
  76.  
  77. 	struct node *temp = G->array[v];
  78. 	while(temp!=NULL)
  79. 	{
  80. 		if(visited[temp->val] != 1)
  81. 		{
  82. 			dfsEdges(G,temp->val,visited,arrTime,depTime);
  83. 		}
  84. 		else
  85. 		{
  86. 			/* 
  87. 			If we visit a node already visited and we have not yet departed from that node, than it 
  88. 			makes a back edge.
  89.  
  90. 			Else, there are two possibilities - cross edge or forward edge. In both these cases we visit a
  91. 			node fron which we have alredy departed. So here, we can distinguish between them using the arrival time.
  92. 			If it is a forward edge (going from ancestor to descendent, u -> v), arrival time of u will be less v and if it is 
  93. 			cross edge, arrival time of u will be greater than v
  94. 			*/
  95. 			if(depTime[temp->val] ==-1)
  96. 			printf("\n%d - %d is back edge\n",v,temp->val);
  97. 			else
  98. 			{
  99. 				if(arrTime[v]<arrTime[temp->val])
  100. 				printf("\n%d - %d is forward edge\n",v,temp->val);
  101. 				else
  102. 				printf("\n%d - %d is cross edge\n",v,temp->val);
  103. 			}
  104.  
  105. 		}
  106. 		temp=temp->next;
  107.  
  108. 	}
  109. 	depTime[v]=time++;
  110.  
  111. }
  112.  
  113. int main()
  114. {
  115. 	struct graph *G = createGraph(6);
  116.  
  117. 	insertEdge(G, 0, 3);
  118.     insertEdge(G, 0, 2);	
  119. 	insertEdge(G, 1, 0);
  120.     insertEdge(G, 1, 3);
  121.    	insertEdge(G, 2, 3);
  122.     insertEdge(G, 2, 4);
  123.     insertEdge(G, 3, 5);
  124.     insertEdge(G, 4, 0);	
  125.     insertEdge(G, 5, 4);
  126.  
  127.  
  128. 	printAdjacencyList(G);
  129.  
  130.  
  131.  
  132. 	printf("\nDFS:\n");
  133. 	int *visited = (int*)malloc(G->V * sizeof(int));
  134. 	int *arrTime = (int*)malloc(G->V * sizeof(int));
  135. 	int *depTime = (int*)malloc(G->V * sizeof(int));
  136. 	int *parent = (int*)malloc(G->V * sizeof(int));
  137.  
  138. 	int i;
  139.  
  140. 	/*
  141. 	for(i=0;i<G->V;i++)
  142. 	{
  143. 		if(visited[i]!=1)
  144. 		dfs(G,i,visited);
  145. 	}
  146. 	*/
  147.  
  148. 	for(i=0;i<G->V;i++)
  149. 	arrTime[i]=-1;
  150. 	for(i=0;i<G->V;i++)
  151. 	visited[i]=0;
  152. 	for(i=0;i<G->V;i++)
  153. 	depTime[i]=-1;
  154.  
  155. 	for(i=0;i<G->V;i++)
  156. 	{
  157. 		if(visited[i]!=1)
  158. 		dfsEdges(G,i,visited,arrTime,depTime);
  159. 	}
  160.  
  161. 	printf("\n");
  162. 	printf("\nArrival Time\n");
  163. 	for(i=0;i<G->V;i++)
  164. 	printf("%d ",arrTime[i]);
  165.  
  166. 	printf("\nDeparture Time\n");	
  167. 	for(i=0;i<G->V;i++)
  168. 	printf("%d ",depTime[i]);
  169.  
  170. 	printf("\n");
  171.  
  172. 	return 0;
  173. }
  174.  
Success #stdin #stdout 0s 2140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 : 2 3 
1 : 3 0 
2 : 4 3 
3 : 5 
4 : 0 
5 : 4 

DFS:

4 - 0 is back edge

5 - 4 is cross edge

0 - 3 is forward edge

1 - 3 is cross edge

1 - 0 is cross edge


Arrival Time
0 10 1 4 2 5 
Departure Time
9 11 8 7 3 6
https://ideone.com/18xfGW
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!