C语言实现图的深度优先遍历算法实验报告

实验题目：图的深度优先遍历

实验目的： 掌握图的深度优先遍历的基本思想和实现方法，加深对图数据结构的理解。

实验原理： 深度优先遍历是一种常用的图遍历方法。其基本思想是从图的某个顶点出发，沿着一条未访问过的边走到下一个顶点，继续沿着未访问过的边走下去，直到走到一个没有未访问过的边的顶点为止。然后回溯到上一个顶点，再走一条未访问过的边，继续上述过程，直到所有的顶点都被访问过为止。

实验步骤：

定义图的数据结构

typedef struct Graph
{
    int vexnum; // 顶点数
    int arcnum; // 边数
    int **arc;  // 邻接矩阵
}Graph;

初始化邻接矩阵

void initGraph(Graph *G)
{
    int i, j;
    G->arc = (int**)malloc(sizeof(int*) * G->vexnum);
    for(i = 0; i < G->vexnum; i++)
    {
        G->arc[i] = (int*)malloc(sizeof(int) * G->vexnum);
        for(j = 0; j < G->vexnum; j++)
        {
            G->arc[i][j] = 0; // 初始化为0
        }
    }
}

创建图

void createGraph(Graph *G)
{
    int i, j, v1, v2;
    printf('请输入顶点数和边数：');
    scanf('%d%d', &G->vexnum, &G->arcnum);

    initGraph(G); // 初始化邻接矩阵

    printf('请输入每条边的两个顶点的编号：\n');
    for(i = 0; i < G->arcnum; i++)
    {
        scanf('%d%d', &v1, &v2);
        G->arc[v1][v2] = 1; // 有边则为1
        G->arc[v2][v1] = 1; // 无向图，两个方向都要改
    }
}

深度优先遍历

void DFS(Graph *G, int v, int *visited)
{
    int i;
    visited[v] = 1; // 标记为已访问
    printf('%d ', v); // 输出顶点编号
    for(i = 0; i < G->vexnum; i++) // 遍历邻接矩阵
    {
        if(G->arc[v][i] == 1 && !visited[i]) // 如果有边且未访问过
        {
            DFS(G, i, visited); // 递归访问
        }
    }
}

主函数

int main()
{
    Graph G;
    int *visited; // 记录每个顶点是否被访问过
    visited = (int*)malloc(sizeof(int) * G.vexnum);

    createGraph(&G); // 创建图

    int i;
    for(i = 0; i < G.vexnum; i++) // 初始化visited数组
    {
        visited[i] = 0;
    }

    printf('深度优先遍历结果为：\n');
    DFS(&G, 0, visited); // 从第一个顶点开始遍历

    return 0;
}

实验结果：

请输入顶点数和边数：5 6
请输入每条边的两个顶点的编号：
0 1
0 2
0 3
1 4
2 4
3 4
深度优先遍历结果为：
0 1 4 2 3

实验结论： 通过本次实验，我成功地掌握了图的深度优先遍历的基本思想和实现方法，加深了对图数据结构的理解。