头歌实训:邻接表存储图的广度优先遍历
文章目录
任务描述
相关知识
邻接表存储图
图的遍历
广度优先遍历过程:
算法设计思路:
编程要求
测试说明
输入格式:
输出格式:
样例输入:
样例输出:
源代码:
任务描述
本关任务:请你实现 bfs.cpp 里的void BFS( AdjGraph* G, VertexType V)函数。 约定:顶点编号小的先输出。
相关知识
为了完成本关任务,你需要掌握:1.如何使用邻接表存储图,2.如何遍历图。
邻接表存储图
一个包含5个顶点的无向图如图所示。
图1 一个包含5个顶点的无向图
图 2 给出了对图 1 的无向图的邻接表存储结构图:每个顶点的名称由一个整数描述,对图中每个顶点i建立一个单链表, 将顶点i的所有邻接点链起来。
每个单链表上添加一个表头结点(表示顶点信息)。并将所有表头结点构成一个数组, 下标为i的元素表示顶点i的表头结点。
图2 图1的无向图的邻接表
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法,如图3所示。
图3 图的邻接表表示形式
一个带权的有向图(网)的邻接表存储形式如图4所示。
图4 带权有向图的邻接表存储结构图
图的邻接表存储类型定义如下:
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
int weight; //该边的权值等信息
} ArcNode;
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode;
typedef struct
{ VNode adjlist[MAXV] ; //邻接表
int n, e; //图中顶点数n和边数e
} AdjGraph;
一个邻接表通常用指针引用:
给定指向该结构的指针G,就可以对图进行操作。
图的遍历
所谓图的遍历(graph traversal),也称为搜索(search),就是从图中某个顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次。遍历可以采取两种方法进行:深度优先搜索(DFS,depth first search)和广度优先搜索(BFS,breadth first search)。
广度优先遍历过程:
广度优先搜索(BFS,Breadth First Search)是一个分层的搜索过程,没有回退过程,是非递归的。其访问过程如下:
(1)访问初始点v, 接着访问v的所有未被访问过的邻接点v1, v2, …, vt。
(2)按照v1, v2, …, vt的次序, 访问每一个顶点的所有未被访问过的邻接点。
(3)依次类推, 直到图中所有和初始点v有路径相通的顶点都被访问过为止。
算法设计思路:
广度优先搜索遍历体现先进先出的特点, 用队列实现。
如何确定一个顶点是否访问过? 设置一个visited[] 全局数组, visited[i]=0表示顶点i没有访问; visited[i]=1表示顶点i已经访问过。
如果用邻接表存储图,则 BFS 算法实现的伪代码如下:
BFS(图 G, 顶点 i ) //从顶点 i 进行广度优先搜索
{
visited[ i ] = 1; //将顶点 i 的访问标志置为 1
将顶点 i 入队列;
while( 队列不为空 )
{
取出队列头的顶点,设为 k
p = 顶点 k 的边链表表头指针
while( p 不为空 )
{
//设指针 p 所指向的边结点所表示的边的另一个顶点为顶点 j
if( 顶点 j 未访问过 )
{
将顶点 j 的访问标志置为 1
将顶点 j 入队列
}
p = p->nextarc; //p 移向下一个边结点
} //end of while
} //end of while
} //end of BFS
对图1运行该算法的结果(从顶点2出发): 2 1 3 4 0。
编程要求
请你在右侧的代码窗口中实现bfs.cpp里的void BFS( AdjGraph* G, VertexType V)函数。 注意遵守约定:顶点编号小的先输出。
注:本关提供C++ STL队列容器queue,你可以直接使用。
测试说明
本关的测试过程如下:
1.平台编译 step2/bfs.cpp 并生成可执行文件;
2.平台运行该可执行文件,并以标准输入方式提供测试输入;
3.平台获取该可执行文件的输出,然后将其与预期输出对比,如果一致则测试通过;否则测试失败。
输入输出格式说明:
输入格式:
输入V,开始遍历的起始顶点编号。
输出格式:
输出对图进行广度优先遍历的顶点序列,每个顶点编号前面有一个空格。
以下是平台对 step2/bfs.cpp 的测试样例:
样例输入:
测试输入:2
样例输出:
预期输出:BFS from 2: 2 0 3 5 4 1 6
开始你的任务吧,祝你成功!
源代码:
#include "bfs.h"
/*
* 从顶点V出发进行广度优先搜索。
* 函数BFS应从编号为V的顶点出发广度优先遍历图,
* 遍历访问邻接点时,要求按序号递增的顺序。
* 题目保证V是图中的合法顶点。
*/
void BFS( AdjGraph* G, VertexType V)
{
/*******************begin*******************/
int Q[11], head, rear, *visited = (int *)malloc(sizeof(int) * G->n);
//利用循环队列存储未遍历完的结点,队头队尾指针head和rear,遍历数组visited初值为0
for(int i = 0; i < G->n; i++) visited[i] = 0;
head = rear = 0;//初始化队头和队尾指针
Q[rear] = V; //第一个访问的元素入栈
rear = (rear + 1) % 11; //队尾指针后移
visited[V] = 1; //遍历数组置为1
printf(" %d", V); //打印第一个元素
while(head != rear) //但队列非空时遍历
{
ArcNode *p = G->adjlist[Q[head]].firstarc; //临时指针p存放以及遍历结点的相邻结点
while(p) //当p非空时遍历它
{
if(visited[p->adjvex] == 0) //当遍历数组为0说明未被遍历过即可直接遍历同时入队以及使遍历数组置为1
{
printf(" %d", p->adjvex);
Q[rear] = p->adjvex;
rear = (rear + 1) % 11;
visited[p->adjvex] = 1;
}
p = p->nextarc; //p向后移
}
head = (head + 1) % 11; //出队刚才遍历完的结点
}
/*******************end*******************/
}
int main()
{
AdjGraph* G;
VertexType V;
G = CreateGraph();
scanf("%d", &V);
printf("BFS from %d:", V);
BFS(G, V);
return 0;
}
标签:遍历,BFS,头歌,实训,邻接,visited,顶点,rear
From: https://blog.csdn.net/guang_Lee/article/details/143166617