【趣学C语言和数据结构100例】

问题描述

76.二叉树的层次遍历算法

77.用邻接表实现广度优先搜索算法

78.用邻接矩阵实现广度优先搜索算法

79.用邻接表实现深度优先搜索算法

80.用邻接矩阵实现深度优先搜索算法

代码分析

==76.二叉树的层次遍历算法==
分析：无返回值+传入树，故函数名为：void 函数名(Bitree T)；使用队列。先创建队列，然后初始化队列，将根节点进行入队，定义一个p用来接收出队元素，只要队列不为空，就一直进行创造。先将根节点进行出队，访问节点p，即输出 。如果左子节点存在，将其入队。如果右子节点存在，将其入队。当队列为空时，表示所有节点都已访问完毕，循环结束。

==77.用邻接表实现广度优先搜索算法==

图的邻接表的数据结构:
// 定义图的邻接表节点
typedef struct ArcNode {
   
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode* nextarc; // 指向下一个邻接点
} ArcNode;

// 定义图的邻接表
typedef struct VNode {
   
    ArcNode* firstarc; // 指向第一个邻接点
} VNode;

typedef struct ALGraph {
   
    VNode vertices[Max_num]; // 图的顶点数组
    int vexnum; // 图的顶点数
    int edgenum; // 图的边数
} ALGraph;

常用: 遍历时初始化:ArcNode（*） p = q->vertices[v].firstarc 对第一个邻接点操作：w = p->adjvex 下一个:p = p->nextarc 图的大小：G->vexnum

分析：BFStraverse(ALGraph* q) 函数：此函数遍历整个图。它使用一个布尔数组 visit 来跟踪已访问的顶点。它迭代所有顶点，如果一个顶点未被访问，则调用 BFS 函数对其进行 BFS 遍历。这确保了即使图是不连通的，所有顶点都会被访问。

BFS(ALGraph q, int i, bool visit[], Queue Q) 函数：这是核心 BFS 函数。它接收图 q，起始顶点 i，访问数组 visit 和队列 Q 作为输入。它首先标记起始顶点 i 为已访问，并将其入队。然后，它进入一个 while 循环，只要队列不为空就继续循环。在每次迭代中，它从队列中出队一个顶点 v。接下来，它遍历 v 的所有邻接顶点。对于每个邻接顶点 w，如果 w 未被访问，则将其标记为已访问并入队。

==78.用邻接矩阵实现广度优先搜索算法==

图的邻接矩阵的数据结构:
typedef struct {
   
    int edge[Max_num][Max_num]; // 邻接矩阵
    int vexnum; // 图的顶点数
    int edgenum; // 图的边数
} AMGraph;

常用: 值：G->edge[v][j] 1有边0无边 图的大小：G->vexnum

分析：BFS(ALGraph* G, int i, bool visit[]) 函数: 该函数接受一个图 G（用邻接矩阵表示）、起始节点 i 和一个布尔数组 visit（用于跟踪已访问的节点）作为输入。队列操作: 代码使用一个队列 Q 来管理待访问的节点。InitQueue(&Q) 初始化队列，Enqueue(&Q, i) 将起始节点入队，Dequeue(&Q, &v) 将队首元素出队并赋值给 v，IsEmpty(&Q) 检查队列是否为空。节点访问和标记: visit[i] = true 将起始节点标记为已访问，printf("%d ", v) 打印访问的节点。邻接矩阵遍历: for (int j = 0; j < G->vexnum; j++) 循环遍历邻接矩阵的每一行，检查与当前节点 v 是否有边相连 (G->edge[v][j] == 1) 且该节点 j 是否未被访问 (!visit[j])。如果是，则将节点 j 标记为已访问并入队。循环: while (!IsEmpty(&Q)) 循环持续直到队列为空，表示所有可达节点都已访问。

==79.用邻接表实现深度优先搜索算法==
DFStraverse 函数:

这个函数是 DFS 遍历的入口函数。它首先初始化一个布尔数组 visit，用于标记每个顶点是否已被访问。然后，它遍历所有顶点，如果一个顶点未被访问，则调用 DFS 函数从该顶点开始进行深度优先搜索。

DFS 函数:这是递归实现的深度优先搜索的核心函数。它接收图指针 q，当前顶点序号 i 和访问数组 visit 作为参数。visit[i] = true;：标记当前顶点 i 为已访问。for (ArcNode* p = q->vertices[i].firstarc; p; p = p->nextarc)：遍历当前顶点 i 的所有邻接顶点。int j = p->adjvex;：获取邻接顶点的序号 j。if (!visit[j]) { DFS(q, j, visit); }：如果邻接顶点 j 未被访问，则递归调用 DFS 函数，从 j 开始继续搜索。

==80.用邻接矩阵实现深度优先搜索算法==
分析：标记已访问: 将 visit[i] 设置为 true，表示顶点 i 已被访问。打印顶点: 打印当前顶点 i 的值。遍历邻接节点: 循环遍历邻接矩阵的第 i 行 (G->edge[i])，检查与当前顶点 i 相连的每个顶点 j。递归调用: 如果顶点 j 未被访问 (!visit[j]) 且存在一条从 i 到 j 的边 (G->edge[i][j] == 1)，则递归调用 DFS 函数，继续访问顶点 j。

代码实现

#include<stdio.h>
#define Max_num 20
int main(){
   
//    76.二叉树的层次遍历算法
void LevelOrderTraversal(Bitree T) {
   
    Queue Q;    //创建队列
    InitQueue(&Q);    // 初始化队列
    Enqueue(&Q, T); // 根节点入队
    Bitnode* p; // 接收出队元素
    while (!IsEmpty(&Q)) {
   
        Dequeue(&Q, &p);
        visit(p);    //访问节点p，即输出 
        if (p->lchild != NULL) {
   
            Enqueue(&Q, p->lchild);        //如果左子节点存在，将其入队。
        }
        if (p->rchild != NULL) {
   
            Enqueue(&Q, p->rchild);
        }
    }
}


//    77.用邻接表实现广度优先搜索算法
void BFStraverse(ALGraph* q) {
   
    bool visit[Max_num] = {
   false};    // 初始化访问数组，记录每个节点是否被访问过。
    Queue Q;    //创建 队列
    InitQueue(&Q);    // 初始化队列
    for (int i = 0; i < q->vexnum; i++) {
   
        if (!visit[i]) {
       //如果节点未被访问，则调用BFS函数。 
            BFS(q, i, visit, &Q);
        }
    }
}
void BFS(ALGraph* q, int i, bool visit[], Queue* Q) {
   
    visit[i] = true;    //标记当前节点为已访问。
    Enqueue(Q, i);    //将当前节点入队
    while (!IsEmpty(Q)) {
    // 队列非空
        int v;
        Dequeue(Q, &v);
        for (ArcNode* p = q->vertices[v].firstarc; p; p = p->nextarc) {
       //遍历与节点v相邻的所有节点。
            int w = p->adjvex;
            if (!visit[w]) {
   
                visit[w] = true;
                Enqueue(Q, w);
            }
        }
    }
}

// 78. 用邻接矩阵实现广度优先搜索算法
void BFS(ALGraph* G, int i, bool visit[]) {
   
    Queue Q; // 创建队列
    InitQueue(&Q); // 初始化队列
    visit[i] = true; // 标记当前节点为已访问
    Enqueue(&Q, i); // 当前节点入队

    while (!IsEmpty(&Q)) {
    // 队列非空
        int v;
        Dequeue(&Q, &v); // 出队
        printf("%d ", v); // 访问节点

        for (int j = 0; j < G->vexnum; j++) {
    // 遍历邻接矩阵
            if (!visit[j] && G->edge[v][j] == 1) {
    // 如果未访问且有边
                visit[j] = true; // 标记为已访问
                Enqueue(&Q, j); // 入队
            }
        }
    }
}

//    79.用邻接表实现深度优先搜索算法
void DFStraverse(ALGraph* q) {
   
    bool visit[Max_num] = {
   false}; // 初始化访问数组
    for (int i = 0; i < q->vexnum; i++) {
   
        if (!visit[i]) {
   
            DFS(q, i, visit);
        }
    }
}

void DFS(ALGraph* q, int i, bool visit[]) {
   
    visit[i] = true;
    for (ArcNode* p = q->vertices[i].firstarc; p; p = p->nextarc) {
   
        int j = p->adjvex;
        if (!visit[j]) {
   
            DFS(q, j, visit);
        }
    }
}    

//    80.用邻接矩阵实现深度优先搜索算法
void DFS(ALGraph* G, int i, bool visit[]) {
   
    visit[i] = true; // 标记当前节点为已访问
    printf("%d ", i); // 访问节点

    for (int j = 0; j < G->vexnum; j++) {
    // 遍历邻接矩阵
        if (!visit[j] && G->edge[i][j] == 1) {
    // 如果未访问且有边
            DFS(G, j, visit); // 递归访问
        }
    }
}     

    return 0;
}

总结

本文介绍了五种图论算法的C语言实现，包括二叉树的层次遍历、广度优先搜索（BFS）和深度优先搜索（DFS）算法的邻接表和邻接矩阵两种实现方式。这些算法是数据结构和算法学习中的重要内容，也是解决图相关问题的基础工具。

二叉树的层次遍历算法通过使用队列来实现，它按照从上到下、从左到右的顺序依次访问二叉树的每个节点。层次遍历是二叉树遍历中的一种，它对于树的可视化、打印和某些特定问题的解决非常有用。

广度优先搜索（BFS）算法是一种基于队列的图遍历算法，它从源节点开始，逐层遍历图中的节点。BFS可以用于寻找最短路径、连通分量的识别以及某些优化问题。本文提供了BFS的两种实现方式：邻接表和邻接矩阵，分别适用于不同场景下的图遍历。

深度优先搜索（DFS）算法是一种基于递归或栈的图遍历算法，它从源节点开始，尽可能深地搜索图的分支。DFS可以用于拓扑排序、路径寻找和解决某些递归问题。同样，本文也提供了DFS的两种实现方式，展示了如何使用邻接表和邻接矩阵来实现深度优先搜索。

这些算法的实现不仅展示了C语言在处理图结构时的能力，也体现了算法设计的基本思想，如递归、栈和队列的使用。通过这些算法的学习，我们可以更好地理解图的结构特性，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对图论算法的理解。通过这些问题的解决，我们可以逐步提高自己的算法设计和实现能力，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。