Algorytm BFS Graph (z kodem w C, C ++, Java i Pythonie)

Spisie treści

Algorytm BFS
Przykład BFS
Pseudokod BFS
Przykłady w Pythonie, Javie i C / C ++
Złożoność algorytmu BFS
Aplikacje algorytmów BFS

W tym samouczku dowiesz się o algorytmie wyszukiwania wszerz. Znajdziesz również działające przykłady algorytmu bfs w językach C, C ++, Java i Python.

Przechodzenie oznacza odwiedzanie wszystkich węzłów wykresu. Breadth First Traversal lub Breadth First Search to rekurencyjny algorytm przeszukiwania wszystkich wierzchołków wykresu lub struktury danych drzewa.

Algorytm BFS

Standardowa implementacja BFS umieszcza każdy wierzchołek grafu w jednej z dwóch kategorii:

Odwiedziłem
Nie odwiedzono

Celem algorytmu jest oznaczenie każdego wierzchołka jako odwiedzonego z jednoczesnym unikaniem cykli.

Algorytm działa w następujący sposób:

Zacznij od umieszczenia dowolnego wierzchołka wykresu z tyłu kolejki.
Weź pierwszą pozycję kolejki i dodaj ją do listy odwiedzonych.
Utwórz listę sąsiednich węzłów tego wierzchołka. Dodaj te, których nie ma na liście odwiedzonych, na koniec kolejki.
Powtarzaj kroki 2 i 3, aż kolejka będzie pusta.

Graf może mieć dwie różne odłączone części, więc aby upewnić się, że pokryjemy każdy wierzchołek, możemy również uruchomić algorytm BFS na każdym węźle

Przykład BFS

Zobaczmy, jak działa algorytm Breadth First Search na przykładzie. Używamy nie skierowanego grafu z 5 wierzchołkami.

Nie skierowany graf z 5 wierzchołkami

Zaczynamy od wierzchołka 0, algorytm BFS zaczyna od umieszczenia go na liście Odwiedzonych i umieszczenia wszystkich sąsiednich wierzchołków na stosie.

Odwiedź wierzchołek początkowy i dodaj jego sąsiednie wierzchołki do kolejki

Następnie odwiedzamy element na początku kolejki tj. 1 i przechodzimy do jego sąsiednich węzłów. Ponieważ 0 zostało już odwiedzone, zamiast tego odwiedzamy 2.

Odwiedź pierwszego sąsiada węzła początkowego 0, czyli 1

Wierzchołek 2 ma nieodwiedzony sąsiedni wierzchołek w 4, więc dodajemy go z tyłu kolejki i odwiedzamy 3, który znajduje się na początku kolejki.

Wizyta 2, która została wcześniej dodana do kolejki w celu dodania sąsiadów

4, pozostaje w kolejce

W kolejce pozostaje tylko 4, ponieważ jedyny sąsiedni węzeł o wartości 3, czyli 0, jest już odwiedzony. Odwiedzamy to.

Odwiedź ostatni pozostały przedmiot w stosie, aby sprawdzić, czy nie ma nie odwiedzonych sąsiadów

Ponieważ kolejka jest pusta, zakończyliśmy pierwszy krok szerokości wykresu.

Pseudokod BFS

 utwórz kolejkę Q zaznacz v jako odwiedzoną i umieść v w Q, gdy Q jest niepusty usuń nagłówek u znaku Q i umieść w kolejce wszystkich (nie odwiedzonych) sąsiadów u

Przykłady w Pythonie, Javie i C / C ++

Kod algorytmu Breadth First Search wraz z przykładem pokazano poniżej. Kod został uproszczony, abyśmy mogli skupić się na algorytmie, a nie na innych szczegółach.

Python Java 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; )