Алгоритм графіків BFS (з кодом на C, C ++, Java та Python)

Зміст

Алгоритм BFS
Приклад BFS
Псевдокод BFS
Приклади Python, Java та C / C ++
Складність алгоритму BFS
Додатки алгоритму BFS

У цьому підручнику ви дізнаєтесь про алгоритм пошуку насамперед по широті. Крім того, ви знайдете робочі приклади алгоритму bfs на C, C ++, Java та Python.

Обхід означає відвідування всіх вузлів графіка. Ширина першого обходу або Ширина першого пошуку - це рекурсивний алгоритм пошуку у всіх вершинах графа або деревоподібної структури.

Алгоритм BFS

Стандартна реалізація BFS включає кожну вершину графіка в одну з двох категорій:

Відвідав
Не відвідували

Мета алгоритму - позначити кожну вершину як відвідану, уникаючи циклів.

Алгоритм працює наступним чином:

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

Графік може мати дві різні відключені частини, тому, щоб переконатися, що ми охоплюємо кожну вершину, ми також можемо запустити алгоритм BFS на кожному вузлі

Приклад BFS

Подивимось, як працює алгоритм Breadth First Search на прикладі. Ми використовуємо неорієнтований графік з 5 вершинами.

Непрямий графік з 5 вершинами

Ми починаємо з вершини 0, алгоритм BFS починається з того, що поміщає його в список відвідуваних і поміщає всі сусідні вершини в стек.

Відвідайте початкову вершину та додайте сусідні вершини до черги

Далі ми відвідуємо елемент в передній частині черги, тобто 1, і переходимо до сусідніх вузлів. Оскільки 0 вже відвідали, замість цього ми відвідуємо 2.

Відвідайте першого сусіда стартового вузла 0, який дорівнює 1

Вершина 2 має невідвідану сусідню вершину в 4, тому ми додаємо її до задньої частини черги та відвідуємо 3, яка знаходиться в передній частині черги.

Візит 2, який був доданий до черги раніше для додавання сусідів

4, залишається в черзі

Лише 4 залишаються в черзі, оскільки єдиний сусідній вузол з 3, тобто 0, вже відвіданий. Ми його відвідуємо.

Відвідайте останній елемент, що залишився в стосі, щоб перевірити, чи немає у нього невідвіданих сусідів

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

Псевдокод BFS

 створити чергу Q позначку v як відвідану і поставити v в Q, поки Q не порожній, видалити головку u позначки Q і поставити в чергу всіх (не відвідуваних) сусідів

Приклади 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; )