【C 数据结构】深度优先搜索、广度优先搜索

文章目录

  • 【 1. DFS 深度优先搜索 】
    • 1.1 基本原理
    • 1.2 C 实现
  • 【 2. BFS 广度优先搜索 】
    • 2.1 基本原理
    • 2.2 C 实现
  • 【 3. 深度优先生成树、广度优先生成树 】
  • 【 4. 深度优先生成森林、广度优先生成森林 】
    • 4.1 深度优先生成森林
    • 4.2 广度优先生成森林

  • 对存储的图中的顶点进行遍历搜索，常用的遍历方式有两种：深度优先搜索和广度优先搜索。

【 1. DFS 深度优先搜索 】

1.1 基本原理

  • 深度优先搜索的过程 类似于树的先序遍历，首先从例子中体会深度优先搜索。例如下图是一个无向图，采用深度优先算法遍历这个图的过程为：
    • 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；
    • 然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；
    • 当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有V5 的邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ，V1 ；
    • 通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3 邻接点 V6 ，然后 V7 ；
    • 由于 V7 没有未被访问的邻接点，所以回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；
    • 最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。
    • 根据上边的过程，可以得到下图通过深度优先搜索获得的顶点的遍历次序为：
      V1、V2、V4、V8、 V5、V3、V6、V7
      在这里插入图片描述
  • 总结：深度优先搜索，是从图中的一个顶点出发，每次遍历当前访问顶点的临接点，一直到访问的顶点没有未被访问过的临接点为止。然后采用依次回退的方式（深度优先搜索是一个不断回溯的过程），查看来的路上每一个顶点是否有其它未被访问的临接点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。

1.2 C 实现

  • 深度优先搜索算法遍历图的实现代码为：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#define MAX_VERtEX_NUM 20         //顶点的最大个数
#define VertexType int            //顶点的数据类型
#define VRType int                //顶点之间的关系的变量类型
#define InfoType char             //存储弧或边额外信息的指针变量类型
bool visited[MAX_VERtEX_NUM];     //设置全局数组，记录标记顶点是否被访问过

//边的信息结构体
typedef struct {
    VRType adj;         //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType* info;     //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

//图结构体
typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];   //一维数据数组
    AdjMatrix  arcs;                   //二维关系数组，即邻接矩阵
    int vexnum, arcnum;                //图的顶点数和弧（边）数
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph* G, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for (; i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i > G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

//构造无向图
void CreateDN(MGraph* G) {
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d", &v1, &v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
    }
}

//返回第一个与顶点v有边的顶点的下标
int FirstAdjVex(MGraph G, int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

//返回从第w+1个位置开始，与顶点v有边的顶点的下标
int NextAdjVex(MGraph G, int v, int w)
{
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for (int i = w + 1; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

//打印输出顶点v的值
void visitVex(MGraph G, int v) {
    printf("%d ", G.vexs[v]);
}

//深度优先搜索核心函数
void DFS(MGraph G, int v) {
    visited[v] = true;//标记为true，表示这个顶点已被处理
    visitVex(G, v);   //输出第v个顶点
    //从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数
    for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
        //如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数
        if (!visited[w]){
            DFS(G, w);
        }
    }
}

//对图进行深度优先搜索
void DFSTraverse(MGraph G) 
{
    int v;
    //初始化为visit标记数组false
    for (v = 0; v < G.vexnum; ++v) {
        visited[v] = false;
    }
    //对于每个标记为false的顶点调用深度优先搜索函数
    for (v = 0; v < G.vexnum; v++) {
        //如果该顶点的标记位为false，则调用深度优先搜索函数
        if (!visited[v]) {
            DFS(G, v);
        }
    }
}

int main() {
    MGraph G; //建立一个图的对象
    CreateDN(&G);   //初始化图
    DFSTraverse(G); //深度优先搜索图
    return 0;
}
  • 使用上述程序存储下图的无向图时，输入如下数据，得到DFS的输出结果：
    在这里插入图片描述
//输入如下数据：
8,9
1
2
3
4
5
6
7
8
1,2
2,4
2,5
4,8
5,8
1,3
3,6
6,7
7,3

在这里插入图片描述

【 2. BFS 广度优先搜索 】

2.1 基本原理

  • 广度优先搜索 类似于树的层次遍历。以下图的无向图为例，假设 V1 作为起始点，遍历其所有的邻接点 V2 和 V3 ，以 V2 为起始点，访问邻接点 V4 和 V5 ，以 V3 为起始点，访问邻接点 V6 、 V7 ，以 V4 为起始点访问 V8 ，以 V5 为起始点，由于 V5 所有的起始点已经全部被访问，所有直接略过， V6 和 V7 也是如此。
    以 V1 为起始点的遍历过程结束后，判断图中是否还有未被访问的点，由于图 1 中没有了，所以整个图遍历结束。遍历顶点的顺序为：
    V1、 V2、 v3、V4、 V5、 V6、 V7、 V8
    在这里插入图片描述
  • 总结：广度优先搜索，是从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。

2.2 C 实现

  • 广度优先搜索的实现需要借助 队列 这一特殊数据结构，实现代码为：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20         //顶点的最大个数
#define VertexType int            //顶点的数据类型
#define VRType int                //顶点之间的关系的变量类型
#define InfoType char             //存储弧或边额外信息的指针变量类型
bool visited[MAX_VERtEX_NUM];     //设置全局数组，记录标记顶点是否被访问过

//队列
typedef struct Queue {
    VertexType data;
    struct Queue* next;
}Queue;

//边的信息结构体
typedef struct {
    VRType adj;         //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType* info;     //弧或边额外含有的信息指针
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

//图结构体
typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];   //一维数据数组
    AdjMatrix  arcs;                   //二维关系数组，即邻接矩阵
    int vexnum, arcnum;                //图的顶点数和弧（边）数
}MGraph;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph* G, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for (; i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i > G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

//构造无向图
void CreateDN(MGraph* G) {
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d", &v1, &v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
    }
}

//返回第一个与顶点v有边的顶点的下标
int FirstAdjVex(MGraph G, int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

//返回从第w+1个位置开始，与顶点v有边的顶点的下标
int NextAdjVex(MGraph G, int v, int w)
{
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for (int i = w + 1; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

//打印输出顶点v的值
void visitVex(MGraph G, int v) {
    printf("%d ", G.vexs[v]);
}

//初始化队列
void InitQueue(Queue** Q) {
    (*Q) = (Queue*)malloc(sizeof(Queue));
    (*Q)->next = NULL;
}

//顶点元素v进队列
void EnQueue(Queue** Q, VertexType v) {
    Queue* element = (Queue*)malloc(sizeof(Queue));
    element->data = v;
    element->next = NULL;
    Queue* temp = (*Q);
    while (temp->next != NULL){
        temp = temp->next;
    }
    temp->next = element;
}

//队头元素出队列，队列新的队头元素值赋给u
void DeQueue(Queue** Q, int* u) {
    (*u) = (*Q)->next->data;
    (*Q)->next = (*Q)->next->next;
}

//判断队列是否为空
bool QueueEmpty(Queue* Q) {
    if (Q->next == NULL) {
        return true;
    }
    return false;
}
//广度优先搜索
void BFSTraverse(MGraph G) {
    int v;
    //将用做标记的visit数组初始化为false
    for (v = 0; v < G.vexnum; ++v) {
        visited[v] = false;
    }
    //对于每个标记为false的顶点调用深度优先搜索函数
    Queue* Q;  //创建1个队列指针Q
    InitQueue(&Q);
    for (v = 0; v < G.vexnum; v++) {    // [对每个顶点v循环]
        if (!visited[v]) {
            visited[v] = true;      //标记为true，表示这个顶点已被处理
            visitVex(G,v);          //输出第v个顶点
            EnQueue(&Q, G.vexs[v]); //将第v个顶点入队
            while (!QueueEmpty(Q)) {    // [判断队列是否为空]
                int u;
                DeQueue(&Q, &u);      //出队，并将新的队头的值赋值给u
                u = LocateVex(&G, u); //新的队头的值对应的下标
                for (int w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G, u, w)) { //将队头u的所有临接点遍历，并入队
                    if (!visited[w]) {
                        visited[w] = true;
                        visitVex(G, w);
                        EnQueue(&Q, G.vexs[w]);
                    }
                }
            }
        }
    }
}

int main() {
    MGraph G;      //建立一个图的对象
    CreateDN(&G);  //初始化图
    BFSTraverse(G);//广度优先搜索图
    return 0;
}
  • 使用上述程序存储下图的无向图时，输入如下数据，得到DFS的输出结果：
    在这里插入图片描述
//输入数据如下：
8,9
1
2
3
4
5
6
7
8
1,2
2,4
2,5
4,8
5,8
1,3
3,6
6,7
7,3

在这里插入图片描述

【 3. 深度优先生成树、广度优先生成树 】

  • 无向图遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林。
    在这里插入图片描述
  • 由深度优先搜索得到的树为 深度优先生成树。例如，当对上图的无向图使用深度优先搜索算法时，假设 V1 作为遍历的起始点，涉及到的顶点和边的遍历顺序为（不唯一）：
    V1、V2、V4、V8、V5、V3、V6、V7。
    此种遍历顺序构建的生成树为：
    在这里插入图片描述
  • 同理，广度优先搜索生成的树为 广度优先生成树，对该无向图以顶点 V1 为起始点进行广度优先搜索遍历得到的树，如下图所示：
    在这里插入图片描述

【 4. 深度优先生成森林、广度优先生成森林 】

  • 前言回顾：详情见：【C 数据结构】图。
    ① 非连通图在进行遍历时，实则是对非连通图中每个连通分量分别进行遍历，在遍历过程经过的每个顶点和边，就构成了每个连通分量的生成树；
    ② 非连通图的多个连通分量构成的多个生成树为非连通图的生成森林。

4.1 深度优先生成森林

  • 对下图 a 的非连通图采用深度优先搜索算法遍历时，得到的深度优先生成森林（由 3 个深度优先生成树构成）如下图 b 所示（不唯一）。

在这里插入图片描述

  • C 实现：
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20         //顶点的最大个数
#define VertexType int            //顶点的数据类型
#define VRType int                //顶点之间的关系的变量类型
bool visited[MAX_VERtEX_NUM];     //设置全局数组，记录标记顶点是否被访问过

//边的信息结构体
typedef struct 
{
    VRType adj;     //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
}ArcCell, AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

//图结构体
typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];   //一维数据数组
    AdjMatrix  arcs;                   //二维关系数组，即邻接矩阵
    int vexnum, arcnum;                //图的顶点数和弧（边）数
}MGraph;

//孩子兄弟表示法的链表结点结构
typedef struct CSNode {
    VertexType data;
    struct CSNode* lchild;//孩子结点
    struct CSNode* nextsibling;//兄弟结点
}*CSTree, CSNode;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph G, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for (; i < G.vexnum; i++) {
        if (G.vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i > G.vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造无向图
void CreateDN(MGraph* G) {
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    getchar();
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vexs[i]));
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        scanf("%d,%d", &v1, &v2);
        int n = LocateVex(*G, v1);
        int m = LocateVex(*G, v2);
        if (m == -1 || n == -1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;//无向图的二阶矩阵沿主对角线对称
    }
}

//返回第一个与顶点v有边的顶点的下标
int FirstAdjVex(MGraph G, int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

//返回从第w+1个位置开始，与顶点v有边的顶点的下标
int NextAdjVex(MGraph G, int v, int w)
{
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for (int i = w + 1; i < G.vexnum; i++) {
        if (G.arcs[v][i].adj) {
            return i;
        }
    }
    return -1;
}

void DFSTree(MGraph G, int v, CSTree* T) {
    //将正在访问的该顶点的标志位设为true
    visited[v] = true;
    bool first = true;
    CSTree q   = NULL;
    //依次遍历该顶点的所有邻接点
    for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
        //如果该临界点标志位为false，说明还未访问
        if (!visited[w]) {
            //为该邻接点初始化为结点
            CSTree p = (CSTree)malloc(sizeof(CSNode));
            p->data = G.vexs[w];
            p->lchild = NULL;
            p->nextsibling = NULL;
            //该结点的第一个邻接点作为孩子结点，其它邻接点作为孩子结点的兄弟结点
            if (first) {
                (*T)->lchild = p;
                first = false;
            }
            //否则，为兄弟结点
            else {
                q->nextsibling = p;
            }
            q = p;
            //以当前访问的顶点为树根，继续访问其邻接点
            DFSTree(G, w, &q);
        }
    }
}

//深度优先搜索生成森林并转化为二叉树
void DFSForest(MGraph G, CSTree* T) {
    (*T) = NULL;
    //每个顶点的标记为初始化为false
    for (int v = 0; v < G.vexnum; v++) {
        visited[v] = false;
    }
    CSTree q = NULL;
    //遍历每个顶点作为初始点，建立深度优先生成树
    for (int v = 0; v < G.vexnum; v++) {
        //如果该顶点的标记位为false，证明未访问过
        if (!(visited[v])) {
            //新建一个结点，表示该顶点
            CSTree p = (CSTree)malloc(sizeof(CSNode));
            p->data = G.vexs[v];
            p->lchild = NULL;
            p->nextsibling = NULL;
            //如果树未空，则该顶点作为树的树根
            if (!(*T)) {
                (*T) = p;

            }
            //该顶点作为树根的兄弟结点
            else {
                q->nextsibling = p;
            }
            //每次都要把q指针指向新的结点，为下次添加结点做铺垫
            q = p;
            //以该结点为起始点，构建深度优先生成树
            DFSTree(G, v, &p);
        }
    }
}

//前序遍历二叉树
void PreOrderTraverse(CSTree T) {
    if (T) {
        printf("%d ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->nextsibling);
    }
    return;
}

int main() {
    MGraph G;    //建立一个图的对象
    CreateDN(&G);//初始化图
    CSTree T;
    DFSForest(G, &T);
    PreOrderTraverse(T);
    return 0;
}
  • 使用上述程序存储下图的无向图，输入如下数据，构建深度优先生成森林，得到DFS的输出结果：
    在这里插入图片描述
  • 构建的深度优先生成森林用孩子兄弟表示法如下所示：3 种颜色的树各代表一棵深度优先生成树，使用孩子兄弟表示法表示，也就是将三棵树的树根相连，第一棵树的树根作为整棵树的树根。
    在这里插入图片描述
//输入数据如下所示：
13,13
1
2
3
4
5
6
7
8
9
10
11
12
13
1,2
1,3
1,6
1,12
2,13
4,5
7,8
7,10
7,9
8,10
11,12
11,13
12,13

在这里插入图片描述

4.2 广度优先生成森林

  • 非连通图采用广度优先搜索算法进行遍历时，经过的顶点以及边的集合为该图的 广度优先生成森林 。
  • C 实现：
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define InfoType char                       //存储弧或者边额外信息的指针变量类型
#define VertexType int                      //图中顶点的数据类型
typedef enum{false,true}bool;               //定义bool型常量
bool visited[MAX_VERtEX_NUM];               //设置全局数组，记录标记顶点是否被访问过
typedef struct {
    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType * info;                        //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
}MGraph;

typedef struct CSNode{
    VertexType data;
    struct CSNode * lchild;//孩子结点
    struct CSNode * nextsibling;//兄弟结点
}*CSTree,CSNode;

typedef struct Queue{
    CSTree data;//队列中存放的为树结点
    struct Queue * next;
}Queue;

//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,VertexType v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; i<G->vexnum; i++) {
        if (G->vexs[i]==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i>G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造无向图
void CreateDN(MGraph *G){
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j].adj=0;
            G->arcs[i][j].info=NULL;
        }
    }
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        int n=LocateVex(G, v1);
        int m=LocateVex(G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj=1;
        G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
    }
}

int FirstAdjVex(MGraph G,int v)
{
    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i<G.vexnum; i++){
        if( G.arcs[v][i].adj ){
            return i;
        }
    }
    return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for(int i = w+1; i<G.vexnum; i++){
        if(G.arcs[v][i].adj){
            return i;
        }
    }
    return -1;
}

//初始化队列
void InitQueue(Queue ** Q){
    (*Q)=(Queue*)malloc(sizeof(Queue));
    (*Q)->next=NULL;
}
//结点v进队列
void EnQueue(Queue **Q,CSTree T){
    Queue * element=(Queue*)malloc(sizeof(Queue));
    element->data=T;
    element->next=NULL;
   
    Queue * temp=(*Q);
    while (temp->next!=NULL) {
        temp=temp->next;
    }
    temp->next=element;
}
//队头元素出队列
void DeQueue(Queue **Q,CSTree *u){
    (*u)=(*Q)->next->data;
    (*Q)->next=(*Q)->next->next;
}
//判断队列是否为空
bool QueueEmpty(Queue *Q){
    if (Q->next==NULL) {
        return true;
    }
    return false;
}

void BFSTree(MGraph G,int v,CSTree*T){
    CSTree q=NULL;
    Queue * Q;
    InitQueue(&Q);
    //根结点入队
    EnQueue(&Q, (*T));
    //当队列为空时，证明遍历完成
    while (!QueueEmpty(Q)) {
        bool first=true;
        //队列首个结点出队
        DeQueue(&Q,&q);
        //判断结点中的数据在数组中的具体位置
        int v=LocateVex(&G,q->data);
        //已经访问过的更改其标志位
        visited[v]=true;
        //遍历以出队结点为起始点的所有邻接点
        for (int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v, w)) {
            //标志位为false，证明未遍历过
            if (!visited[w]) {
                //新建一个结点 p，存放当前遍历的顶点
                CSTree p=(CSTree)malloc(sizeof(CSNode));
                p->data=G.vexs[w];
                p->lchild=NULL;
                p->nextsibling=NULL;
                //当前结点入队
                EnQueue(&Q, p);
                //更改标志位
                visited[w]=true;
                //如果是出队顶点的第一个邻接点，设置p结点为其左孩子
                if (first) {
                    q->lchild=p;
                    first=false;
                }
                //否则设置其为兄弟结点
                else{
                    q->nextsibling=p;
                }
                q=p;
            }
        }
    }
}
//广度优先搜索生成森林并转化为二叉树
void BFSForest(MGraph G,CSTree *T){
    (*T)=NULL;
    //每个顶点的标记为初始化为false
    for (int v=0; v<G.vexnum; v++) {
        visited[v]=false;
    }
    CSTree q=NULL;
    //遍历图中所有的顶点
    for (int v=0; v<G.vexnum; v++) {
        //如果该顶点的标记位为false，证明未访问过
        if (!(visited[v])) {
            //新建一个结点，表示该顶点
            CSTree p=(CSTree)malloc(sizeof(CSNode));
            p->data=G.vexs[v];
            p->lchild=NULL;
            p->nextsibling=NULL;
            //如果树未空，则该顶点作为树的树根
            if (!(*T)) {
                (*T)=p;
            }
            //该顶点作为树根的兄弟结点
            else{
                q->nextsibling=p;
            }
            //每次都要把q指针指向新的结点，为下次添加结点做铺垫
            q=p;
            //以该结点为起始点，构建广度优先生成树
            BFSTree(G,v,&p);
        }
    }
}
//前序遍历二叉树
void PreOrderTraverse(CSTree T){
    if (T) {
        printf("%d ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->nextsibling);
    }
    return;
}
int main() {
    MGraph G;//建立一个图的变量
    CreateDN(&G);//初始化图
    CSTree T;
    BFSForest(G, &T);
    PreOrderTraverse(T);
    return 0;
}
  • 使用上述程序存储下图的无向图，输入如下数据，构建广度优先生成森林，得到BFS的输出结果：
    在这里插入图片描述
  • 对上图通过广度优先搜索得到的广度优先生成森林用孩子兄弟表示法如下图所示：
    在这里插入图片描述
//输入如下数据：
13,13
1
2
3
4
5
6
7
8
9
10
11
12
13
1,2
1,3
1,6
1,12
2,13
4,5
7,8
7,10
7,9
8,10
11,12
11,13
12,13

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/584149.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【信号与系统杂谈 - 1】为什么拉普拉斯变换有收敛域而傅里叶变换没有

【信号与系统杂谈 - 1】为什么拉普拉斯变换有收敛域而傅里叶变换没有

这个问题是我在推导傅里叶变换的时移特性公式和拉普拉斯变换的延时特性公式时发现的&#xff08;即拉氏变换总是需要考虑收敛域的原因&#xff09; 援引知乎上的回答解释
阅读更多...
12_Scala_package

12_Scala_package

文章目录 Scaal面向对象编程1.回顾Java2.package可以多次声明3.设置作用域&#xff0c;设置上下级4.包可以当作对象使用5.import6.Scala用_取代Java *7.导入多个包8.屏蔽类9.类起别名10.import的规则11.有些包无需导入 Scaal面向对象编程 Scala是一门完全面向对象语言&#xf…
阅读更多...
C# winform 漂亮的日期时间控件

C# winform 漂亮的日期时间控件

源代码下载&#xff1a; https://download.csdn.net/download/gaoxiang19820514/89242240 效果图 在 HZH-Controls控件 基础上修改的日期控件 因为HZH_Controls控件 中的日期控件太大了&#xff0c; 我的程序中需要多个日期时间的控件放不下&#xff0c;主题是绿色的&#…
阅读更多...
Springboot+Vue项目-基于Java+MySQL的校园疫情防控系统(附源码+演示视频+LW)

Springboot+Vue项目-基于Java+MySQL的校园疫情防控系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…
阅读更多...
力扣刷题Day2

力扣刷题Day2

题目链接&#xff1a; 24. 两两交换链表中的节点 - 力扣&#xff08;LeetCode&#xff09; 效果&#xff1a; 解题思路&#xff1a; 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 注意不可以只是单纯的改变节点内部的值&#xff0c;而…
阅读更多...
Docker--compose概述与部署

Docker--compose概述与部署

目录 一、概述 1. Compose简介 1.1 docker compose常用命令 1.2 Compose配置常用字段 2. YAML简介 2.1 YAML支持的数据结构 2.2 YML文件编写注意事项 2.3 Docker Compose文件结构 3. Docker-Compose安装 ​编辑 4.docker Compose撰写nginx 镜像 1. 准备环境 ​编辑…
阅读更多...
苹果和OpenAI再续前缘，iOS 18会是颠覆级的吗？｜TodayAI

苹果和OpenAI再续前缘，iOS 18会是颠覆级的吗？｜TodayAI

据彭博社最新报道&#xff0c;苹果公司已经与人工智能领域的先锋企业OpenAI重启了对话&#xff0c;双方目前正在讨论一项可能的合作&#xff0c;以将OpenAI的生成式人工智能技术整合到苹果即将推出的iOS 18操作系统中。这一举措表明&#xff0c;苹果正加速其在人工智能技术上的…
阅读更多...
【EI会议|稳定检索】2024年传感技术与图像处理国际会议(ICSTIP 2024)

【EI会议|稳定检索】2024年传感技术与图像处理国际会议(ICSTIP 2024)

2024 International Conference on Sensing Technology and Image Processing 一、大会信息 会议名称&#xff1a;2024年传感技术与图像处理国际会议会议简称&#xff1a;ICSTIP 2024收录检索&#xff1a;提交Ei Compendex,CPCI,CNKI,Google Scholar等会议官网&#xff1a;htt…
阅读更多...
final原理

final原理

文章目录 1. 设置 final 变量的原理2. 获取 final 变量的原理 1. 设置 final 变量的原理 理解了 volatile 原理&#xff0c;再对比 final 的实现就比较简单了 public class TestFinal {final int a 20; }字节码 0: aload_0 1: invokespecial #1 // Method java/lang/Object…
阅读更多...
数组 Leetcode 704 二分查找/Leetcode 59 螺旋矩阵/Leetcode 203移除链表元素

数组 Leetcode 704 二分查找/Leetcode 59 螺旋矩阵/Leetcode 203移除链表元素

数组 Leetcode 704 二分查找 Leetcode 704 学习记录自代码随想录 二分法模板记忆&#xff0c;数值分析中牛顿迭代法 class Solution { public:int search(vector<int>& nums, int target) {int left 0, right nums.size()-1;// 是否需要等于号&#xff0c;假设…
阅读更多...
SpringCloud之OpenFeign

SpringCloud之OpenFeign

学习笔记&#xff1a; 官网地址&#xff1a;https://docs.spring.io/spring-cloud-openfeign/docs/current/reference/html/#spring-cloud-feign 源码&#xff1a;https://github.com/spring-cloud/spring-cloud-openfeign 1、概念总结 OpenFeign是一个声明式的Web服务客户端…
阅读更多...
MySql-日期分组

MySql-日期分组

一、分别统计各时间各类型数据条数 数据库的 request_time字段 数据类型&#xff1a;timestamp 默认值&#xff1a;CURRENT_TIMESTAMP 例子&#xff1a; 2024-01-26 08:25:48 原数据&#xff1a; 1、将数据按照日期&#xff08;年月日&#xff09;形式输出 按照request_…
阅读更多...
【人工智能基础】聚类实验分析

【人工智能基础】聚类实验分析

实验环境&#xff1a;anaconda、jupyter notebook、spyder 实现用到的类库&#xff1a;numpy、matplotlib、scikit-learn k均值聚类&#xff08;K-MEANS&#xff09; k均值聚类的原理&#xff1a; 选定k个聚类中心把数据集中距离聚类中心i最近的点都归属到一个簇根据每个簇中…
阅读更多...
debian配置四叶草输入法

debian配置四叶草输入法

效果展示 一、前言 在linux下体验比较好的输入法只有两款&#xff1a;搜狗输入法、四叶草输入法。 ubuntu下可以成功配置搜狗输入法&#xff0c;但debian下从来没有成功过。 今天在用fcitx5 四叶草时发现VNC远程输入法会失灵&#xff0c;于是改用了ibus 四叶草&#xff0c…
阅读更多...
C# wpf 运行时替换方法实现mvvm自动触发刷新

C# wpf 运行时替换方法实现mvvm自动触发刷新

文章目录 前言一、如何实现&#xff1f;1、反射获取属性2、定义替换方法3、交换属性的setter方法 二、完整代码1、接口2、项目 三、使用示例1、倒计时&#xff08;1&#xff09;、继承ViewModelBase&#xff08;2&#xff09;、定义属性&#xff08;3&#xff09;、属性赋值&am…
阅读更多...
小程序地理位置接口怎么开通？

小程序地理位置接口怎么开通？

小程序地理位置接口有什么功能&#xff1f; 如果我们提审后驳回理由写了“当前提审小程序代码包中地理位置相关接口( chooseAddress、getLocation )暂未开通&#xff0c;建议完成接口开通后或移除接口相关内容后再进行后续版本提审”&#xff0c;如果你也碰到类似问题&#xf…
阅读更多...
C#基础之冒泡排序

C#基础之冒泡排序

排序初探 文章目录 冒泡排序1、概念2、冒泡排序的基本原理3、代码实现思考1 随机数冒泡排序思考2 函数实现排序 冒泡排序 1、概念 将一组无序的记录序列调整为有序的记录序列&#xff08;升、降序&#xff09; 2、冒泡排序的基本原理 两两相邻&#xff0c;不停比较&#x…
阅读更多...
mySQL商城项目实战 （终）（全部表）（1-88张）

mySQL商城项目实战 （终）（全部表）（1-88张）

本章无sql语句&#xff0c;直接放转出的sql文件。 88张表结果如图! 资源在已经与文章绑定&#xff0c; 在navicat工具中&#xff0c;执行以下步骤 在新建的数据库中右键,点击【运行sql文件】&#xff0c;运行绑定的资源&#xff0c;之后您就可以在您的navicat中看到我建好的8…
阅读更多...
OpenLayers入门①（引入的是一个高德地图）

OpenLayers入门①（引入的是一个高德地图）

OpenLayers入门&#xff08;一&#xff09; - 知乎 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport&qu…
阅读更多...
使用 LooperPrinter 监控 Android 应用的卡顿

使用 LooperPrinter 监控 Android 应用的卡顿

在 Android 开发中&#xff0c;主线程&#xff08;UI线程&#xff09;的卡顿直接影响用户体验。LooperPrinter 是一种有效的工具&#xff0c;可以帮助我们监测和识别这些卡顿。下面是如何实现 LooperPrinter 监控的详细步骤和相应的 Kotlin 代码示例。 步骤 1: 创建自定义的 P…
阅读更多...
最新文章

Copyright @ 2022~2023