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

• 

  广度优先遍历

  广度优先搜索（bfs）算法以广度运动遍历图形，并在任何迭代出现死角时使用队列记住要获取的下一个顶点以开始搜索。

  

  如以上示例所示，BFS算法首先从A到B遍历到E到F，然后遍历C和G，最后遍历到D。它采用以下规则。

  • 规则1-访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。
  • 规则2-如果未找到相邻的顶点，请从队列中删除第一个顶点。
  • 规则3-重复规则1和规则2，直到队列为空。

  遍历	描述
  	初始化堆栈。
  	将S标记为已访问，并将其放入堆栈。探索S中所有未访问的相邻节点。我们有三个节点，我们可以选择其中任何一个。对于此示例，我们将按字母顺序选择节点。
  	将A标记为已访问，并将其放入堆栈。探索来自A的任何未访问的相邻节点。S和D都与A相邻，但是我们仅关注未访问的节点。
  	访问D并将其标记为已访问并放入堆栈。在这里，我们有B和C节点，它们与D相邻并且都未访问。但是，我们将再次按字母顺序选择。
  	我们选择B，将其标记为已访问并放入堆栈。在这里B没有任何未访问的相邻节点。因此，我们从堆栈中弹出B。
  	我们检查堆栈顶部是否返回上一个节点，并检查它是否有未访问的节点。在这里，我们发现D在堆栈的顶部。
  	只有未访问的邻接节点是从D是C现在。因此，我们访问C，将其标记为已访问并将其放入堆栈。

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

  C语言算法实现

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

  

  
  #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;
  }
  

  复制

  尝试一下