图的广度优先遍历:释义详见百度百科

  基本思想: 广度优先搜索使用队列(queue)来实现:
    1、把根节点放到队列的末尾。
    2、每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
    3、找到所要找的元素时结束程序。
    4、如果遍历整个树还没有找到,结束程序。

广度优先遍历

1.邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
const int maxsize = 1010;
//图的邻接表的存储结构
typedef struct ArcNode { //边结点
int adjvex; //序号
struct ArcNode *next;
}ArcNode;
typedef struct VNode{ //顶点
ArcNode *firstarc;
int no;
}VNode;
typedef struct Graph { //图
VNode VNodeList[maxsize];
int node; //顶点数
int edge; //边数
}Graph;

//创建邻接表
void createGraph(Graph *G){
int start;
int end;
ArcNode *e;

scanf("%d%d",&(G->node),&(G->edge)); //输入边数和结点数

for(int i = 0; i < G->node; i++){//输入顶点
scanf("%d",&(G->VNodeList[i].no));
G->VNodeList[i].firstarc = NULL;
}

for(int i = 0; i < G->edge; i++){
scanf("%d%d",&start,&end);

//插入该点指向的边表
e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
e->adjvex = end;
e->next = G->VNodeList[start].firstarc;
G->VNodeList[start].firstarc = e;//类似于链表的前插

//无向图才有下方
e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
e->adjvex = start;
e->next = G->VNodeList[end].firstarc;
G->VNodeList[end].firstarc = e;//类似于链表的前插
}
}

int visited[maxsize] = {0};
void BFS(Graph *g, int v){
if(g == NULL) return;
int queue[maxsize];
int front = -1, rear = 0;
printf("访问结点:%d\n",g->VNodeList[v].no);
visited[v] = 1;
queue[rear++] = v;
ArcNode* e;

while(front != rear){
int u = queue[++front]; //取队首
e = g->VNodeList[u].firstarc; //获取第一个邻接点
while(e!=NULL){ //遍历
if(visited[e->adjvex] == 0){
printf("访问结点:%d\n",g->VNodeList[e->adjvex].no);
visited[e->adjvex] = 1;
queue[rear++] = e->adjvex;
}
e = e.next;
}
}
}

2.邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <stdlib.h>
const int maxn = 110;
//图的邻接矩阵的存储结构
typedef struct
{
int vertex[maxn]; //顶点数组
int arc[maxn][maxn]; //邻接矩阵
int vertexnum; //顶点数
int arcnum; //边数
}Graph;

//创建邻接矩阵
void CreateGraph(Graph &G){
scanf("%d%d",&G.vertexnum,&G.arcnum); //输入边数,顶点数
for(int i = 0; i < G.vertexnum; i++) //输入顶点信息
scanf("%d",&G.vertex[i]);
for(int i = 0; i < G.vertexnum; i++) //将所有边初始化为无穷大
for(int j = 0; j < G.vertexnum; j++)
G.arc[i][j] = -1;
for(int k = 0; k < G.arcnum; k++){
int start, end, weight;
scanf("%d%d%d",&start,&end,&weight); //输入起点,终点,权重
G.arc[start][end] = weight;
//无向图才有下方这句
G.arc[end][start] = G.arc[start][end]; //无向图的邻接矩阵为对称矩阵
}
}

int visited[maxn] = {0}
void BFS(Graph* g, int v){
if(g == NULL) return;
int queue[maxn];
int front = -1, rear = 0;
//memset(visited,0,sizeof(visited)); //或者在这初始化数组
printf("访问结点:%d\n", g->vertex[v]);                 //访问
visited[v] = 1;            //顶点v已被访问
q[rear++] = v;         //将v入队

while (front != rear){
int u = q[++front]; //将队头元素u出队,开始访问u的所有邻接点
for (int i = 0; i < G.vexnum; i++){
int w = g->vertex[i];
if (g->arc[u][i]!=-1 && visited[i] == 0){ //有边,且顶点未被访问
printf("访问结点:%d\n", w); //输出顶点
q[rear++] = i; //将顶点w入队
visited[i] = 1; //置已访问
}
}
}
}

本文标题:图的广度优先遍历

文章作者:JarryChen

发布时间:2019年10月29日 - 17:42

最后更新: 2019年11月29日 07:18

原始链接: https://jarrychen.xyz/archives/3acb628c.html

× 请我喝奶茶~
打赏二维码