算法:图的广度优先遍历(Breadth First Search)

图的遍历和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traverse Graph)。

图的遍历方法一般有两种,第一种是我们在前面讲过的《深度优先遍历(Depth First Search)》,也有称为深度优先搜索,简称为DFS。第二种是广度优先遍历(Breadth  First Search),也有称为广度优先搜索,简称为BFS。我们在《队列与广度优先搜索》中已经较为详细地讲述了广度优先搜索的策略,这里不再赘述。如果说图的深度优先遍历类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历了,我们把图7-5-3的第一幅图稍微变形成第二幅图所示,这样层次感就更强了,广度优先遍历需要用到队列的操作,可以参考《队列的顺序存储结构》。

下面只给出邻接矩阵和邻接表存储方式时的图的广度优先遍历的算法代码,没有给出整体可供测试运行的代码,其实只需要再写一个创建图的函数就可以进行整体测试了,可以参考《邻接矩阵创建图》和《邻接表创建图

一、如果我们使用的是邻接矩阵的方式,则代码如下:(改编自《大话数据结构》)

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9

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

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
    int i, j;
    Queue Q;
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = false;
    InitQueue(&Q);/* 初始化一辅助用的队列 */

    for (i = 0; i < G.numVertexes; i++)/* 对每一个顶点做循环 */
    {
        if (!visited[i])/* 若是未访问过就处理 */
        {
            visited[i] = true;/* 设置当前顶点访问过 */
            cout << G.vexs[i] << ' '; /* 打印顶点,也可以其它操作 */
            EnQueue(&Q, i);/* 将此顶点入队列 */
            while (!QueueEmpty(Q))/* 若当前队列不为空 */
            {
                DeQueue(&Q, &i);/* 将队对元素出队列,赋值给i */
                for (j = 0 ; j < G.numVertexes; j++)
                {
                    /* 判断其它顶点若与当前顶点存在边且未访问过  */
                    if (G.arc[i][j] == 1 && !visited[j])
                    {
                        visited[j] = true;/* 将找到的此顶点标记为已访问 */
                        cout << G.vexs[j] << ' '; /* 打印顶点 */
                        EnQueue(&Q, j);/* 将找到的此顶点入队列  */
                    }
                }
            }
        }
    }
}

遍历结果为:A B F C G I E D H (上图所示的图结构)

一、如果我们使用的是邻接表的方式,则代码如下:(改编自《大话数据结构》)

typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9

/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */
{
    int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
    int weight;     /* 用于存储权值,对于非网图可以不需要 */
    struct EdgeNode *next; /* 链域,指向下一个邻接点 */
} EdgeNode;

typedef struct VertexNode /* 顶点表结点 */
{
    int in; //结点入度
    char data; /* 顶点域,存储顶点信息 */
    EdgeNode *firstedge;/* 边表头指针 */
} VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges; /* 图中当前顶点数和边数 */
} graphAdjList, *GraphAdjList;

/* 邻接表的广度遍历算法 */
void BFSTraverse(GraphAdjList GL)
{
    int i, j;
    EdgeNode *p;
    Queue Q;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = false;
    InitQueue(&Q);/* 初始化一辅助用的队列 */

    for (i = 0; i < GL->numVertexes; i++)/* 对每一个顶点做循环 */
    {
        if (!visited[i])/* 若是未访问过就处理 */
        {
            visited[i] = true;/* 设置当前顶点访问过 */
            cout << GL->adjList[i].data << ' '; /* 打印顶点,也可以其它操作 */
            EnQueue(&Q, i);/* 将此顶点入队列 */
            while (!QueueEmpty(Q))/* 若当前队列不为空 */
            {
                DeQueue(&Q, &i);/* 将队对元素出队列,赋值给i */
                p = GL->adjList[i].firstedge;/* 找到当前顶点的边表链表头指针 */

                while (p)
                {
                    /* 判断其它顶点若与当前顶点存在边且未访问过  */
                    if (!visited[p->adjvex])
                    {
                        visited[p->adjvex] = true;/* 将找到的此顶点标记为已访问 */
                        cout << GL->adjList[p->adjvex].data << ' '; /* 打印顶点 */
                        EnQueue(&Q, p->adjvex);/* 将找到的此顶点入队列  */
                    }
                    p  = p->next;/* 指针指向下一个邻接点 */
                }
            }
        }
    }
}

遍历结果为:A F B G E I C H D (上图所示的图结构)

由结果可以看出,因为我们采用了不同的存储方式,即使使用的是同样的广度优先搜索,遍历的结果也是不同的。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

5.3.1图的遍历

图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特...

901
来自专栏python读书笔记

《python算法教程》Day2 - 图和树的基本数据结构图树

今天是读《python算法教程》的第2天,读书笔记内容为用python实现图和树的基本数据结构。 图 图的基本数据结构有两种,分别为邻接列表和邻接矩阵。 现根...

2665
来自专栏有趣的Python

15-数据结构探险系列-图篇数据结构探险之图篇

图的存储结构:邻接矩阵(数组);邻接表(链表)有向; 十字链表(链表)有向;邻接多重表(链表)无向

1213
来自专栏Ryan Miao

Java8-理解Collector

2954
来自专栏Danny的专栏

设计模式奠基石——UML关系转化为代码

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1943
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

2488
来自专栏mathor

搜索(2)

1334
来自专栏数据结构与算法

BZOJ4245: [ONTAK2015]OR-XOR(前缀和)

因为最终答案是xor之后or,所以分开之后之后这样位上1的数量是一定是偶数,否则直接加到答案里面

731
来自专栏猿人谷

三位数的排列组合

题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列...

2379
来自专栏清墨_iOS分享

OpenGLES-02 绘制基本图元(点、线、三角形)

在绘制之前,我们需要了解下面的知识: 一、渲染管线 下图中展示整个OpenGL ES 2.0可编程渲染管线 ? 渲染管线.png 图中Vertex Shade...

3849

扫码关注云+社区

领取腾讯云代金券