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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
| #include <stdio.h> #include <stdlib.h>
#define MAX 32767
typedef struct Graph { char* vexs; int** arcs; int vexNum; int arcNum; }Graph;
Graph* initGraph(int vexNum) { Graph* G = (Graph*)malloc(sizeof(Graph)); G -> vexs = (char*)malloc(sizeof(char) * vexNum); G -> arcs = (int**)malloc(sizeof(int*) * vexNum); for (int i = 0 ; i < vexNum; i++) { G -> arcs[i] = (int*)malloc(sizeof(int) * vexNum); } G -> vexNum = vexNum; G -> arcNum = 0; return G; }
void createGraph(Graph* G, char* vexs, int* arcs) { for (int i = 0 ; i < G -> vexNum; i++) { G -> vexs[i] = vexs[i]; for (int j = 0; j < G -> vexNum; j++) { G -> arcs[i][j] = *(arcs + i * G -> vexNum + j); if (G -> arcs[i][j] != 0 && G -> arcs[i][j] != MAX) G -> arcNum ++; } } G -> arcNum /= 2; }
void DFS(Graph* G, int* visited, int index) { printf("%c\t", G -> vexs[index]); visited[index] = 1; for (int i = 0; i < G ->vexNum; i++) { if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX && !visited[i]) { DFS(G, visited, i); } } }
int getMin(int* d, int* s, Graph* G) { int min = MAX; int index; for (int i = 0; i < G -> vexNum; i++) { if (!s[i] && d[i] < min) { min = d[i]; index = i; } } return index; }
void dijkstra(Graph* G, int index) { int* s = (int*)malloc(sizeof(int) * G -> vexNum); int* p = (int*)malloc(sizeof(int) * G -> vexNum); int* d = (int*)malloc(sizeof(int) * G -> vexNum); for (int i = 0; i < G -> vexNum; i++) { if (G -> arcs[index][i] > 0 && G -> arcs[index][i] != MAX) { d[i] = G -> arcs[index][i]; p[i] = index; } else { d[i] = MAX; p[i] = -1; } if (i == index) { s[i] = 1; d[i] = 0; } else s[i] = 0; } for (int i = 0; i < G -> vexNum - 1; i++) { int index = getMin(d, s, G); s[index] = 1; for (int j = 0; j < G -> vexNum; j++) { if (!s[j] && d[index] + G -> arcs[index][j] < d[j]) { d[j] = d[index] + G -> arcs[index][j]; p[j] = index; } } } for (int i = 0; i < G ->vexNum; i++) { printf("%d %d %d\n", s[i], p[i], d[i]); } }
int main() { Graph* G = initGraph(7); int* visited = (int*)malloc(sizeof(int) * G -> vexNum); for (int i = 0; i < G -> vexNum; i++) visited[i] = 0; int arcs[7][7] = { 0, 12, MAX, MAX, MAX, 16, 14, 12, 0, 10, MAX, MAX, 7, MAX, MAX, 10, 0, 3, 5, 6, MAX, MAX, MAX, 3, 0, 4, MAX, MAX, MAX, MAX, 5, 4, 0, 2, 8, 16, 7, 6, MAX, 2, 0, 9, 14, MAX, MAX, MAX, 8, 9, 0 }; createGraph(G, "1234567", (int*)arcs); DFS(G, visited, 0); printf("\n"); dijkstra(G, 0); return 0; }
|