Algoritmus grafu BFS (s kódem v C, C ++, Javě a Pythonu)

Obsah

Algoritmus BFS
Příklad BFS
BFS pseudokód
Python, Java a C / C ++ příklady
Složitost algoritmu BFS
Algoritmické aplikace BFS

V tomto kurzu se dozvíte o algoritmu pro vyhledávání prvního šíře. Pracovní příklady algoritmu bfs najdete také v jazycích C, C ++, Java a Python.

Traverz znamená navštívit všechny uzly grafu. Breadth First Traversal nebo Breadth First Search je rekurzivní algoritmus pro prohledávání všech vrcholů grafu nebo stromové datové struktury.

Algoritmus BFS

Standardní implementace BFS staví každý vrchol grafu do jedné ze dvou kategorií:

Navštíveno
Není navštěvováno

Účelem algoritmu je označit každý vrchol jako navštívený a vyhnout se cyklům.

Algoritmus funguje následovně:

Začněte umístěním kteréhokoli z vrcholů grafu na zadní stranu fronty.
Vezměte přední položku fronty a přidejte ji do seznamu navštívených.
Vytvořte seznam sousedních uzlů tohoto vrcholu. Přidejte ty, které nejsou v seznamu navštívených, do zadní části fronty.
Opakujte kroky 2 a 3, dokud fronta není prázdná.

Graf může mít dvě různé odpojené části, abychom se ujistili, že pokryjeme každý vrchol, můžeme také spustit algoritmus BFS na každém uzlu

Příklad BFS

Podívejme se, jak algoritmus Breadth First Search funguje na příkladu. Používáme neorientovaný graf s 5 vrcholy.

Neusměrněný graf s 5 vrcholy

Začínáme od vrcholu 0, algoritmus BFS začíná vložením do seznamu Navštíveno a vložením všech jeho sousedních vrcholů do zásobníku.

Navštivte počáteční vrchol a přidejte jeho sousední vrcholy do fronty

Dále navštívíme prvek v přední části fronty, tj. 1 a přejdeme do jeho sousedních uzlů. Protože 0 již byla navštívena, navštěvujeme místo toho 2.

Navštivte prvního souseda počátečního uzlu 0, což je 1

Vrchol 2 má nenavštívený sousední vrchol ve 4, takže přidáme, že do zadní části fronty a návštěva 3, která je v přední části fronty.

Navštivte 2, která byla přidána do fronty dříve, abyste přidali své sousedy

4, zůstává ve frontě

Ve frontě zůstávají pouze 4, protože jediný sousední uzel 3, tj. 0, je již navštíven. Navštěvujeme to.

Navštivte poslední zbývající položku v zásobníku a zkontrolujte, zda nemá neviděné sousedy

Vzhledem k tomu, že fronta je prázdná, dokončili jsme Breadth First Traversal grafu.

BFS pseudokód

 vytvořte frontu Q značka v jako navštívená a vložte v do Q, zatímco Q není prázdná, odstraňte hlavu u značky Q a zařadí všechny (nenavštívené) sousedy u

Python, Java a C / C ++ příklady

Níže je uveden kód algoritmu pro vyhledávání prvního šířky s příkladem. Kód byl zjednodušen, takže se můžeme soustředit spíše na algoritmus než na další podrobnosti.

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