数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Breadth First Search (BFS) Algorithm


Breadth First Search (BFS) Algorithm

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion to search a graph data structure for a node that meets a set of criteria. It uses a queue to remember the next vertex to start a search, when a dead end occurs in any iteration.

Breadth First Search (BFS) algorithm starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

Breadth First Traversal

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

  • Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.

  • Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Step Traversal Description
1 Breadth First Search Step One Initialize the queue.
2 Breadth First Search Step Two We start from visiting S (starting node), and mark it as visited.
3 Breadth First Search Step Three We then see an unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.
4 Breadth First Search Step Four Next, the unvisited adjacent node from S is B. We mark it as visited and enqueue it.
5 Breadth First Search Step Five Next, the unvisited adjacent node from S is C. We mark it as visited and enqueue it.
6 Breadth First Search Step Six Now, S is left with no unvisited adjacent nodes. So, we dequeue and find A.
7 Breadth First Search Step Seven From A we have D as unvisited adjacent node. We mark it as visited and enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program is over.

Example

Following are the implementations of Breadth First Search (BFS) Algorithm in various programming languages −

#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("
Breadth First Search: ");
   breadthFirstSearch();
   return 0;
}

Output

Breadth First Search: S A B C D
//C++ code for Breadth First Traversal
#include <iostream>
#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) {
   std::cout << 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
   std::cout << "Breadth First Search: ";
   breadthFirstSearch();
   return 0;
}

Output

Breadth First Search: S A B C D
//Java code for Breadth First Traversal
import java.util.LinkedList;
import java.util.Queue;
class Vertex {
    char label;
    boolean visited;
    public Vertex(char label) {
        this.label = label;
        visited = false;
    }
}
public class Graph {
    private static final int MAX = 5;
    private Vertex[] lstVertices;
    private int[][] adjMatrix;
    private int vertexCount;
    public Graph() {
        lstVertices = new Vertex[MAX];
        adjMatrix = new int[MAX][MAX];
        vertexCount = 0;
    }
    private void addVertex(char label) {
        Vertex vertex = new Vertex(label);
        lstVertices[vertexCount++] = vertex;
    }
    private void addEdge(int start, int end) {
        adjMatrix[start][end] = 1;
        adjMatrix[end][start] = 1;
    }
    private void displayVertex(int vertexIndex) {
        System.out.print(lstVertices[vertexIndex].label + " ");
    }
    private int getAdjUnvisitedVertex(int vertexIndex) {
        for (int i = 0; i < vertexCount; i++) {
            if (adjMatrix[vertexIndex][i] == 1 && !lstVertices[i].visited)
                return i;
        }
        return -1;
    }
    private void breadthFirstSearch() {
        lstVertices[0].visited = true;
        displayVertex(0);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            int tempVertex = queue.poll();
            int unvisitedVertex;
            while ((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                queue.add(unvisitedVertex);
            }
        }
        // Reset the visited flag
        for (int i = 0; i < vertexCount; i++) {
            lstVertices[i].visited = false;
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph();
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++)
                graph.adjMatrix[i][j] = 0;
        }
        graph.addVertex('S');   // 0
        graph.addVertex('A');   // 1
        graph.addVertex('B');   // 2
        graph.addVertex('C');   // 3
        graph.addVertex('D');   // 4
        graph.addEdge(0, 1);    // S - A
        graph.addEdge(0, 2);    // S - B
        graph.addEdge(0, 3);    // S - C
        graph.addEdge(1, 4);    // A - D
        graph.addEdge(2, 4);    // B - D
        graph.addEdge(3, 4);    // C - D
        System.out.print("Breadth First Search: ");
        graph.breadthFirstSearch();
    }
}

Output

Breadth First Search: S A B C D
#Python program for Breadth First Search
# defining MAX 5
MAX = 5
class Vertex:
   def __init__(self, label):
      self.label = label
      self.visited = False
# queue variables
queue = [0] * MAX
rear = -1
front = 0
queueItemCount = 0
# graph variables
#array of vertices
lstVertices = [None] * MAX
#adjacency matrix
adjMatrix = [[0] * MAX for _ in range(MAX)]
#vertex count
vertexCount = 0
# queue functions
def insert(data):
   global rear, queueItemCount
   rear += 1
   queue[rear] = data
   queueItemCount += 1
def removeData():
   global front, queueItemCount
   queueItemCount -= 1
   data = queue[front]
   front += 1
   return data
def isQueueEmpty():
   return queueItemCount == 0
# graph functions
#add vertex to the vertex list
def addVertex(label):
   global vertexCount
   vertex = Vertex(label)
   lstVertices[vertexCount] = vertex
   vertexCount += 1
#add edge to edge array
def addEdge(start, end):
   adjMatrix[start][end] = 1
   adjMatrix[end][start] = 1
#Display the vertex
def displayVertex(vertexIndex):
   print(lstVertices[vertexIndex].label, end=" ")
#Get the adjacent unvisited vertex
def getAdjUnvisitedVertex(vertexIndex):
   for i in range(vertexCount):
      if adjMatrix[vertexIndex][i] == 1 and not lstVertices[i].visited:
         return i
   return -1
def breadthFirstSearch():
    #mark first node as visited
   lstVertices[0].visited = True
   #Display the vertex
   displayVertex(0)
   #insert vertex index in queue
   insert(0)
   while not isQueueEmpty():
    #get the unvisited vertex of vertex which is at front of the queue
      tempVertex = removeData()     
      #no adjacent vertex found
      unvisitedVertex = getAdjUnvisitedVertex(tempVertex)
      while unvisitedVertex != -1:
         lstVertices[unvisitedVertex].visited = True
         displayVertex(unvisitedVertex)
         insert(unvisitedVertex)
         unvisitedVertex = getAdjUnvisitedVertex(tempVertex)     
    #queue is empty, search is complete, reset the visited flag 
   for i in range(vertexCount):
      lstVertices[i].visited = False
# main function
if __name__ == "__main__":
    #set adjacency
   for i in range(MAX):
       #matrix to 0
       for j in range(MAX):
         adjMatrix[i][j] = 0
   addVertex('S')
   addVertex('A')
   addVertex('B')
   addVertex('C')
   addVertex('D')
   addEdge(0, 1)
   addEdge(0, 2)
   addEdge(0, 3)
   addEdge(1, 4)
   addEdge(2, 4)
   addEdge(3, 4)
   print("Breadth First Search: ", end="")
   breadthFirstSearch()

Output

Breadth First Search: S A B C D

Click to check C implementation of Breadth First Search (BFS) Algorithm

Complexity of BFS Algorithm

Time Complexity

The time complexity of the BFS algorithm is represented in the form of O(V + E), where V is the number of nodes and E is the number of edges.

Space Complexity

The space complexity of the BFS algorithm is O(V).