- 1. Алгоритм BFS
- 2. Приклад BFS
- 3. BFS псевдокод
- 4. У BFS
- 5. BFS у C
- 6. BFS у C++
- 7. BFS Java код (Java code)
- 8. BFS у Python
Обхід означає відвідування всіх вузлів графа. «Обхід завширшки» або «Пошук завширшки» (Breadth first traversal or Breadth first Search) - це рекурсивний алгоритм пошуку всіх вершин графа чи деревоподібної структури даних. У цій статті ви познайомитеся з прикладами алгоритму BFS, псевдокода BFS та кодом алгоритму «пошуку завширшки» з реалізацією в програмах на C++, C, Java та Python.
Алгоритм BFS
Стандартна реалізація ВFS містить кожну вершину графа в одну з двох категорій:
- Відвідані.
- Чи не відвідані.
Мета алгоритму - позначити кожну вершину, як відвідану, уникаючи циклів.
Алгоритм працює наступним чином:
- Почніть із розміщення будь-якої вершини графа наприкінці черги.
- Візьміть передній елемент черги та додайте його до списку відвідуваних.
- Створіть перелік суміжних вузлів цієї вершини. Додайте ті, яких немає у списку відвіданих, наприкінці черги.
- Продовжуйте повторювати кроки 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 <stdio.h>
#include <stdlib.h>
#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 <iostream>
#include <list>
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 << "Visited " << currVertex << " ";
queue.pop_front();
for(i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i)
{
int adjVertex = *i;
if(!visited[adjVertex])
{
visited[adjVertex] = true;
queue.push_back(adjVertex);
}
}
}
}
int main()
{
Graph g(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);
g.BFS(2);
return 0;
}
BFS Java код (Java code)
import java.io.*;
import java.util.*;
class Graph
{
private int numVertices;
private LinkedList<Integer> adjLists[];
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 = {0: [1, 2], 1: [2], 2: [3], 3: [1,2]}
breadth_first_search(graph, 0)
это foreach или где?