图的广度优先搜索(BFS)与树的广度优先搜索类似,与树不同的是,图中可能存在循环。所我们可能会再次访问到同一个节点。为了表面多次处理同一个节点,我们要布尔变量数据记录节点有没有被访问过。为了简化,我们假设所有的节点都是从根节点可达的。
如以上示例所示,BFS算法首先从A到B遍历到E到F,然后遍历C和G,最后遍历到D。它采用以下规则。
规则1 - 访问相邻的未访问顶点,将其标签为已访问,将其插入队列。
规则2 - 如果未找到相邻的顶点,请从队列中删除第一个顶点。
规则3 - 重复规则1和规则2,直到队列为空。
步骤 | 遍历 | 说明 |
---|---|---|
1 | 初始化队列。 | |
2 | 我们从访问 S (起始节点)开始,并将其标签为已访问。 | |
3 | 然后我们看到了 S 中未访问的相邻节点。在此示例中,我们有三个节点,但按字母顺序选择 A ,将其标签为已访问并排队。 | |
4 | 接下来, S 中未访问的相邻节点是 B 。我们将其标签为已访问并排队。 | |
5 | 接下来, S 中未访问的相邻节点是 C 。我们将其标签为已访问并排队。 | |
6 | 现在, S 不再有未访问的相邻节点。因此,我们出队并找到 A 。 | |
7 | 从 A 开始,我们将 D 作为未访问的相邻节点。我们将其标签为已访问并排队。 |
在这一阶段,我们没有未标签(未访问)的节点。但是按照算法,我们继续进行出队以获取所有未访问的节点,清空队列后,程序结束。
来源:LearnFk无涯教程网
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //stack variables int stack[MAX]; int top = -1; //graph variables //array of vertices struct Vertex* lstVertices[MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //stack functions void push(int item) { stack[++top] = item; } int pop() { return stack[top--]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { printf("%c ",lstVertices[vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i < vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) { return i; } } return -1; } void depthFirstSearch() { int i; //mark first node as visited lstVertices[0]->visited = true; //display the vertex displayVertex(0); //push vertex index in stack push(0); while(!isStackEmpty()) { //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(peek()); //no adjacent vertex found if(unvisitedVertex == -1) { pop(); } else { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i < MAX; i++) // set adjacency { for(j = 0; j < MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex('S'); // 0 addVertex('A'); // 1 addVertex('B'); // 2 addVertex('C'); // 3 addVertex('D'); // 4 addEdge(0, 1); // S - A addEdge(0, 2); // S - B addEdge(0, 3); // S - C addEdge(1, 4); // A - D addEdge(2, 4); // B - D addEdge(3, 4); // C - D printf("Depth First Search: ") depthFirstSearch(); return 0; }
Depth First Search: S A D B C
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)