Shulou(Shulou.com)06/02 Report--

This article will explain in detail that the breadth-first traversal algorithm of the graph is similar to the example analysis of binary tree. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

The breadth-first traversal of a graph is horizontal priority traversal, which is similar to the layer-by-layer traversal of binary trees. Breadth-first traversal is a search traversal along the width of the tree starting from the root node, that is, traversing according to the level; each layer is accessed sequentially from top to bottom, in each layer, the node is accessed from left to right (or right to left), and after visiting one layer, it goes to the next layer until no node can be accessed.

1. Preface

Similar to the traversal of a tree, the traversal of a graph starts from a certain point in the graph, and then accesses all the vertices in the graph in some way, and only once.

But the traversal of a graph is more complex than a tree. Because any vertex in the graph may be adjacent to other vertices, the vertices that have been visited must be recorded in the traversal of the graph to avoid repeated visits.

According to the different search paths, we can divide the methods of traversing the graph into two kinds: breadth-first search and depth-first search.

two。 The basic concept of graph 2.1. Undirected graph and undirected graph

The vertex pair (u.j.v) is disordered, that is, (u.j.v) and (v.j.u) are the same edge. It is often represented by a pair of parentheses.

Figure 2-1-1 example of undirected graph

The vertex pair is ordered, which refers to a directed edge from vertex u to vertex v. Where u is the starting point of the directed edge and v is the end point of the directed edge. It is often indicated by a pair of angle brackets.

Figure 2-1-2 directed illustration

2.2. Weighted and net

There may be a value with some meaning on each edge of the graph, which is called the weight on that edge. This weighted graph is called a net.

2.3. Connected graphs and unconnected graphs

Connected graph: in undirected graph G, if there is a path from vertex v to vertex v', then v and v 'are said to be connected. G is said to be a connected graph if any two vertices v, v '∈ V, v and v' are connected. The above two graphs are connected graphs.

Unconnected graph: if there is a disconnection between v and v'in an undirected graph G, then G is called an unconnected graph.

Figure 2-3 example of an unconnected graph

3. Breadth first search 3.1. The basic idea of the algorithm

Breadth-first search is similar to the hierarchical traversal process of a tree. It needs to be implemented with a queue. As shown in figure 2-1-1, to traverse every vertex from v0 to V6, we can set v0 as the first layer, v1, v2, and v3 as the second layer, v4 and v5 as the third layer, and v6 as the fourth layer, and then traverse each vertex of each layer one by one.

The specific process is as follows:

1. Preparation: create a visited array to record the vertices that have been visited; create a queue to store the vertices of each layer; initialize graph G.

two。 Start with v0 in the figure, set the value of the visited [v0] array to true, and queue v0.

3. As long as the queue is not empty, repeat the following:

(1) the leader of the team is out of the team.

(2) check all adjacent vertices w of u in turn. If the value of visited [w] is false, visit w, set visited [w] to true, and join the queue at the same time.

3.2. The implementation process of the algorithm

White indicates that it has not been accessed, gray indicates that it is about to be visited, and black indicates that it has been visited.

Visited array: 0 means not accessed, 1 indicates access.

Queue: elements at the beginning of the line and elements at the end of the line.

1. Initially, all vertices are not accessed, the visited array is initialized to 0, and there are no elements in the queue.

Figure 3-2-1

two。 The vertex v0 is about to be accessed.

Figure 3-2-2

3. Access vertex v0, juxtapose the value of visited [0] to 1, and queue v0.

Figure 3-2-3

4. Dequeue v0 and visit the neighbor v2 of v0. Judge visited [2], because the value of visited [2] is 0, access v2.

Figure 3-2-4

5. Set visited [2] to 1 and join the team with v2.

Figure 3-2-5

6. Access v0 adjacency point v1. Judge visited [1], because the value of visited [1] is 0, access v1.

Figure 3-2-6

7. Set visited [1] to 0 and join the team with v1.

Figure 3-2-7

8. Determine visited [3], because its value is 0, access v3. Set visited [3] to 0 and join the team with v3.

Figure 3-2-8

All adjacency points of 9.v0 have been accessed. Dequeue the head element v2 and start visiting all the neighboring points of v2.

Start accessing v2 neighbor v0, determine visited [0], because its value is 1, do not access.

Continue to visit v2 neighbor v4 and judge visited [4]. Since its value is 0, access v4, as shown below:

Figure 3-2-9

10. Set visited [4] to 1 and join the team with v4.

Figure 3-2-10

All adjacency points of 11.v2 have been accessed. Dequeue the header element v1 and start accessing all adjacent points of v1.

Start accessing v1 adjacency v0 because the visited [0] value is 1 and no access is made.

Continue to access v1 adjacency v4 because visited [4] has a value of 1 and does not access.

Continue to access v1 adjacency v5, because the value of visited [5] is 0, and access v5, as shown below:

Figure 3-2-11

twelve。 Set visited [5] to 1 and join the team with v5.

Figure 3-2-12

All adjacency points of 13.v1 have been visited. Dequeue the header element v3 and start visiting all adjacency points of v3.

Start accessing v3 adjacency v0 because the visited [0] value is 1 and no access is made.

Continue to access v3 neighbor v5 because the visited [5] value is 1 and there is no access.

Figure 3-2-13

All adjacency points of 14.v3 have been visited. Dequeue the header element v4 and start visiting all adjacency points of v4.

Start accessing the adjacency v2 of v4 because the value of visited [2] is 1 and no access is made.

Continue to access the adjacency point V6 of v4, because the value of visited [6] is 0, and access V6, as shown below:

Figure 3-2-14

15. Set the visited [6] value to 1 and join the queue with V6.

Figure 3-2-15

All adjacency points of 16.v4 have been visited. Dequeue the header element v5 and start visiting all adjacency points of v5.

Start accessing v5 adjacency v3 because visited [3] has a value of 1 and no access is made.

Continue to access v5 adjacency point V6 because visited [6] has a value of 1 and is not accessed.

Figure 3-2-16

All the adjacency points of 17.v5 have been visited. Dequeue the header element V6 and start visiting all the adjacency points of V6.

Start accessing V6 adjacency point v4 because visited [4] has a value of 1 and no access is made.

Continue to access v6 adjacency v5, because the value of visited [5] is 1, no access is made.

Figure 3-2-17

18. The queue is empty, exit the loop, and all vertices are accessed.

Figure 3-2-18

3.3.The implementation of the specific code 3.3.1 represents the breadth-first search of the graph in terms of adjacency matrix / * definition of some quantities * / queue Q; / / defines a queue and uses the library function queue#define MVNum 100 / / to represent the maximum number of vertices bool visited [MVNum] / / define a visited array to record the vertices that have been accessed / * adjacency matrix storage representation * / typedef struct AMGraph {char vexs [MVNum]; / / vertex table int arcs [MVNum] [MVNum]; / / adjacency matrix int vexnum, arcnum; / / current number of vertices and edges} AMGraph / * find the corresponding subscript of vertex v * / int LocateVex (AMGraph & G, char v) {int i; for (I = 0; I)

< G.vexnum; i++) if (G.vexs[i] == v) return i;}/*采用邻接矩阵表示法，创建无向图G*/int CreateUDG_1(AMGraph &G){ int i, j, k; char v1, v2; scanf("%d%d", &G.vexnum, &G.arcnum); //输入总顶点数，总边数 getchar(); //获取'\n'，防止其对之后的字符输入造成影响 for (i = 0; i < G.vexnum; i++) scanf("%c", &G.vexs[i]); //依次输入点的信息 for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = 0; //初始化邻接矩阵边，0表示顶点i和j之间无边 for (k = 0; k < G.arcnum; k++) { getchar(); scanf("%c%c", &v1, &v2); //输入一条边依附的顶点 i = LocateVex(G, v1); //找到顶点i的下标 j = LocateVex(G, v2); //找到顶点j的下标 G.arcs[i][j] = G.arcs[j][i] = 1; //1表示顶点i和j之间有边，无向图不区分方向 } return 1;}/*采用邻接矩阵表示图的广度优先遍历*/void BFS_AM(AMGraph &G,char v0){/*从v0元素开始访问图*/ int u,i,v,w; v = LocateVex(G,v0); //找到v0对应的下标 printf("%c ", v0); //打印v0 visited[v] = 1; //顶点v0已被访问 q.push(v0); //将v0入队 while (!q.empty()) { u = q.front(); //将队头元素u出队，开始访问u的所有邻接点 v = LocateVex(G, u); //得到顶点u的对应下标 q.pop(); //将顶点u出队 for (i = 0; i < G.vexnum; i++) { w = G.vexs[i]; if (G.arcs[v][i] && !visited[i])//顶点u和w间有边，且顶点w未被访问 { printf("%c ", w); //打印顶点w q.push(w); //将顶点w入队 visited[i] = 1; //顶点w已被访问 } } }}3.3.2用邻接表表示图的广度优先搜索/*找到顶点对应的下标*/int LocateVex(ALGraph &G, char v){ int i; for (i = 0; i < G.vexnum; i++) if (v == G.vertices[i].data) return i;}/*邻接表存储表示*/typedef struct ArcNode //边结点{ int adjvex; //该边所指向的顶点的位置 ArcNode *nextarc; //指向下一条边的指针 int info; //和边相关的信息，如权值}ArcNode;typedef struct VexNode //表头结点{ char data; ArcNode *firstarc; //指向第一条依附该顶点的边的指针}VexNode,AdjList[MVNum]; //AbjList表示一个表头结点表typedef struct ALGraph{ AdjList vertices; int vexnum, arcnum;}ALGraph;/*采用邻接表表示法，创建无向图G*/int CreateUDG_2(ALGraph &G){ int i, j, k; char v1, v2; scanf("%d%d", &G.vexnum, &G.arcnum); //输入总顶点数，总边数 getchar(); for (i = 0; i < G.vexnum; i++) //输入各顶点，构造表头结点表 { scanf("%c", &G.vertices[i].data); //输入顶点值 G.vertices[i].firstarc = NULL; //初始化每个表头结点的指针域为NULL } for (k = 0; k < G.arcnum; k++) //输入各边，构造邻接表 { getchar(); scanf("%c%c", &v1, &v2); //输入一条边依附的两个顶点 i = LocateVex(G, v1); //找到顶点i的下标 j = LocateVex(G, v2); //找到顶点j的下标 ArcNode *p1 = new ArcNode; //创建一个边结点*p1 p1->

Adjvex = j; / its adjacency domain is j p1-> nextarc = G.vertices [I] .firstarc; G.vertices [I] .firstarc = p1; / / insert the new node * p into the edge table header ArcNode * p2 = new ArcNode of vertex v1 / generate another symmetrical new table node * p2p2-> adjvex = I; p2-> nextarc = G.vertices [j] .firstarc; G.vertices [j] .firstarc = p1;} return 1 } / * the breadth-first traversal of the graph is represented by the adjacency table * / void BFS_AL (ALGraph & G, char v0) {int uLINGWL v; ArcNode * p; printf ("% c", v0); / / print vertex v = LocateVex (G, v0) / / find the subscript visited [v] = 1 for v0; / / Vertex v0 has been accessed q.push (v0) / / add vertex v0 to the team while (! q.empty ()) {u = q.front () / / dequeue the vertex element u and start visiting all adjacent points v = LocateVex (G, u) of u; / / get the corresponding subscript q.pop () of vertex u / / dequeue vertex u from for (p = G.vertices [v] .firstarc; p; p = p-> nextarc) / / traverse the adjacency {w = p-> adjvex of vertex u If (! visited [w]) / / Vertex p was not accessed {printf ("% c", G.vertices [w] .data); / / print vertex p visited [w] = 1 / / Vertex p has been visited by q.push (G.vertices [w] .data); / / Vertex p has been queued} 3.4. Implementation of breadth-first traversal of unconnected graphs / * breadth-first search for unconnected graphs * / void BFSTraverse (AMGraph G) {int v; for (v = 0; v)

< G.vexnum; v++) visited[v] = 0; //将visited数组初始化 for (v = 0; v < G.vexnum; v++) if (!visited[v]) BFS_AM(G, G.vexs[v]); //对尚未访问的顶点调用BFS}4.深度优先搜索4.1算法的基本思路 深度优先搜索类似于树的先序遍历，具体过程如下： 准备工作：创建一个visited数组，用于记录所有被访问过的顶点。 1.从图中v0出发，访问v0。 2.找出v0的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。 3.返回前一个访问过的仍有未被访问邻接点的顶点，继续访问该顶点的下一个未被访问领接点。 4.重复2,3步骤，直至所有顶点均被访问，搜索结束。 4.2算法的实现过程 1.初始时所有顶点均未被访问，visited数组为空。 图4-2-1 2.即将访问v0。 图4-2-2 3.访问v0，并将visited[0]的值置为1。 图4-2-3 4.访问v0的邻接点v2，判断visited[2]，因其值为0，访问v2。 图4-2-4 5.将visited[2]置为1。 图4-2-5 6.访问v2的邻接点v0，判断visited[0]，其值为1，不访问。 继续访问v2的邻接点v4，判断visited[4]，其值为0，访问v4。 图4-2-6 7.将visited[4]置为1。 图4-2-7 8.访问v4的邻接点v1，判断visited[1]，其值为0，访问v1。 图4-2-8 9.将visited[1]置为1。 图4-2-9 10.访问v1的邻接点v0，判断visited[0]，其值为1，不访问。 继续访问v1的邻接点v4，判断visited[4]，其值为1，不访问。 继续访问v1的邻接点v5，判读visited[5]，其值为0，访问v5。 图4-2-10 11.将visited[5]置为1。 图4-2-11 12.访问v5的邻接点v1，判断visited[1]，其值为1，不访问。 继续访问v5的邻接点v3，判断visited[3]，其值为0，访问v3。 图4-2-12 13.将visited[1]置为1。 图4-2-13 14.访问v3的邻接点v0，判断visited[0]，其值为1，不访问。 继续访问v3的邻接点v5，判断visited[5]，其值为1，不访问。 v3所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5所有邻接点。 访问v5的邻接点v6，判断visited[6]，其值为0，访问v6。 图4-2-14 15.将visited[6]置为1。 图4-2-15 16.访问v6的邻接点v4，判断visited[4]，其值为1，不访问。 访问v6的邻接点v5，判断visited[5]，其值为1，不访问。 v6所有邻接点均已被访问，回溯到其上一个顶点v5，遍历v5剩余邻接点。 图4-2-16 17.v5所有邻接点均已被访问，回溯到其上一个顶点v1。 v1所有邻接点均已被访问，回溯到其上一个顶点v4，遍历v4剩余邻接点v6。 v4所有邻接点均已被访问，回溯到其上一个顶点v2。 v2所有邻接点均已被访问，回溯到其上一个顶点v1，遍历v1剩余邻接点v3。 v1所有邻接点均已被访问，搜索结束。 图4-2-17 4.3具体代码实现4.3.1用邻接矩阵表示图的深度优先搜索 邻接矩阵的创建在上述已描述过，这里不再赘述 void DFS_AM(AMGraph &G, int v){ int w; printf("%c ", G.vexs[v]); visited[v] = 1; for (w = 0; w < G.vexnum; w++) if (G.arcs[v][w]&&!visited[w]) //递归调用 DFS_AM(G,w);}4.3.2用邻接表表示图的深度优先搜素 邻接表的创建在上述已描述过，这里不再赘述。 void DFS_AL(ALGraph &G, int v){ int w; printf("%c ", G.vertices[v].data); visited[v] = 1; ArcNode *p = new ArcNode; p = G.vertices[v].firstarc; while (p) { w = p->

Adjvex; if (! visited [w]) DFS_AL (G, w); p = p-> nextarc }} this is the end of the article on "the breadth-first traversal algorithm of a graph is similar to the example analysis of a binary tree". I hope the above content can be helpful to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.