Como solicitado, segue o c\u00f3digo que a turma de 2015.2 desenvolveu em sala de aula para o algoritmo de DFS.<\/p>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <string.h>\r\n\r\nint v, a;\r\nint *pai;\r\nint *dist;\r\nint *vist;\r\n\r\nint **leitura(int &v, int &a)\r\n{\r\n int orig, dest, peso;\r\n int **G;\r\n\r\n \/\/ Obt\u00e9m n\u00famero de v\u00e9rtices e arestas\r\n scanf("%d", &v);\r\n scanf("%d", &a);\r\n\r\n \/\/ Declara a matriz de adjac\u00eancias\r\n G = (int **)malloc(sizeof(int) * v * v);\r\n for (int i = 0; i < v; i++)\r\n G[i] = (int *)malloc(sizeof(int) * v);\r\n\r\n \/\/ Obt\u00e9m os dados de cada aresta\r\n for (int i = 0; i < a; i++)\r\n {\r\n scanf("%d %d %d", &orig, &dest, &peso);\r\n G[orig][dest] = G[dest][orig] = peso;\r\n }\r\n\r\n return G;\r\n}\r\n\r\nvoid percorrer(int dest)\r\n{\r\n printf("%d",dest);\r\n if(pai[dest] != -1)\r\n {\r\n printf("<-");\r\n percorrer(pai[dest]);\r\n }\r\n}\r\n\r\nvoid dfs(int orig, int **G)\r\n{\r\n vist[orig] = 1;\r\n for(int i = 0; i < v; i++)\r\n {\r\n if(G[orig][i] != 0 && vist[i] != 1)\r\n {\r\n pai[i] = orig;\r\n dist[i] = dist[orig] + G[orig][i];\r\n dfs(i,G);\r\n }\r\n }\r\n}\r\n\r\nint main(void)\r\n{\r\n int orig = 0;\r\n int dest = 0;\r\n\r\n int **G = leitura(v, a);\r\n\r\n pai = (int *) malloc (sizeof (int)*v);\r\n dist = (int *) malloc (sizeof (int)*v);\r\n vist = (int *) malloc (sizeof (int)*v);\r\n\r\n for (int i = 0; i < v; i++)\r\n {\r\n pai[i] = -1;\r\n dist[i] = vist[i] = 0;\r\n }\r\n\r\n \/\/ Imprime a matriz de adjac\u00eancias\r\n for (int i = 0; i < v; i++)\r\n {\r\n for (int j = 0; j < v; j++)\r\n printf("%3d ", G[i][j]);\r\n printf("\\n");\r\n }\r\n\r\n printf("\\nDigite a origem: ");\r\n scanf("%d",&orig);\r\n printf("Digite o destino: ");\r\n scanf("%d",&dest);\r\n dfs(orig,G);\r\n percorrer(dest);\r\n\r\n return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Como solicitado, segue o c\u00f3digo que a turma de 2015.2 desenvolveu em sala de aula para o algoritmo de DFS. #include <stdio.h> #include <stdlib.h> #include <string.h> int v, a; int *pai; int *dist; int *vist; int **leitura(int &v, int &a) …<\/p>\n