BFS Graph Algorithm (kóddal C, C ++, Java és Python nyelven)

Tartalomjegyzék

BFS algoritmus
BFS példa
BFS álkód
Példák Python, Java és C / C ++
BFS algoritmus komplexitás
BFS algoritmus alkalmazások

Ebben az oktatóanyagban megismerheti a szélesebb körű első keresési algoritmust. A BFS algoritmusról működő példákat is talál C, C ++, Java és Python nyelven.

A bejárás azt jelenti, hogy meglátogatja a gráf összes csomópontját. A Breadth First Traversal vagy a Breadth First Search egy rekurzív algoritmus egy grafikon vagy fa adatszerkezet összes csúcsának keresésére.

BFS algoritmus

A BFS szabványos megvalósítása a grafikon minden csúcsát a két kategória egyikébe sorolja:

Meglátogatott
Nincs meglátogatva

Az algoritmus célja, hogy minden csúcsot meglátogatottként jelöljön meg, miközben elkerüli a ciklusokat.

Az algoritmus a következőképpen működik:

Kezdje azzal, hogy a gráf bármelyik csúcsát a sor hátuljába teszi.
Vegye ki a sor elejét, és vegye fel a meglátogatott listára.
Hozzon létre egy listát a csúcs szomszédos csomópontjairól. Adja hozzá azokat, amelyek nem szerepelnek a felkeresett listán, a sor hátuljába.
Addig ismételje a 2. és a 3. lépést, amíg a sor üres nem lesz.

A grafikonnak két különálló része lehet, így annak biztosítása érdekében, hogy minden csúcsot lefedjünk, minden csomóponton futtathatjuk a BFS algoritmust is

BFS példa

Nézzük meg, hogyan működik a Breadth First Search algoritmus egy példával. 5 irányú irányítatlan grafikont használunk.

Irányítatlan gráf 5 csúccsal

A 0 csúcsból indulunk ki, a BFS algoritmus azzal kezdődik, hogy felteszi a Visited listába, és az összes szomszédos csúcsát a verembe rakja.

Látogassa meg a start csúcsot, és adja hozzá a szomszédos csúcsokat a sorba

Ezután meglátogatjuk a sor elején lévő elemet, azaz az 1-et, és elmegyünk a szomszédos csomópontokhoz. Mivel a 0 már meglátogatott, helyette 2-et látogatunk meg.

Látogassa meg a 0 kezdőcsomópont első szomszédját, amely 1

A 2. csúcsnak van egy meglátogatatlan szomszédos csúcsa a 4-ben, ezért hozzáadjuk ezt a sor hátuljához, és meglátogatjuk a 3-at, amely a sor elején van.

Látogassa meg a 2. látogatást, amelyet korábban a várólistához adtak, hogy hozzáadják a szomszédjait.

4 továbbra is a sorban marad

Csak 4 maradt a sorban, mivel az egyetlen szomszédos 3, azaz 0 csomópont már meglátogatott. Meglátogatjuk.

Látogassa meg a verem utolsó megmaradt elemét, hogy ellenőrizze, vannak-e látogatatlan szomszédjai

Mivel a sor üres, befejeztük a grafikon Szélesség első bejárását.

BFS álkód

 hozzon létre egy várólistát Q v jelölésként, és tegye v-t Q-ba, amíg Q nem üres, távolítsa el a Q jel u fejét, és vonja le az összes (nem látogatott) szomszédot

Példák Python, Java és C / C ++

Az alábbiakban látható a Breadth First Search algoritmus kódja egy példával. A kódot leegyszerűsítettük, hogy más részletek helyett az algoritmusra koncentrálhassunk.

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