Grafični algoritem BFS (s kodo v C, C ++, Java in Python)

Kazalo

BFS algoritem
Primer BFS
BFS psevdokoda
Primeri Python, Java in C / C ++
Zapletenost algoritma BFS
Aplikacije algoritma BFS

V tej vadnici boste spoznali algoritem iskanja po širini. Prav tako boste našli delovne primere algoritma bfs v C, C ++, Java in Python.

Prehod pomeni obisk vseh vozlišč grafa. Breadth First Traversal ali Breadth First Search je rekurzivni algoritem za iskanje vseh točk v grafu ali drevesni strukturi podatkov.

BFS algoritem

Standardna izvedba BFS uvršča vsako oglišče grafa v eno od dveh kategorij:

Obiskano
Ni obiskan

Namen algoritma je označiti vsako oglišče kot obiskano, hkrati pa se izogniti ciklom.

Algoritem deluje na naslednji način:

Najprej postavite katero koli točko grafa na zadnji del čakalne vrste.
Vzemite sprednji element čakalne vrste in ga dodajte na obiskani seznam.
Ustvarite seznam sosednjih vozlišč te točke. Tiste, ki jih ni na obiskanem seznamu, dodajte na zadnji del čakalne vrste.
Ponavljajte koraka 2 in 3, dokler se vrsta ne izprazni.

Graf ima lahko dva različna ločena dela, tako da lahko zagotovimo, da pokrijemo vsako oglišče, lahko tudi algoritem BFS zaženemo na vsakem vozlišču

Primer BFS

Poglejmo, kako algoritem za prvo iskanje v širini deluje s primerom. Uporabljamo neusmerjeni graf s 5 oglišči.

Neusmerjeni graf s 5 oglišči

Izhajamo iz oglišča 0, algoritem BFS se začne tako, da ga uvrstimo na seznam obiskanih in v sosednjo skladbo vstavimo vse njegove sosednje točke.

Obiščite začetno točko in dodajte njene sosednje točke v čakalno vrsto

Nato obiščemo element na sprednji strani čakalne vrste, tj. 1, in pojdimo na sosednja vozlišča. Ker je 0 že obiskano, namesto tega obiščemo 2.

Obiščite prvega soseda začetnega vozlišča 0, ki je 1

Vertex 2 ima v 4 sosednjo točko, ki ni bila obiskana, zato jo dodamo na zadnji del čakalne vrste in obiščemo 3, ki je na sprednji strani čakalne vrste.

Obisk 2, ki je bil prej dodan v čakalno vrsto, da je dodal svoje sosede,

4 ostane v čakalni vrsti

V čakalni vrsti ostanejo samo 4, saj je edino sosednje vozlišče 3, tj. 0, že obiskano. Obiščemo ga.

Obiščite zadnji preostali element v kupčku in preverite, ali ima obiskane sosede

Ker je vrsta prazna, smo zaključili prvo prečkanje širine grafa.

BFS psevdokoda

 ustvari vrsto Q oznake v kot obiskano in vstavi Q v Q, medtem ko Q ni prazen, odstrani glavo u oznake Q in postavi v vrsto vse (neobiskane) sosede u

Primeri Python, Java in C / C ++

Koda algoritma širine prvega iskanja s primerom je prikazana spodaj. Koda je poenostavljena, tako da se lahko osredotočimo na algoritem in ne na druge 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; )