C语言代码实现用递归的方法实现深度优先搜索遍历连通图

好的，这个问题我可以回答：C语言代码实现用递归的方法实现深度优先搜索遍历连通图的逻辑如下：

1. 初始化一个访问标记数组 visited[]，并将其初始值都设为 false。

2. 从起始节点开始进行递归遍历，遍历过的节点打上访问标记并输出。

3. 对于每个被访问过的节点，遍历它的相邻节点，如果相邻节点没有被访问过，则递归调用深度优先遍历函数。

代码实现如下：

void DFS(int node, bool visited[], int graph[][MAX])
{
visited[node] = true; // 标记已访问节点
printf("%d ", node); // 输出当前节点

// 遍历相邻节点
for (int i = 0; i < MAX; ++i)
{
if (graph[node][i] == 1 && !visited[i])
{
DFS(i, visited, graph); // 递归调用
}
}
}

请确认是否有其他问题需要我回答？

相关问题

C语言代码实现对连通图的深度优先搜索遍历

很高兴为您解答问题。要实现对连通图的深度优先搜索遍历，可以采用递归实现方式，具体代码如下：

#include <stdio.h>

#define MAX_VERTEX_NUM 100 // 图中顶点数的最大值

typedef struct {
    int vertices[MAX_VERTEX_NUM]; // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 顶点数和边数
} MGraph;

int visited[MAX_VERTEX_NUM]; // 标记数组，记录每个节点是否已经被访问过

void DFS(MGraph G, int v) {
    visited[v] = 1; // 标记节点v已经被访问过
    printf("%d ", G.vertices[v]); // 输出节点v的值
    for (int i = 0; i < G.vexnum; i++) { // 依次遍历节点v的所有邻居
        if (G.arcs[v][i] == 1 && visited[i] == 0) { // 如果节点i是节点v的邻居，并且没有被访问过
            DFS(G, i); // 递归访问节点i
        }
    }
}

int main() {
    MGraph G;
    // 省略初始化代码
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0; // 初始化标记数组
    }
    DFS(G, 0); // 从节点0开始深度优先遍历
    return 0;
}

希望我的回答对您有帮助。如果您有其他问题，欢迎继续提问。

先依次输入有向图的顶点信息，再依次输入有向图的弧信息，建立图的邻接表存储结构并将其打印输出； 接下来在建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列； 最后在建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现

好的，以下是C语言实现的代码：

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

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef char VertexType;  // 顶点类型

typedef struct ArcNode {
    int adjvex;  // 邻接点在顶点数组中的位置下标
    struct ArcNode *nextarc;  // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    VertexType data;  // 顶点信息
    ArcNode *firstarc;  // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;  // 顶点数组
    int vexnum, arcnum;  // 图的当前顶点数和弧数
} ALGraph;

// 创建有向图的邻接表存储结构
void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和弧数：");
    scanf("%d %d", &(G->vexnum), &(G->arcnum));

    printf("请输入顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL;
    }

    printf("请输入弧信息：");
    for (int k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条弧的两个端点：", k + 1);
        VertexType v1, v2;
        scanf(" %c %c", &v1, &v2);

        int i, j;
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) {
                break;
            }
        }

        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

// 深度优先搜索遍历
void DFS(ALGraph G, int v, int visited[]) {
    visited[v] = 1;
    printf("%c ", G.vertices[v].data);

    ArcNode *p = G.vertices[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;
        if (visited[w] == 0) {
            DFS(G, w, visited);
        }
        p = p->nextarc;
    }
}

void DFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0};
    printf("深度优先搜索遍历顶点序列为：");
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

// 广度优先搜索遍历
void BFSTraverse(ALGraph G) {
    int visited[MAX_VERTEX_NUM] = {0};
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;

    printf("广度优先搜索遍历顶点序列为：");
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            printf("%c ", G.vertices[i].data);
            queue[rear++] = i;
        }
        while (front != rear) {
            int j = queue[front++];
            ArcNode *p = G.vertices[j].firstarc;
            while (p != NULL) {
                int k = p->adjvex;
                if (visited[k] == 0) {
                    visited[k] = 1;
                    printf("%c ", G.vertices[k].data);
                    queue[rear++] = k;
                }
                p = p->nextarc;
            }
        }
    }
    printf("\n");
}

int main() {
    ALGraph G;
    CreateGraph(&G);

    printf("邻接表存储结构为：\n");
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c -> ", G.vertices[i].data);
        ArcNode *p = G.vertices[i].firstarc;
        while (p != NULL) {
            printf("%c -> ", G.vertices[p->adjvex].data);
            p = p->nextarc;
        }
        printf("NULL\n");
    }

    DFSTraverse(G);
    BFSTraverse(G);

    return 0;
}

在程序中，我们首先定义了结构体 `ArcNode`（表示弧）和 `VNode`（表示顶点），并将 `VNode` 数组定义为 `AdjList`。`ALGraph` 结构体包含了 `AdjList` 数组、图的顶点数 `vexnum` 和弧数 `arcnum`。

`CreateGraph` 函数用于创建有向图的邻接表存储结构。我们先输入顶点数和弧数，然后输入每个顶点的信息，最后输入每条弧的信息。在输入弧的信息时，我们需要找到它们在顶点数组中的下标，然后将弧插入到相应的邻接表中。

`DFS` 函数用于进行深度优先搜索遍历。我们首先将当前顶点标记为已访问，并输出它的信息。然后遍历它的邻接表，对于每个未访问的邻接点，递归调用 `DFS` 函数。这样，我们就可以依次遍历图中所有连通的顶点。

`DFSTraverse` 函数用于对整个图进行深度优先搜索遍历。我们从第一个未访问的顶点开始，依次调用 `DFS` 函数。

`BFSTraverse` 函数用于进行广度优先搜索遍历。我们使用一个队列来存储已访问的顶点，以便按照广度优先的顺序访问它们。首先将第一个未访问的顶点标记为已访问，并输出它的信息。然后将它加入队列中。接下来，从队列中取出一个顶点，遍历它的邻接表，并将未访问的邻接点加入队列中。这样，我们就可以依次遍历图中所有连通的顶点。

最后，我们在 `main` 函数中依次调用上述函数，即可完成有向图的建立和遍历。