#include <stdio.h> #include <stdlib.h> #define INFINITY 32768 #define MaxVexNum 20 typedef char ElemType; typedef enum {DG, DN, UDG, UDN} GraphKind; typedef struct { ElemType vexs[MaxVexNum]; int arcs[MaxVexNum][MaxVexNum]; int vexnum, arcnum; } AMGraph; int locate(AMGraph G, char v) { int k; for (k = 0; k < G.vexnum; k++) { if (G.vexs[k] == v) { return k; } } return -1; } void CreatMGraph(AMGraph *G) { int i, j, k; char v1, v2; scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->arcs[i][j] = 0; } } for (i = 0; i < G->vexnum; i++) { scanf(" %c", &G->vexs[i]); } getchar(); for (k = 0; k < G->arcnum; k++) { scanf("%c%c", &v1, &v2); getchar(); i = locate(*G, v1); j = locate(*G, v2); G->arcs[i][j] = 1; G->arcs[j][i] = 1; } } int visited[MaxVexNum]; void DepthFirstSearch(AMGraph g, int v0) { visited[v0] = 1; printf("%c", g.vexs[v0]); for (int vj = 0; vj < g.vexnum; vj++) { if (!visited[vj] && g.arcs[v0][vj] == 1) { DepthFirstSearch(g, vj); } } } void TraverseGraph(AMGraph g) { for (int vi = 0; vi < g.vexnum; vi++) { visited[vi] = 0; } for (int vi = 0; vi < g.vexnum; vi++) { if (!visited[vi]) { DepthFirstSearch(g, vi); } } } int main() { AMGraph G; CreatMGraph(&G); TraverseGraph(G); printf("\n%d",G.vexnum-1); return 0; }找连通分量

这段代码实现了对于一个无向图的遍历，并且在遍历完成后输出该无向图的连通分量数量。具体实现如下：

1. 定义一个 `visited[]` 数组来标记节点是否已访问过。

2. 实现一个 `DepthFirstSearch()` 函数，使用深度优先搜索（DFS）算法来遍历无向图。在该函数中，首先标记当前节点已访问，然后输出该节点的值。接着遍历所有与当前节点相邻的节点，如果该节点未被访问过且与当前节点有连边，则递归调用 `DepthFirstSearch()` 函数。

3. 实现一个 `TraverseGraph()` 函数，遍历整个无向图。在该函数中，首先将 `visited[]` 数组全部初始化为 0。然后从节点 0 开始遍历整个图，对于每个未被访问过的节点，调用 `DepthFirstSearch()` 函数进行遍历。由于无向图可能不连通，因此需要对每个未被访问过的节点都进行一次遍历。

4. 在 `main()` 函数中，先调用 `CreatMGraph()` 函数创建无向图。然后调用 `TraverseGraph()` 函数进行遍历，并输出连通分量数量，即为节点数减一。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

#define INFINITY 32768
#define MaxVexNum 20

typedef char ElemType;

typedef enum {DG, DN, UDG, UDN} GraphKind;

typedef struct {
    ElemType vexs[MaxVexNum];
    int arcs[MaxVexNum][MaxVexNum];
    int vexnum, arcnum;
} AMGraph;

int locate(AMGraph G, char v) {
    int k;
    for (k = 0; k < G.vexnum; k++) {
        if (G.vexs[k] == v) {
            return k;
        }
    }
    return -1;
}

void CreatMGraph(AMGraph *G) {
    int i, j, k;
    char v1, v2;
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar();
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = 0;
        }
    }
    for (i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vexs[i]);
    }
    getchar();
    for (k = 0; k < G->arcnum; k++) {
        scanf("%c%c", &v1, &v2);
        getchar();
        i = locate(*G, v1);
        j = locate(*G, v2);
        G->arcs[i][j] = 1;
        G->arcs[j][i] = 1;
    }
}

int visited[MaxVexNum];

void DepthFirstSearch(AMGraph g, int v0) {
    visited[v0] = 1;
    printf("%c", g.vexs[v0]);
    for (int vj = 0; vj < g.vexnum; vj++) {
        if (!visited[vj] && g.arcs[v0][vj] == 1) {
            DepthFirstSearch(g, vj);
        }
    }
}

void TraverseGraph(AMGraph g) {
    for (int vi = 0; vi < g.vexnum; vi++) {
        visited[vi] = 0;
    }
    for (int vi = 0; vi < g.vexnum; vi++) {
        if (!visited[vi]) {
            DepthFirstSearch(g, vi);
            printf("\n");
        }
    }
}

int main() {
    AMGraph G;
    CreatMGraph(&G);
    TraverseGraph(G);
    printf("%d", G.vexnum - 1);
    return 0;
}

该代码中，对于每个连通分量， `DepthFirstSearch()` 函数会输出一行，并且在遍历完成后输出连通分量数量，即为节点数减一。