上一节:
下一节:

  数据结构&算法 广度优先遍历

  • 广度优先遍历

    广度优先搜索（bfs）算法以广度运动遍历图形，并在任何迭代出现死角时使用队列记住要获取的下一个顶点以开始搜索。
    bsf
    如以上示例所示，BFS算法首先从A到B遍历到E到F，然后遍历C和G，最后遍历到D。它采用以下规则。
    • 规则1-访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。
    • 规则2-如果未找到相邻的顶点，请从队列中删除第一个顶点。
    • 规则3-重复规则1和规则2，直到队列为空。
    遍历 描述
    bfs 初始化堆栈。
    bfs 将S标记为已访问，并将其放入堆栈。探索S中所有未访问的相邻节点。我们有三个节点，我们可以选择其中任何一个。对于此示例，我们将按字母顺序选择节点。
    bfs 将A标记为已访问，并将其放入堆栈。探索来自A的任何未访问的相邻节点。S和D都与A相邻，但是我们仅关注未访问的节点。
    bfs 访问D并将其标记为已访问并放入堆栈。在这里，我们有B和C节点，它们与D相邻并且都未访问。但是，我们将再次按字母顺序选择。
    bfs 我们选择B，将其标记为已访问并放入堆栈。在这里B没有任何未访问的相邻节点。因此，我们从堆栈中弹出B。
    bfs 我们检查堆栈顶部是否返回上一个节点，并检查它是否有未访问的节点。在这里，我们发现D在堆栈的顶部。
    bfs 只有未访问的邻接节点是从D是C现在。因此，我们访问C，将其标记为已访问并将其放入堆栈。
    在这一阶段，我们没有未标记（未访问）的节点。但是按照算法，我们继续进行出队以获取所有未访问的节点。清空队列后，程序结束。

  • C语言算法实现

    我们不会看到C编程语言中广度优先遍历(或深度优先搜索)的实现。作为参考，我们将仿效我们的例子，并以此作为我们的图的模型
    bfs
    
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 5

struct Vertex {
   char label;
   bool visited;
};

//queue variables

int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;

//graph variables

//array of vertices
struct Vertex* lstVertices[MAX];

//adjacency matrix
int adjMatrix[MAX][MAX];

//vertex count
int vertexCount = 0;

//queue functions

void insert(int data) {
   queue[++rear] = data;
   queueItemCount++;
}

int removeData() {
   queueItemCount--;
   return queue[front++]; 
}

bool isQueueEmpty() {
   return queueItemCount == 0;
}

//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 breadthFirstSearch() {
   int i;

   //mark first node as visited
   lstVertices[0]->visited = true;

   //display the vertex
   displayVertex(0);   

   //insert vertex index in queue
   insert(0);
   int unvisitedVertex;

   while(!isQueueEmpty()) {
      //get the unvisited vertex of vertex which is at front of the queue
      int tempVertex = removeData();   

      //no adjacent vertex found
      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
    
   }   

   //queue 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("\nBreadth First Search: ");
   
   breadthFirstSearch();

   return 0;
}
    尝试一下
上一节:
下一节: