fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include "stackqueue.h"
  5.  
  6. typedef struct _GNode {
  7. 	int id;
  8. 	char data; //The data can be either 'A', 'B', 'C', 'D', 'E' and 'F'.
  9. 	struct _GNode *next;
  10. } GNode;
  11.  
  12. typedef struct {
  13. 	int num;
  14. 	GNode **heads;
  15. } Graph;
  16.  
  17. void CreateGraph(Graph *pgraph, int num, char data[]);
  18.  
  19. void DestroyGraph(Graph *pgraph);
  20.  
  21. void AddEdge(Graph *pgraph, int src, int dest);
  22.  
  23. void PrintGraph(Graph *pgraph);
  24.  
  25. void DFS(Graph *pgraph);
  26.  
  27. void BFS(Graph *pgraph);
  28.  
  29. void GetInput();
  30.  
  31. int main() {
  32.  
  33. 	Graph g;
  34. 	CreateGraph(&g, 5, "ABCFC");
  35. 	AddEdge(&g, 0, 1);
  36. 	AddEdge(&g, 0, 2);
  37. 	AddEdge(&g, 0, 4);
  38. 	AddEdge(&g, 1, 2);
  39. 	AddEdge(&g, 2, 3);
  40. 	AddEdge(&g, 2, 4);
  41. 	AddEdge(&g, 3, 4);
  42.  
  43. 	PrintGraph(&g);
  44.  
  45. 	DFS(&g);	
  46. 	BFS(&g);
  47.  
  48. 	DestroyGraph(&g);
  49.  
  50. 	// GetInput();
  51. 	/*
  52. 	5 7
  53. 	ABCFC
  54. 	0 1
  55. 	0 2
  56. 	0 4
  57. 	1 2
  58. 	2 3
  59. 	2 4
  60. 	3 4
  61. 	*/
  62.  
  63. 	return 0;
  64.  
  65. }
  66.  
  67. void GetInput(){
  68. 	int node, edge, src, des;
  69. 	char *a;
  70. 	scanf("%d %d",&node, &edge);
  71. 	while(getchar()!='\n'); // = fflush(stdin) = __fpurge(stdin)
  72.  
  73. 	a = malloc(sizeof(char)*(node+1));
  74. 	scanf("%s",a);
  75.  
  76. 	Graph g;
  77. 	CreateGraph(&g, node, a);
  78. 	for(int i = 0; i<edge; i++){
  79. 		while(getchar()!='\n'); // = fflush(stdin) = __fpurge(stdin)
  80. 		scanf("%d %d", &src, &des);
  81. 		AddEdge(&g, src, des);
  82. 	}
  83. 	PrintGraph(&g);
  84.  
  85. 	DFS(&g);	
  86. 	BFS(&g);
  87.  
  88. 	DestroyGraph(&g);
  89.  
  90. }
  91.  
  92. /* Modify from here */
  93.  
  94. void CreateGraph(Graph *pgraph, int num, char data[]) {
  95. 	//set number of nodes to num
  96. 	pgraph->num = num;
  97.  
  98. 	//allocate dynamic memory to heads
  99. 	pgraph->heads = (GNode **)malloc(sizeof(GNode*)* num);
  100.  
  101. 	//for each vertex
  102. 	for (int i = 0; i < num; i++) {
  103.  
  104. 		//create a new vertex and add it to heads array
  105. 		pgraph->heads[i] = (GNode *)malloc(sizeof(GNode));
  106. 		pgraph->heads[i]->data = data[i];
  107. 		pgraph->heads[i]->id = i;
  108. 		pgraph->heads[i]->next = NULL;
  109. 	}
  110. };
  111.  
  112. void DestroyGraph(Graph *pgraph) {
  113. 	for (int i = 0; i < pgraph->num; i++) {
  114.  
  115. 		//for each vertex
  116. 		GNode* cur = pgraph->heads[i];
  117.  
  118. 		//free all the connected components (edges)
  119. 		while (cur != NULL) {
  120. 			GNode* temp = cur;
  121. 			cur = cur->next;
  122. 			free(temp);
  123. 		}
  124. 	}
  125. 	//free the vertex
  126. 	free(pgraph->heads);
  127. };
  128.  
  129. void AddEdge(Graph *pgraph, int src, int dest) {
  130. 	//variable declarations
  131. 	GNode* newNode1, *newNode2, *cur;
  132.  
  133. 	//new node to connect source to destination
  134. 	newNode1 = (GNode *)malloc(sizeof(GNode));
  135. 	newNode1->id = dest;
  136. 	newNode1->data = pgraph->heads[dest]->data;
  137. 	newNode1->next = NULL;
  138.  
  139. 	//connect from souce to destination
  140. 	cur = pgraph->heads[src];
  141. 	while (cur->next != NULL)
  142. 		cur = cur->next;
  143. 	cur->next = newNode1;
  144.  
  145. 	//new node to connect destination to source
  146. 	newNode2 = (GNode *)malloc(sizeof(GNode));
  147. 	newNode2->id = src;
  148. 	newNode2->data = pgraph->heads[src]->data;
  149. 	newNode2->next = NULL;
  150.  
  151. 	//connect from destination to source
  152. 	cur = pgraph->heads[dest]; 
  153. 	while (cur->next != NULL)
  154. 		cur = cur->next;
  155. 	cur->next = newNode2;
  156. };
  157.  
  158. void PrintGraph(Graph *pgraph) {
  159.  
  160. 	for (int i = 0; i < pgraph->num; i++) {
  161. 		//for each vertex
  162. 		GNode* edge = pgraph->heads[i];
  163.  
  164. 		//variable that is used to go through the edges
  165. 		GNode* current = edge;
  166.  
  167. 		//go through all the connected edges of each vertex and print them
  168. 		while (current->next != NULL) {
  169. 			printf("(%d, %c) -> ", current->id, current->data);
  170. 			current = current->next;
  171. 		}
  172.  
  173. 		printf("(%d, %c)", current->id, current->data);
  174. 		puts("");
  175. 	}
  176. };
  177.  
  178. void DFS(Graph *pgraph) {
  179. 	//array to count the alphabets
  180. 	int count[100] = { 0, };
  181.  
  182. 	//array to mark nodes as visited
  183. 	bool* visited = (bool *)malloc(sizeof(bool)* pgraph->num);
  184.  
  185. 	//mark all the nodes as unvisited
  186. 	for (int i = 0; i < pgraph->num; i++){
  187. 		visited[i] = false; 
  188. 	}
  189.  
  190. 	//declare and initalize stack 
  191. 	Stack stack;
  192. 	InitStack(&stack);
  193.  
  194. 	//push first vertex to stack
  195. 	Push(&stack, 0);
  196.  
  197. 	//while stack is not empty
  198. 	while (!IsSEmpty(&stack)) {
  199.  
  200. 		//save the peek value and pop stack
  201. 		int vtx = SPeek(&stack);
  202. 		Pop(&stack);
  203.  
  204. 		//skip the iteration if vertex is already visited
  205. 		if (visited[vtx]) continue;
  206.  
  207. 		else {
  208. 				//mark as visited
  209. 				visited[vtx] = true;
  210.  
  211. 				//increment count of alphabet (data)
  212. 				count[pgraph->heads[vtx]->data]++;
  213.  
  214. 				//print vertex
  215. 				printf("%d ", vtx);
  216. 		}
  217.  
  218. 		//set cur to the first connected component of the vertex
  219. 		GNode* cur = pgraph->heads[vtx]->next;
  220.  
  221. 		//push all the unvisited adjacent vertices
  222. 		while (cur != NULL) {
  223. 			if (!visited[cur->id]) {
  224. 				Push(&stack, cur->id);
  225. 			}
  226. 			cur = cur->next;
  227. 		}
  228. 	}
  229. 	puts("");
  230.  
  231. 	//print the number of alphabets
  232. 	for (int i = 65; i < 71; i++) {
  233. 		printf("%c: %d\n", i, count[i]);
  234. 	}
  235. };
  236.  
  237. void BFS(Graph *pgraph) {
  238. 	//array to count the alphabets
  239. 	int count[100] = { 0, };
  240.  
  241. 	//array to mark nodes as visited
  242. 	bool* visited = (bool *)malloc(sizeof(bool)* pgraph->num);
  243.  
  244. 	//mark all the nodes as unvisited
  245. 	for (int i = 0; i < pgraph->num; i++){
  246. 		visited[i] = false;
  247. 	}
  248.  
  249. 	//declare and initalize queue 
  250. 	Queue queue;
  251. 	InitQueue(&queue);
  252.  
  253. 	//enqueue first element to queue
  254. 	EnQueue(&queue, 0);
  255.  
  256. 	//while queue is not empty
  257. 	while (!IsQEmpty(&queue)) {
  258.  
  259. 		//save the front value and dequeue queue
  260. 		int vtx = QPeek(&queue);
  261. 		DeQueue(&queue);
  262.  
  263. 		//skip the iteration if vertex is already visited
  264. 		if (visited[vtx]) continue;
  265.  
  266. 		else {
  267. 			  	//mark as visited
  268. 				visited[vtx] = true;
  269.  
  270. 				//increment count of alphabet (data)
  271. 				count[pgraph->heads[vtx]->data]++;
  272.  
  273. 				//print vertex
  274. 				printf("%d ", vtx);
  275. 		}
  276.  
  277. 		//set cur to the first connected component of the vertex
  278. 		GNode* cur = pgraph->heads[vtx]->next;
  279.  
  280. 		//push all the unvisited adjacent vertices
  281. 		while (cur != NULL) {
  282. 			if (!visited[cur->id])
  283. 				EnQueue(&queue, cur->id);
  284. 			cur = cur->next;
  285. 		}
  286. 	}
  287. 	puts("");
  288.  
  289. 	//print the number of alphabets
  290. 	for (int i = 65; i < 71; i++) {
  291. 		printf("%c: %d\n", i, count[i]);
  292. 	}
  293. };
  294.  
  295. /* Modify to here */
  296.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:4:24: fatal error: stackqueue.h: No such file or directory
 #include "stackqueue.h"
                        ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/kd2epU
language:
C (gcc 8.3)
created:
6 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!