Σε αυτό το σεμινάριο, θα μάθετε για τον αλγόριθμο πρώτης αναζήτησης. Επίσης, θα βρείτε λειτουργικά παραδείγματα αλγορίθμου bfs σε C, C ++, Java και Python.
Διασταύρωση σημαίνει επίσκεψη σε όλους τους κόμβους ενός γραφήματος. Breadth First Traversal ή Breadth First Search είναι ένας αναδρομικός αλγόριθμος για την αναζήτηση όλων των κορυφών ενός γραφήματος ή μιας δομής δεδομένων δέντρου.
Αλγόριθμος BFS
Μια τυπική εφαρμογή BFS τοποθετεί κάθε κορυφή του γραφήματος σε μία από τις δύο κατηγορίες:
- Επισκέφτηκε
- Δεν έχει επισκεφθεί
Ο σκοπός του αλγορίθμου είναι να επισημάνει κάθε κορυφή ως επισκέφθηκε, αποφεύγοντας κύκλους.
Ο αλγόριθμος λειτουργεί ως εξής:
- Ξεκινήστε βάζοντας οποιαδήποτε από τις κορυφές του γραφήματος στο πίσω μέρος μιας ουράς.
- Πάρτε το μπροστινό στοιχείο της ουράς και προσθέστε το στη λίστα επισκέψεων.
- Δημιουργήστε μια λίστα με τους γειτονικούς κόμβους αυτής της κορυφής. Προσθέστε αυτά που δεν περιλαμβάνονται στη λίστα επισκέψεων στο πίσω μέρος της ουράς.
- Συνεχίστε να επαναλαμβάνετε τα βήματα 2 και 3 έως ότου η ουρά είναι κενή.
Το γράφημα μπορεί να έχει δύο διαφορετικά αποσυνδεδεμένα μέρη, ώστε να διασφαλίσουμε ότι καλύπτουμε κάθε κορυφή, μπορούμε επίσης να εκτελέσουμε τον αλγόριθμο BFS σε κάθε κόμβο
Παράδειγμα BFS
Ας δούμε πώς λειτουργεί ο αλγόριθμος Breadth First Search με ένα παράδειγμα. Χρησιμοποιούμε ένα μη κατευθυνόμενο γράφημα με 5 κορυφές.
Μη κατευθυνόμενο γράφημα με 5 κορυφές
Ξεκινάμε από την κορυφή 0, ο αλγόριθμος BFS ξεκινά τοποθετώντας τον στη λίστα Επίσκεψη και βάζοντας όλες τις γειτονικές κορυφές του στη στοίβα.
Επισκεφθείτε την αρχή εκκίνησης και προσθέστε τις γειτονικές κορυφές της στην ουρά
Στη συνέχεια, επισκέπτουμε το στοιχείο στο μπροστινό μέρος της ουράς δηλαδή 1 και πηγαίνουμε στους γειτονικούς κόμβους του. Δεδομένου ότι το 0 έχει ήδη επισκεφθεί, επισκεφθούμε 2.
Επισκεφτείτε τον πρώτο γείτονα του κόμβου έναρξης 0, που είναι 1
Το Vertex 2 έχει μια μη ελεγμένη γειτονική κορυφή στο 4, οπότε το προσθέτουμε στο πίσω μέρος της ουράς και επισκεφθούμε το 3, το οποίο βρίσκεται στο μπροστινό μέρος της ουράς.
Επισκεφτείτε το 2 που προστέθηκε στην ουρά νωρίτερα για να προσθέσετε τους γείτονές του 
4 παραμένει στην ουρά
Μόνο 4 παραμένουν στην ουρά αφού ο μοναδικός γειτονικός κόμβος του 3 δηλ. 0 έχει ήδη επισκεφτεί. Το επισκεφτούμε.
Επισκεφτείτε το τελευταίο εναπομείναν στοιχείο στη στοίβα για να ελέγξετε αν έχει γείτονες που δεν έχουν επισκεφθεί
Δεδομένου ότι η ουρά είναι κενή, ολοκληρώσαμε το Breadth First Traversal του γραφήματος.
Ψευδοκώδικας BFS
δημιουργήστε μια ουρά Q mark v όπως επισκεφτήκατε και βάλτε το v στο Q ενώ το Q δεν είναι κενό αφαιρέστε την κεφαλή u του Q και ενεργοποιήστε όλους τους (μη ελεγμένους) γείτονες του u
Παραδείγματα Python, Java και C / C ++
Ο κωδικός για τον αλγόριθμο Πρώτης Αναζήτησης Breadth με ένα παράδειγμα φαίνεται παρακάτω. Ο κώδικας έχει απλοποιηθεί ώστε να μπορούμε να επικεντρωθούμε στον αλγόριθμο και όχι σε άλλες λεπτομέρειες.
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; )
Πολυπλοκότητα αλγορίθμου BFS
Η χρονική πολυπλοκότητα του αλγορίθμου BFS αντιπροσωπεύεται με τη μορφή O(V + E), όπου V είναι ο αριθμός των κόμβων και E είναι ο αριθμός των άκρων.
Η διαστημική πολυπλοκότητα του αλγορίθμου είναι O(V).
Εφαρμογές αλγορίθμου BFS
- Για να δημιουργήσετε ευρετήριο ανά ευρετήριο αναζήτησης
- Για πλοήγηση GPS
- Αλγόριθμοι εύρεσης διαδρομής
- Σε αλγόριθμο Ford-Fulkerson για να βρείτε τη μέγιστη ροή σε ένα δίκτυο
- Ανίχνευση κύκλου σε ένα μη κατευθυνόμενο γράφημα
- Σε ελάχιστο δέντρο
