考研图C语言深度优先遍历代码及注释

好的，以下是C语言实现深度优先遍历的代码及注释：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_ARC_NUM 500 // 最大边数

typedef int VertexType; // 顶点的数据类型

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 顶点数和边数
} MGraph; // 图的邻接矩阵表示法

typedef struct {
    VertexType data; // 数据域
    int firstarc; // 头结点
} VNode;

typedef struct {
    VNode adjlist[MAX_VERTEX_NUM]; // 邻接表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph; // 图的邻接表表示法

// 初始化邻接矩阵图
void InitMGraph(MGraph *G)
{
    int i, j;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            G->arcs[i][j] = 0; // 初始化为0
        }
    }
    G->vexnum = 0;
    G->arcnum = 0;
}

// 添加顶点到邻接矩阵图
void AddVertexToMGraph(MGraph *G, VertexType v)
{
    G->vexs[G->vexnum++] = v; // 加入顶点数组
}

// 添加边到邻接矩阵图
void AddEdgeToMGraph(MGraph *G, int v1, int v2)
{
    G->arcs[v1][v2] = 1;
    G->arcs[v2][v1] = 1; // 无向图，所以要添加两条边
    G->arcnum++; // 边数加1
}

// 初始化邻接表图
void InitALGraph(ALGraph *G)
{
    int i;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->adjlist[i].firstarc = -1; // 初始化为-1
    }
    G->vexnum = 0;
    G->arcnum = 0;
}

// 添加顶点到邻接表图
void AddVertexToALGraph(ALGraph *G, VertexType v)
{
    G->adjlist[G->vexnum].data = v; // 加入数据
    G->vexnum++; // 顶点数加1
}

// 添加边到邻接表图
void AddEdgeToALGraph(ALGraph *G, int v1, int v2)
{
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v2; // 邻接点为v2
    p->nextarc = G->adjlist[v1].firstarc; // 头插法
    G->adjlist[v1].firstarc = p; // 头节点指向新节点
    G->arcnum++; // 边数加1
}

// 深度优先遍历邻接矩阵图
void DFSTraverseMGraph(MGraph G, int v, int visited[])
{
    printf("%d ", v); // 访问该顶点
    visited[v] = 1; // 标记为已访问
    int i;
    for (i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] == 1 && !visited[i]) { // 如果存在边且未访问
            DFSTraverseMGraph(G, i, visited); // 递归访问邻接点
        }
    }
}

// 深度优先遍历邻接表图
void DFS(ALGraph *G, int v, int visited[])
{
    printf("%d ", v); // 访问该顶点
    visited[v] = 1; // 标记为已访问
    ArcNode *p = G->adjlist[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex]) { // 如果邻接点未访问
            DFS(G, p->adjvex, visited); // 递归访问邻接点
        }
        p = p->nextarc; // 访问下一个邻接点
    }
}

int main()
{
    MGraph G;
    InitMGraph(&G);

    AddVertexToMGraph(&G, 1);
    AddVertexToMGraph(&G, 2);
    AddVertexToMGraph(&G, 3);
    AddVertexToMGraph(&G, 4);
    AddVertexToMGraph(&G, 5);

    AddEdgeToMGraph(&G, 0, 1);
    AddEdgeToMGraph(&G, 0, 2);
    AddEdgeToMGraph(&G, 1, 3);
    AddEdgeToMGraph(&G, 1, 4);

    int visited[MAX_VERTEX_NUM] = {0};
    DFSTraverseMGraph(G, 0, visited);

    ALGraph G;
    InitALGraph(&G);

    AddVertexToALGraph(&G, 1);
    AddVertexToALGraph(&G, 2);
    AddVertexToALGraph(&G, 3);
    AddVertexToALGraph(&G, 4);
    AddVertexToALGraph(&G, 5);

    AddEdgeToALGraph(&G, 0, 1);
    AddEdgeToALGraph(&G, 0, 2);
    AddEdgeToALGraph(&G, 1, 3);
    AddEdgeToALGraph(&G, 1, 4);

    int visited[MAX_VERTEX_NUM] = {0};
    DFS(&G, 0, visited);

    return 0;
}

这里实现了两种图的表示方法：邻接矩阵和邻接表，分别对应 `MGraph` 和 `ALGraph` 结构体。其中，邻接矩阵使用二维数组表示，邻接表使用链表表示。在添加顶点和边的函数中，都是将数据存储到对应的结构体中，同时更新顶点数和边数。在深度优先遍历函数中，使用递归的方式遍历图，标记已访问的节点，避免重复访问。