【C++】DFS簡單範例 (for connectivity / weighted graph shortest path)

?

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

#include <cstdio> #include <cstdlib> #define N 100 using namespace std; struct node{     int color, pi, start, finish; }; node node[N]; int adj_matrix[N][N], time, n; void init(){     time = 0;     for (int i=1; i<=n; i++) {         node[i].color = 0;         node[i].pi = -1;         for (int j=1; j<=n; j++)             adj_matrix[i][j] = 0;     } } void dfs_visit(int u){     printf("visit %d\n", u);     node[u].color = 1;     node[u].start = ++time;     for (int v=1; v<=n; v++) {         if (adj_matrix[u][v] && node[v].color==0){             node[v].pi = u;             dfs_visit(v);         }     }     node[u].finish = ++time; } int main(){     init();     scanf("%d", &n);/*有幾個點*/     while (true) {         int a, b;         scanf("%d %d", &a, &b);         if(a==0) break;         adj_matrix[a][b] = adj_matrix[b][a] = 1;     }           int tree_count=0;     for (int i=1; i<=n; i++) {         if (node[i].color==0){             dfs_visit(i);             tree_count++;         }     }     return 0; }