廣度優先遍歷

廣度優先搜索算法

廣度優先搜索算法(BFS)遍歷圖在廣度運動並使用隊列記得要獲得下一個頂點，當窮途末路發生時迭代開始搜索。

Breadth

正如上面的例子給出的，BFS算法首先從A到B遍歷到E到F，再到C和G最後到D. 它採用以下規則。

規則 1 − 訪問鄰近的未訪問頂點。標記它訪問並顯示它。將其插入到隊列中。
規則 2 − 如果沒有相鄰頂點發現，刪除隊列中的第一個頂點。
規則 3 − 重複第1條和第2條，直到隊列爲空。

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

演示程序

GraphDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 10

struct Vertex {
char label;
bool visited;
};

//stack variables

int stack[MAX];
int top = -1;

//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;

//stack functions

void push(int item) {
stack[++top] = item;
}

int pop() {
return stack[top--];
}

int peek() {
return stack[top];
}

bool isStackEmpty(){
return top == -1;
}

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

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

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('A'); //0
addVertex('B'); //1
addVertex('C'); //2
addVertex('D'); //3
addVertex('E'); //4
addVertex('F'); //5
addVertex('G'); //6

/* 1 2 3
* 0 |--B--C--D
* A--|
* |
* | 4
* |-----E
* | 5 6
* | |--F--G
* |--|
*/
addEdge(0, 1); //AB
addEdge(1, 2); //BC
addEdge(2, 3); //CD
addEdge(0, 4); //AC
addEdge(0, 5); //AF
addEdge(5, 6); //FG

printf("Depth First Search: ");
//A B C D E F G
depthFirstSearch();

printf("\nBreadth First Search: ");
//A B E F C G D
breadthFirstSearch();
}

如果我們編譯並運行上述程序，那麼這將產生以下結果 -

Depth First Search: A B C D E F G
Breadth First Search: A B E F C G D

數據結構和算法教程

廣度優先搜索算法

演示程序