fork(4) download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <limits.h>
  4. typedef unsigned short word_t;
  5. typedef unsigned char  byte_t;
  6.  
  7. typedef struct node {
  8. 	struct node* next;
  9. 	word_t v;
  10. } node_t;
  11.  
  12. typedef struct {
  13. 	node_t* h, *t;
  14. } queue_t;
  15.  
  16. void   queue_init(queue_t* q){ q->h = q->t = NULL; }
  17. int    queue_empty(queue_t* q){ return (q->h == NULL); }
  18. word_t queue_front(queue_t* q) { return q->h->v; }
  19. int    queue_push(queue_t* q, word_t v);
  20. void   queue_pop(queue_t* q);
  21. void   queue_clear(queue_t* q);
  22.  
  23. typedef struct {
  24. 	word_t v, p;
  25. } vert_t;
  26. byte_t** graph_input(FILE* _in, int* n);
  27. void     graph_free(byte_t** g, int n);
  28. word_t*  graph_bfs(byte_t** g, int n, word_t s, word_t e, int* m);
  29.  
  30.  
  31. int main(void){
  32. 	int      i, n, m;
  33. 	word_t*  p, s, e;
  34. 	byte_t** g;
  35.  
  36. /*   ввод из файла
  37. 	FILE* f = fopen("graph.txt", "rt");
  38. 	if(f == NULL)
  39. 		return 1;
  40. 	g = graph_input(f, &n);
  41. 	fclose(f);
  42. */
  43. 	g = graph_input(stdin, &n);
  44. 	if(g == NULL)
  45. 		return 1;
  46.  
  47. 	s = 3;//старт
  48. 	e = 4;//конец
  49. 	p = graph_bfs(g, n, s, e, &m);
  50. 	if(p != NULL){
  51. 		printf("path: ");
  52. 		for(i = 0; i < m; ++i)
  53. 			printf("%u ", p[i]);
  54. 		putchar('\n');
  55.  
  56. 		free(p);
  57. 	} else
  58. 		fputs("error find bfs!\n", stderr);
  59.  
  60. 	graph_free(g, n);
  61. 	return 0;
  62. }
  63.  
  64. //поиск в ширину
  65. word_t* graph_bfs(byte_t** g, int n, word_t s, word_t e, int* m){
  66. 	int     i, y;
  67. 	queue_t q;
  68. 	vert_t* vs;
  69. 	word_t  v, *p, *d, *j;
  70.  
  71. 	p  = NULL;
  72. 	vs = (vert_t*)malloc((size_t)n * sizeof(vert_t));
  73. 	if(vs == NULL)
  74. 		return NULL;
  75. 	for(i = 0; i < n; ++i)
  76. 		vs[i].p = vs[i].v = USHRT_MAX;
  77.  
  78. 	vs[s].v = 0;
  79. 	queue_init(&q);
  80. 	queue_push(&q, s);
  81.  
  82. 	y = 0;
  83. 	while(! queue_empty(&q)){
  84. 		v = queue_front(&q);
  85. 		queue_pop(&q);
  86. 		if(v == e){
  87. 			y = 1;
  88. 			break;
  89. 		}
  90. 		for(i = 0; i < n; ++i){
  91. 			if((g[v][i] != 0) && (vs[i].v > (vs[v].v + 1))){
  92. 				queue_push(&q, (word_t)i);
  93. 				vs[i].p = v;
  94. 				vs[i].v = vs[v].v + 1;
  95. 			}
  96. 		}
  97. 	}
  98. 	queue_clear(&q);
  99.  
  100. 	if(y){
  101. 		v = e;
  102. 		i = 1;
  103. 		while(v != s){
  104. 			v = vs[v].p;
  105. 			++i;
  106. 		}
  107. 		p = (word_t*)malloc((size_t)i * sizeof(word_t));
  108. 		if(p == NULL)
  109. 			return NULL;
  110.  
  111. 		d = p;
  112. 		for(*d++ = e; e != s; e = vs[e].p)
  113. 			*d++ = vs[e].p;
  114.  
  115. 		for(--d, j = p; j < d; ++j, --d){
  116. 			v  = *d;
  117. 			*d = *j;
  118. 			*j = v;
  119. 		}
  120. 		*m = i;
  121. 	}
  122. 	free(vs);
  123. 	return p;
  124. }
  125.  
  126. /*
  127. ввод неориентированного графа, формат
  128. 	N - кол-во вершин  M - кол-во рёбер
  129. */
  130. byte_t** graph_input(FILE* _in, int* n){
  131. 	int      i, j, vn, em, a, b;
  132. 	byte_t** g;
  133. 	if((fscanf(_in, "%d %d", &vn, &em) != 2) || (vn <= 1) || (em <= 1))
  134. 		return NULL;
  135.  
  136. 	g = (byte_t**)malloc((size_t)vn * sizeof(byte_t*));
  137. 	if(g == NULL)
  138. 		return NULL;
  139.  
  140. 	for(i = 0; i < vn; ++i){
  141. 		g[i] = (byte_t*)calloc((size_t)vn, sizeof(byte_t));
  142. 		if(g[i] == NULL){
  143. 			i -= 1;
  144. 			goto err;
  145. 		}
  146. 	}
  147.  
  148. 	for(i = 0; i < em; ++i){
  149. 		if(fscanf(_in, "%d %d", &a, &b) == 2){
  150. 			if((a < vn) && (b < vn))
  151. 				g[a][b] = g[b][a] = 1;
  152. 		} else
  153. 			break;
  154. 	}
  155. 	*n = vn;
  156. 	return g;
  157. err:
  158. 	for(j = i; j >= 0; --j)
  159. 		free(g[j]);
  160. 	free(g);
  161. 	return NULL;
  162. }
  163.  
  164. //удаление графа из памяти
  165. void graph_free(byte_t** g, int n){
  166. 	int i;
  167. 	for(i = 0; i < n; ++i)
  168. 		free(g[i]);
  169. 	free(g);
  170. }
  171.  
  172. //---------------
  173. //вставка
  174. int queue_push(queue_t* q, word_t v){
  175. 	node_t* p = (node_t*)malloc(sizeof(node_t));
  176. 	if(p != NULL){
  177. 		p->v    = v;
  178. 		p->next = NULL;
  179. 		if(q->h == NULL)
  180. 			q->h = q->t = p;
  181. 		else {
  182. 			q->t->next = p;
  183. 			q->t = p;
  184. 		}
  185. 	}
  186. 	return (p != NULL);
  187. }
  188.  
  189. //извлечение
  190. void queue_pop(queue_t* q){
  191. 	node_t* t;
  192. 	if(q->h != NULL){
  193. 		t    = q->h;
  194. 		q->h = q->h->next;
  195. 		free(t);
  196. 		if(q->h == NULL)
  197. 			q->t = NULL;
  198. 	}
  199. }
  200.  
  201. //удаление всех
  202. void queue_clear(queue_t* q){
  203. 	while(! queue_empty(q))
  204. 		queue_pop(q);
  205. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
5 4
0 1
0 2
0 3
1 4
stdout
copy 
path: 3 0 1 4
https://ideone.com/uga7zR
language:
C++ (gcc 8.3)
created:
10 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!