BFS graafi algoritm (koodiga C, C ++, Java ja Python)

Lang L: none (table-of-contents)

BFS-i algoritm
BFS näide
BFS-i pseudokood
Pythoni, Java ja C / C ++ näited
BFS-i algoritmi keerukus
BFS-i algoritmirakendused

Selles õpetuses saate teada esimese otsingu algoritmi kohta. Samuti leiate toimivaid näiteid bfs-algoritmist C, C ++, Java ja Python.

Läbimine tähendab graafiku kõigi sõlmede külastamist. Breadth First Traversal ehk Breadth First Search on rekursiivne algoritm graafiku või puu andmestruktuuri kõigi tippude otsimiseks.

BFS-i algoritm

BFS-i standardne juurutamine paigutab graafiku iga tipu ühte kahest kategooriast:

Külastatud
Pole külastatud

Algoritmi eesmärk on märkida iga tipp külastatuna, vältides tsükleid.

Algoritm töötab järgmiselt:

Alustuseks pange ükskõik milline graafi tipp järjekorra taha.
Võtke järjekorra esikülg ja lisage see külastatud loendisse.
Looge selle tipu külgnevate sõlmede loend. Lisage need, mida pole külastatud loendis, järjekorra taha.
Korrake 2. ja 3. toimingut seni, kuni järjekord on tühi.

Graafil võib olla kaks erinevat lahti ühendatud osa, nii et iga tipu katmise tagamiseks saame BFS-i algoritmi käivitada ka igas sõlmes

BFS näide

Vaatame, kuidas töötab Breadth First Search algoritm koos näitega. Kasutame 5 tipuga suunamata graafi.

5 tipuga suunamata graaf

Alustame tipust 0, BFS-i algoritm algab selle panemisest loendisse Visited ja kõigi selle kõrvuti asetsevate tippude virna panemisest.

Külastage algustippu ja lisage selle kõrval olevad tipud järjekorda

Järgmisena külastame järjekorra esiosas olevat elementi 1 ja läheme selle külgnevatesse sõlmedesse. Kuna 0 on juba külastatud, siis külastame hoopis 2.

Külastage stardisõlme 0 esimest naabrit, milleks on 1

Tipul 2 on külastamata külgnev tipp neljas, nii et lisame selle järjekorra taha ja külastame 3, mis asub järjekorra ees.

2. visiit, mis lisati järjekorda varem, et lisada naabrid

4, jääb järjekorda

Järjekorda jääb ainult 4, kuna ainsat kõrvuti asetsevat 3 st 0 sõlme on juba külastatud. Me külastame seda.

Külastage virna viimast järelejäänud üksust ja kontrollige, kas sellel on külastamata naabreid

Kuna järjekord on tühi, oleme graafiku esimese laiuse esimese läbimise lõpetanud.

BFS-i pseudokood

 luua järjekord Q märk v külastatuna ja panna v Q-sse, kui Q pole tühi, eemaldage Q-märgi u ja eemaldage kõik u (külastamata) naabrid

Pythoni, Java ja C / C ++ näited

Allpool on näidatud laiusega esimese otsingu algoritmi kood koos näitega. Koodi on lihtsustatud, et saaksime keskenduda algoritmile, mitte muudele üksikasjadele.

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