Breadth first search cpp

Breadth first search (BFS) and Depth first search (DFS) for a Graph in C++

In this tutorial we will learn about the traversal (or search) of the graph by using the two approaches, one is the breadth-first search (BFS) and another one is depth-first search (DFS). Here we will also see the algorithm used for BFS and DFS.

In BFS, we start with the starting node and explores all the neighbouring node and then select the one by one neighbouring nodes(using queue) and explores its unvisited neighbouring nodes. While in DFS we go to depth as possible from starting node.

BFS and DFS for the Graph

First, we will look at the algorithm for BFS.

1. Take the empty queue and bool type array (visit) initialise with FALSE.
2. Push the starting node in the queue and set the value TRUE for this node in visited array.
3. Pop out the front node of the queue and print the node.
4. Push the adjacent node of pop node in queue which are not visited. Set the value TRUE in visited array of adding node.
5. Repeat step 3 and 4 until the queue becomes empty.

Now we will look on the algorithm for DFS.

1. Take the empty stack and bool type array (visit) initialise with FALSE.
2. Push the starting node in the stack and set the value TRUE for this node in visited array.
3. Pop the top node from the stack and print that node.
4. Push the adjacent node of pop node in the stack which is not visited. Set the value TRUE in visited array of adding node.
5. Repeat step 3 and 4until the stack becomes empty.

So, here we also look that the BFS and DFS algorithm is mostly similar in above iterative approaches, only one difference is that in BFS that we will use the queue and in DFS we will use the stack because need goes to depth for DFS.

Implementation of the graph is by the method of an adjacency list. Therefore Implementation of adjacency list is by the using of the vector of an array:-

vectoradj[5]; //vector of array to store the edge

C++ code implementation for BFS and DFS :-

#include #include #include #include using namespace std; //add the edge in graph void edge(vectoradj[],int u,int v) < adj[u].push_back(v); >//function for bfs traversal void bfs(int s,vectoradj[],bool visit[])< queueq;//queue in STL q.push(s); visit[s]=true; while(!q.empty()) < int u=q.front(); cout> > > //function for dfs traversal void dfs(int s,vectoradj[],bool visit[])< stackstk;//stack in STL stk.push(s); visit[s]=true; while(!stk.empty()) < int u=stk.top(); cout> > > //main function int main()< vectoradj[5];//vector of array to store the graph bool visit[5];//array to check visit or not of a node //initially all node are unvisited for(int i=0;i <5;i++)< visit[i]=false; >//input for edges edge(adj,0,2); edge(adj,0,1); edge(adj,1,3); edge(adj,2,0); edge(adj,2,3); edge(adj,2,4); cout cout

The output of our program is given below:

BFS traversal is 0 2 1 3 4 DFS traversal is 0 1 3 2 4

Important aspects:-

• Dfs takes less memory space, therefore, DFS is better than BFS.
• We can find the goal node fastly in DFS.
• For large network due to reoccurring of node, no guarantee to find the node in DFS but in BFS, we are definitely found the goal node.

Источник

Поиск в ширину (Breadth first search, BFS)

Обход означает посещение всех узлов графа. «Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) — это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье вы познакомитесь с примерами алгоритма BFS, псевдокода BFS и кодом алгоритма «поиска в ширину» с реализацией в программах на C ++, C, Java и Python.

Алгоритм BFS

Цель алгоритма — пометить каждую вершину, как посещенную, избегая циклов.

Алгоритм работает следующим образом:

1. Начните с размещения любой вершины графа в конце очереди.
2. Возьмите передний элемент очереди и добавьте его в список посещенных.
3. Создайте список смежных узлов этой вершины. Добавьте те, которых нет в списке посещенных, в конец очереди.
4. Продолжайте повторять шаги 2 и 3, пока очередь не опустеет.

Граф может иметь две разные несвязанные части, поэтому, чтобы убедиться, что мы покрываем каждую вершину, мы также можем запустить алгоритм BFS на каждом узле.

Пример BFS

Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.

Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.

Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.

У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.

В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.

Поскольку очередь пуста, мы завершили обход в ширину графика.

BFS псевдокод

create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u
 
Код BFS
 
Код для алгоритма «поиска в ширину» с примером показан ниже. Код был упрощен, поэтому мы можем сосредоточиться на алгоритме, а не на других деталях.
 
BFS в C
 
#include #include #define SIZE 40 struct queue < int items[SIZE]; int front; int rear; >; struct queue* createQueue(); void enqueue(struct queue* q, int); int dequeue(struct queue* q); void display(struct queue* q); int isEmpty(struct queue* q); void printQueue(struct queue* q); struct node < int vertex; struct node* next; >; struct node* createNode(int); struct Graph < int numVertices; struct node** adjLists; int* visited; >; struct Graph* createGraph(int vertices); void addEdge(struct Graph* graph, int src, int dest); void printGraph(struct Graph* graph); void bfs(struct Graph* graph, int startVertex); int main() < struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0; >void bfs(struct Graph* graph, int startVertex) < struct queue* q = createQueue(); graph->visited[startVertex] = 1; enqueue(q, startVertex); while(!isEmpty(q))< printQueue(q); int currentVertex = dequeue(q); printf("Visited %d\n", currentVertex); struct node* temp = graph->adjLists[currentVertex]; while(temp) < int adjVertex = temp->vertex; if(graph->visited[adjVertex] == 0)< graph->visited[adjVertex] = 1; enqueue(q, adjVertex); > temp = temp->next; > > > struct node* createNode(int v) < struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; > struct Graph* createGraph(int vertices) < struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) < graph->adjLists[i] = NULL; graph->visited[i] = 0; > return graph; > void addEdge(struct Graph* graph, int src, int dest) < // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; > struct queue* createQueue() < struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; > int isEmpty(struct queue* q) < if(q->rear == -1) return 1; else return 0; > void enqueue(struct queue* q, int value)< if(q->rear == SIZE-1) printf("\nQueue is Full!!"); else < if(q->front == -1) q->front = 0; q->rear++; q->items[q->rear] = value; > > int dequeue(struct queue* q) < int item; if(isEmpty(q))< printf("Queue is empty"); item = -1; >else< item = q->items[q->front]; q->front++; if(q->front > q->rear)< printf("Resetting queue"); q->front = q->rear = -1; > > return item; > void printQueue(struct queue *q) < int i = q->front; if(isEmpty(q)) < printf("Queue is empty"); >else < printf("\nQueue contains \n"); for(i = q->front; i < q->rear + 1; i++) < printf("%d ", q->items[i]); > > >
 
BFS в C++
 
#include #include using namespace std; class Graph < int numVertices; list *adjLists; bool* visited; public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex); >; Graph::Graph(int vertices) < numVertices = vertices; adjLists = new list[vertices]; >void Graph::addEdge(int src, int dest) < adjLists[src].push_back(dest); adjLists[dest].push_back(src); >void Graph::BFS(int startVertex) < visited = new bool[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; list queue; visited[startVertex] = true; queue.push_back(startVertex); list::iterator i; while(!queue.empty()) < int currVertex = queue.front(); cout > > > int main()
 
BFS Java код (Java code)
 
import java.io.*; import java.util.*; class Graph < private int numVertices; private LinkedListadjLists[]; private boolean visited[]; Graph(int v) < numVertices = v; visited = new boolean[numVertices]; adjLists = new LinkedList[numVertices]; for (int i=0; i i = adjLists[currVertex].listIterator(); while (i.hasNext()) < int adjVertex = i.next(); if (!visited[adjVertex]) < visited[adjVertex] = true; queue.add(adjVertex); >> > > public static void main(String args[]) < Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal "+ "(starting from vertex 2)"); g.BFS(2); >>
 
BFS в Python
 
import collections def bfs(graph, root): visited, queue = set(), collections.deque([root]) visited.add(root) while queue: vertex = queue.popleft() for neighbour in graph[vertex]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = breadth_first_search(graph, 0)
 
 
Рекомендуем хостинг TIMEWEB
 
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
 
Рекомендуемые статьи по этой тематике
 
По статье задано0 вопрос(ов) 
 
Вам это нравится? Поделитесь в социальных сетях!
 
Источник
 
Breadth First Search (BFS) in C++
 
Breadth First Search (BFS) is an algorithm for traversing or searching a graph data structure. It is one of the most basic and fundamental search algorithms, and is often used as a starting point for other algorithms. In this post, we will discuss Breadth First Search in C++, including how it works, how to implement it, and some examples.
 
What is Breadth First Search?
 
Breadth First Search (BFS) is an algorithm for traversing or searching a graph data structure. It is one of the most basic and fundamental search algorithms, and is often used as a starting point for other algorithms. BFS works by starting at a root node, and then exploring all of the nodes at the same depth before moving down to the next level. This process is repeated until the goal node is found, or until all of the nodes have been explored.
 
The basic idea behind BFS is that it looks at all of the nodes at the current level before moving on to the next level. This means that the algorithm will look at all of the nodes connected to the root node before looking at any other nodes. As a result, BFS is often used for finding the shortest path between two nodes in a graph.
 
How to Implement BFS in C++?
 
BFS can be implemented in C++ by using a queue data structure. A queue is a First-In-First-Out (FIFO) data structure, which means that the first item added to the queue is the first item to be removed. This is similar to a line of people waiting to enter a store, where the first person in line is the first person to be served.
 
In order to implement BFS in C++, we will need to create a queue to store the nodes that we have yet to visit. We will also need to create a boolean array to keep track of which nodes have been visited. This array will help us avoid getting stuck in an infinite loop by only visiting nodes once.
 
We can then create a function that takes in the root node and the goal node as parameters. This function will add the root node to the queue and mark it as visited. We then loop over the queue, and for each node in the queue we check if it is the goal node. If it is not, we add all of its adjacent nodes to the queue and mark them as visited. We then repeat this process until we find the goal node or until the queue is empty.
 
Example
 
Let’s look at an example of how to implement BFS in C++ with the following graph:
 
 
We will start with the root node, which is A . We then add A to the queue and mark it as visited. We then loop over the queue and check if A is the goal node. Since it is not, we add its adjacent nodes, B and C , to the queue and mark them as visited.
 
Next, we loop over the queue again and check if either B or C is the goal node. Since they are not, we add their adjacent nodes, D and E , to the queue and mark them as visited. We then repeat this process until we find the goal node or until the queue is empty. In this case, the goal node is F , which is the fourth node to be visited.
 
The C++ code for this example is as follows:
 
#include  #include using namespace std; const int MAX = 6; // Array to keep track of visited nodes bool visited[MAX] = false>; // Function to implement Breadth First Search void BFS(int adjMatrix[][MAX], int start)  // Create a queue to store the nodes queueint> q; // Mark the start node as visited visited[start] = true; // Add the start node to the queue q.push(start); // Loop until the queue is empty while (!q.empty())  // Get the first node in the queue int node = q.front(); q.pop(); // Print the visited node cout  <node  <" "; // Check if the adjacent nodes have been visited for (int i = 0; i  MAX; i++)  if (adjMatrix[node][i] == 1 && !visited[i])  // Mark the adjacent node as visited visited[i] = true; // Add the adjacent node to the queue q.push(i); > > > > int main()  // Create an adjacency matrix int adjMatrix[MAX][MAX] =  0, 1, 1, 0, 0, 0>, 1, 0, 0, 1, 0, 0>, 1, 0, 0, 1, 0, 0>, 0, 1, 1, 0, 1, 0>, 0, 0, 0, 1, 0, 1>, 0, 0, 0, 0, 1, 0> >; // Start the BFS at node 0 BFS(adjMatrix, 0); return 0; > 
 
Conclusion
 
In this post, we discussed Breadth First Search (BFS) in C++, including how it works, how to implement it, and an example. BFS is a powerful algorithm for traversing or searching a graph data structure and can be used for finding the shortest path between two nodes in a graph. We implemented BFS in C++ by using a queue data structure and a boolean array to keep track of which nodes have been visited.
 
Copyright © 2022 helpful.codes
 
Источник