用c语言实现图的遍历操作

Question

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。

Answer 1

邻接矩阵存储结构：

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define INFINITY 65535

typedef struct
{
    int vexs[MAXVEX]; // 存储顶点的数组
    int arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看作边表
    int numVertexes, numEdges; // 图中当前的顶点数和边数
} MGraph;

// 邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i, int *visited)
{
    int j;
    visited[i] = 1;
    printf("%d ", G.vexs[i]);
    for (j = 0; j < G.numVertexes; j++)
    {
        if (G.arc[i][j] == 1 && !visited[j])
        {
            DFS(G, j, visited);
        }
    }
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
    int i;
    int visited[MAXVEX];
    for (i = 0; i < G.numVertexes; i++)
    {
        visited[i] = 0; // 初始化所有顶点为未访问状态
    }
    for (i = 0; i < G.numVertexes; i++)
    {
        if (!visited[i])
        {
            DFS(G, i, visited);
        }
    }
}

// 邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G)
{
    int i, j;
    int visited[MAXVEX];
    int queue[MAXVEX], front = 0, rear = 0;
    for (i = 0; i < G.numVertexes; i++)
    {
        visited[i] = 0; // 初始化所有顶点为未访问状态
    }
    for (i = 0; i < G.numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i] = 1;
            printf("%d ", G.vexs[i]);
            queue[rear++] = i;
        }
        while (front != rear)
        {
            j = queue[front++];
            for (i = 0; i < G.numVertexes; i++)
            {
                if (G.arc[j][i] == 1 && !visited[i])
                {
                    visited[i] = 1;
                    printf("%d ", G.vexs[i]);
                    queue[rear++] = i;
                }
            }
        }
    }
}

int main()
{
    MGraph G;
    int i, j, k, w;
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G.numVertexes, &G.numEdges);
    for (i = 0; i < G.numVertexes; i++)
    {
        printf("请输入第%d个顶点：", i + 1);
        scanf("%d", &G.vexs[i]);
    }
    for (i = 0; i < G.numVertexes; i++)
    {
        for (j = 0; j < G.numVertexes; j++)
        {
            G.arc[i][j] = INFINITY; // 邻接矩阵初始化
        }
    }
    for (k = 0; k < G.numEdges; k++)
    {
        printf("请输入边(vi, vj)上的下标i，下标j和权值w：\n");
        scanf("%d %d %d", &i, &j, &w);
        G.arc[i][j] = w;
    }
    printf("邻接矩阵数据如下：\n");
    for (i = 0; i < G.numVertexes; i++)
    {
        for (j = 0; j < G.numVertexes; j++)
        {
            printf("%d ", G.arc[i][j]);
        }
        printf("\n");
    }
    printf("邻接矩阵的深度优先遍历结果为：\n");
    DFSTraverse(G);
    printf("\n");
    printf("邻接矩阵的广度优先遍历结果为：\n");
    BFSTraverse(G);
    printf("\n");
    return 0;
}