广度优先遍历

广度优先遍历 首页 / 结构和算法入门教程 / 广度优先遍历

图的广度优先搜索(BFS)与树的广度优先搜索类似,与树不同的是,图中可能存在循环。所我们可能会再次访问到同一个节点。为了表面多次处理同一个节点,我们要布尔变量数据记录节点有没有被访问过。为了简化,我们假设所有的节点都是从根节点可达的。

Breadth First Traversal

如以上示例所示,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 作为未访问的相邻节点。我们将其标签为已访问并排队。

在这一阶段,我们没有未标签(未访问)的节点。但是按照算法,我们继续进行出队以获取所有未访问的节点,清空队列后,程序结束。

无涯教程网

C语言实现该算法

#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

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

算法面试通关40讲 -〔覃超〕

玩转Git三剑客 -〔苏玲〕

编辑训练营 -〔总编室〕

设计模式之美 -〔王争〕

深入浅出云计算 -〔何恺铎〕

Spark性能调优实战 -〔吴磊〕

容量保障核心技术与实战 -〔吴骏龙〕

搞定音频技术 -〔冯建元 〕

Rust 语言从入门到实战 -〔唐刚〕

好记忆不如烂笔头。留下您的足迹吧 :)