Графичен алгоритъм на BFS (с код на C, C ++, Java и Python)

Съдържание

BFS алгоритъм
Пример за BFS
BFS псевдокод
Примери за Python, Java и C / C ++
Сложност на алгоритъма на BFS
Приложения на BFS алгоритъм

В този урок ще научите за алгоритъма за първо търсене по ширина. Също така ще намерите работещи примери за bfs алгоритъм в C, C ++, Java и Python.

Обхождането означава посещение на всички възли на графика. Breadth First Traversal или Breadth First Search е рекурсивен алгоритъм за търсене във всички върхове на графика или дървовидна структура от данни.

BFS алгоритъм

Стандартно изпълнение на BFS поставя всеки връх на графиката в една от двете категории:

Посетен
Не е посетен

Целта на алгоритъма е да маркира всеки връх като посетен, като същевременно се избягват цикли.

Алгоритъмът работи по следния начин:

Започнете, като поставите някой от върховете на графиката в задната част на опашката.
Вземете предния елемент на опашката и го добавете към посетения списък.
Създайте списък със съседните възли на този връх. Добавете тези, които не са в посетения списък, в задната част на опашката.
Продължавайте да повтаряте стъпки 2 и 3, докато опашката не се изпразни.

Графиката може да има две различни несвързани части, така че за да сме сигурни, че покриваме всеки връх, можем също така да изпълним алгоритъма BFS на всеки възел

Пример за BFS

Нека да видим как работи алгоритъмът за първо търсене на широчина с един пример. Използваме неориентирана графика с 5 върха.

Ненасочена графика с 5 върха

Започваме от връх 0, алгоритъмът на BFS започва, като го поставя в списъка Visited и поставя всички съседни върхове в стека.

Посетете началния връх и добавете съседните му върхове към опашката

След това посещаваме елемента в предната част на опашката, т.е. 1 и отиваме в съседните му възли. Тъй като 0 вече е посетен, вместо него посещаваме 2.

Посетете първия съсед на началния възел 0, който е 1

Vertex 2 има непосетен съседен връх в 4, така че добавяме това към задната част на опашката и посещаваме 3, която е в предната част на опашката.

Посещение 2, което е добавено в опашката по-рано, за да добави своите съседи

4, остава в опашката

В опашката остават само 4, тъй като единственият съседен възел от 3, т.е. 0, вече е посетен. Посещаваме го.

Посетете последния останал елемент в стека, за да проверите дали той не е посещавал съседи

Тъй като опашката е празна, завършихме Първото обръщане на широчината на графиката.

BFS псевдокод

 създайте опашка Q марка v като посетена и поставете v в Q, докато Q не е празна, премахнете главата u на Q марка и поставете в опашка всички (непосетени) съседи на u

Примери за Python, Java и C / C ++

Кодът за алгоритъма за първо търсене на широчина с пример е показан по-долу. Кодът е опростен, за да можем да се съсредоточим върху алгоритъма, а не върху други подробности.

Python Java C C +

 # BFS algorithm in Python import collections # BFS algorithm def bfs(graph, root): visited, queue = set(), collections.deque((root)) visited.add(root) while queue: # Dequeue a vertex from queue vertex = queue.popleft() print(str(vertex) + " ", end="") # If not visited, mark it as visited, and # enqueue it 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)) print("Following is Breadth First Traversal: ") bfs(graph, 0)

 // BFS algorithm in Java import java.util.*; public class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int v) ( V = v; adj = new LinkedList(v); for (int i = 0; i < v; ++i) adj(i) = new LinkedList(); ) // Add edges to the graph void addEdge(int v, int w) ( adj(v).add(w); ) // BFS algorithm void BFS(int s) ( boolean visited() = new boolean(V); LinkedList queue = new LinkedList(); visited(s) = true; queue.add(s); while (queue.size() != 0) ( s = queue.poll(); System.out.print(s + " "); Iterator i = adj(s).listIterator(); while (i.hasNext()) ( int n = i.next(); if (!visited(n)) ( visited(n) = true; queue.add(n); ) ) ) ) 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 algorithm in 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; ); // BFS algorithm 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", 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; ) ) ) // Creating a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Creating a graph 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 adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge 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; ) // Create a queue struct queue* createQueue() ( struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; ) // Check if the queue is empty int isEmpty(struct queue* q) ( if (q->rear == -1) return 1; else return 0; ) // Adding elements into queue void enqueue(struct queue* q, int value) ( if (q->rear == SIZE - 1) printf("Queue is Full!!"); else ( if (q->front == -1) q->front = 0; q->rear++; q->items(q->rear) = value; ) ) // Removing elements from queue 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; ) // Print the queue void printQueue(struct queue* q) ( int i = q->front; if (isEmpty(q)) ( printf("Queue is empty"); ) else ( printf("Queue contains "); for (i = q->front; i rear + 1; i++) ( printf("%d ", q->items(i)); ) ) ) 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; )

 // BFS algorithm in 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); ); // Create a graph with given vertices, // and maintain an adjacency list Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); ) // Add edges to the graph void Graph::addEdge(int src, int dest) ( adjLists(src).push_back(dest); adjLists(dest).push_back(src); ) // BFS algorithm 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; )