BFS-kaavion algoritmi (koodilla C, C ++, Java ja Python)

Tässä opetusohjelmassa opit ensimmäisen hakualgoritmin laajuudesta. Löydät myös toimivia esimerkkejä bfs-algoritmista C, C ++, Java ja Python.

Liikkuminen tarkoittaa käyntiä kaavion kaikissa solmuissa. Laajuuden ensimmäinen läpikulku tai Breadth First -haku on rekursiivinen algoritmi kaavion tai puun tietorakenteen kaikkien huippujen etsimiseen.

BFS-algoritmi

Tavallinen BFS-toteutus sijoittaa kaavion jokaisen kärjen kahteen luokkaan:

Vieraillut
Ei käynyt

Algoritmin tarkoituksena on merkitä kukin kärkipiste vierailuksi välttäen syklejä.

Algoritmi toimii seuraavasti:

Aloita asettamalla mikä tahansa kaavion kärjestä jonon takaosaan.
Ota jonon etuosa ja lisää se vierailukohteiden luetteloon.
Luo luettelo kyseisen kärjen vierekkäisistä solmuista. Lisää ne, jotka eivät ole vierailukohteiden luettelossa, jonon takaosaan.
Toista vaiheita 2 ja 3, kunnes jono on tyhjä.

Kaaviossa voi olla kaksi erilaista irrotettua osaa, joten varmistaaksemme, että peitämme jokaisen kärjen, voimme myös suorittaa BFS-algoritmin jokaisessa solmussa

BFS-esimerkki

Katsotaanpa, kuinka Breadth First Search -algoritmi toimii esimerkin kanssa. Käytämme suuntaamatonta kuvaajaa, jossa on 5 kärkeä.

Ohjaamaton kaavio, jossa 5 kärkeä

Aloitetaan huipusta 0, BFS-algoritmi alkaa asettamalla se Visited-luetteloon ja asettamalla kaikki sen vierekkäiset pisteet pinoon.

Käy aloituspisteessä ja lisää sen vierekkäiset kärjet jonoon

Seuraavaksi käymme jonon edessä olevassa elementissä eli 1 ja menemme sen vierekkäisiin solmuihin. Koska 0 on jo käynyt, käymme sen sijaan 2: ssa.

Käy aloitussolmun 0 ensimmäisen naapurin kanssa, joka on 1

Vertex 2: lla on avaamaton vierekkäinen kärki 4: ssä, joten lisätään se jonon takaosaan ja käy 3, joka on jonon edessä.

Käy 2, joka lisättiin jonoon aiemmin lisätäksesi naapurit

4 pysyy jonossa

Vain 4 on jonossa, koska ainoa vierekkäinen solmu 3 eli 0 on jo käynyt. Käymme siellä.

Käy pinon viimeisimmässä jäljellä olevassa tuotteessa ja tarkista, onko sillä vieraita naapureita

Koska jono on tyhjä, olemme suorittaneet kaavion leveyden ensimmäisen läpikulun.

BFS-pseudokoodi

 luo jono Q-merkki v vierailun aikana ja laita v Q: seen, kun Q on tyhjä, poista Q-merkin pää u ja vie kaikki u: n (vierailemattomat) naapurit

Python-, Java- ja C / C ++ -esimerkkejä

Laajuuden ensimmäisen haun algoritmin koodi ja esimerkki on esitetty alla. Koodia on yksinkertaistettu, jotta voimme keskittyä algoritmiin muiden yksityiskohtien sijaan.

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