核心思想:
根据图与树的关系 到 图与连通分量关系 知
无环时候： 顶点数 -边数 = 树个数 （连通分量数）
有环时候：顶点数-边数 < 树个数（连通分量数）
连通分量数可以在dfs中求得
void dfs_trvsal(Graph g) { int i; for (i = 0; i < g.vex_num; i++) { visited[i] = FALSE; } link_component = 0; for (i = 0; i < g.vex_num; i++) { if (!visited[i]) { link_component++; //图连通的话 该for循环只进行一次 就可以遍历整个图了 连通分量也就是1 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 Bool int Bool visited[MAXVEX]; 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, w, 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++) { g->vex[i] = read_char(); } //printf("请输入边的信息:\n"); char c1, c2; int p1, p2; 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; g->edge[p2][p1] = g->edge[p1][p2]; } } 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; visited[i] = TRUE; printf("%c ", g.vex[i]); for (j = 0; j < g.vex_num; j++) { if (!visited[j] && g.edge[i][j] != INFINITY && i != j) { dfs(g, j); visited[j] = TRUE; } } } void dfs_trvsal(Graph g) { int i; for (i = 0; i < g.vex_num; i++) { visited[i] = FALSE; } link_component = 0; for (i = 0; i < g.vex_num; i++) { if (!visited[i]) { link_component++; dfs(g, i); } } } int main() { int i; Graph g; create_graph(&g); //print_graph(g); dfs_trvsal(g); printf("\n"); if ((link_component + g.edge_num) > g.vex_num) { // 核心 printf("有环."); } else { printf("无环.\n"); } if (link_component == 1) { printf("图连通."); } else { printf("图不连通."); } getchar(); getchar(); return 0; }
