1 DFS 搜索 修改
有向图有环需要注意 ： 按照路径方向能组成回路才叫有环
例如 三边 A->B, A->C, B->C则 构成的不是环
A->B,B->C,C-A 组成的才是环
// 因为是有向图两个顶点也可以成环 void dfs(Graph g, int i) { int j; color[i] = gray; //灰色 表示正在访问 printf("%c ", g.vex[i]); for (j = 0; j < g.vex_num; j++) { if (i != j && g.edge[i][j] != INFINITY) {//两顶点有边相连 if (color[j] == white) { dfs(g, j);//如果该节点未访问 继续访问其临近节点 } else if(color[j] == gray){ loop_num++; is_dag = false; //有环 } } } color[i] = black; } void dfs_trvsal(Graph g) { int i; for (i = 0; i < g.vex_num; i++) { color[i] = white; loop_num = 0; } link_component = 0; for (i = 0; i < g.vex_num; i++) { if (color[i] == white) { link_component++; dfs(g, i); } } }
完整实现 ：
#include<stdio.h> #include<stdlib.h> #include<ctype.h> #define MAXVEX 100 #define INFINITY 65535 #define TRUE 1 #define FALSE 0 #define gray -1 #define white 0 #define black 1 int loop_num; //环 数量 int color[MAXVEX]; //-1 表示灰色 0表示白色 1 表示黑色 bool is_dag = true;//是否是有向无环图 int link_component; // 连通分量 数量 typedef int EdgeType; typedef char VertexType; typedef struct Graph { VertexType vex[MAXVEX]; EdgeType edge[MAXVEX][MAXVEX]; int vex_num, edge_num; }Graph; void init_graph(Graph *g) { int i, j; for (i = 0; i < g->vex_num; i++) { for (j = 0; j < g->vex_num; j++) { if (i == j) { g->edge[i][j] = 0; } else g->edge[i][j] = INFINITY; } } } char read_char() { char ch; do { ch = getchar(); } while (!isalpha(ch)); return ch; } int get_pos(Graph g, char ch) { int i; for (i = 0; i < g.vex_num; i++) { if (g.vex[i] == ch) return i; } return -1; } void create_graph(Graph *g) { int i, k; //printf("请输入顶点数与边数:\n"); scanf("%d%d", &g->vex_num, &g->edge_num); init_graph(g);// 初始化 //printf("请输入顶点信息:\n"); for (i = 0; i < g->vex_num; i++) { //scanf("%c", g->vex[i]); g->vex[i] = read_char(); } //printf("请输入边的信息:\n"); char c1, c2; int p1, p2,w; for (k = 0; k < g->edge_num; k++) { c1 = read_char(); c2 = read_char(); scanf("%d", &w); p1 = get_pos(*g, c1); p2 = get_pos(*g, c2); g->edge[p1][p2] = w;//有向边的权重 } } void print_graph(Graph g) { int i, j; for (i = 0; i < g.vex_num; i++) { for (j = 0; j < g.vex_num; j++) { if (g.edge[i][j] == INFINITY) printf("\", '*'); else { printf("]", g.edge[i][j]); } } printf("\n"); } } // 因为是有向图两个顶点也可以成环 void dfs(Graph g, int i) { int j; color[i] = gray; //灰色 表示正在访问 printf("%c ", g.vex[i]); for (j = 0; j < g.vex_num; j++) { if (i != j && g.edge[i][j] != INFINITY) {//两顶点有边相连 if (color[j] == white) { dfs(g, j);//如果该节点未访问 继续访问其临近节点 } else if(color[j] == gray){ loop_num++; is_dag = false; //有环 } } } color[i] = black; } void dfs_trvsal(Graph g) { int i; for (i = 0; i < g.vex_num; i++) { color[i] = white; loop_num = 0; } link_component = 0; for (i = 0; i < g.vex_num; i++) { if (color[i] == white) { link_component++; dfs(g, i); } } } int main() { Graph g; create_graph(&g); //print_graph(g); printf("\n\nDFS:\t"); dfs_trvsal(g); printf("\n\n"); if (is_dag) { printf("该有向图无环.\n"); } else { printf("该有向图有%d个环.\n", loop_num); } if (link_component == 1) { printf("该有向图连通."); } else { printf("该有向图不连通."); } getchar(); getchar(); return 0; }
