Σε αυτό το σεμινάριο, θα μάθετε για τον αλγόριθμο πρώτης αναζήτησης βάθους με παραδείγματα και ψευδοκώδικα. Επίσης, θα μάθετε να εφαρμόζετε το DFS σε C, Java, Python και C ++.
Depth first Search ή Depth first traversal είναι ένας αναδρομικός αλγόριθμος για την αναζήτηση όλων των κορυφών ενός γραφήματος ή μιας δομής δεδομένων δέντρου. Διασταύρωση σημαίνει επίσκεψη σε όλους τους κόμβους ενός γραφήματος.
Αλγόριθμος πρώτης αναζήτησης βάθους
Μια τυπική εφαρμογή DFS τοποθετεί κάθε κορυφή του γραφήματος σε μία από τις δύο κατηγορίες:
- Επισκέφτηκε
- Δεν έχει επισκεφθεί
Ο σκοπός του αλγορίθμου είναι να επισημάνει κάθε κορυφή ως επισκέφθηκε, αποφεύγοντας κύκλους.
Ο αλγόριθμος DFS λειτουργεί ως εξής:
- Ξεκινήστε βάζοντας οποιαδήποτε από τις κορυφές του γραφήματος πάνω από μια στοίβα.
- Πάρτε το κορυφαίο στοιχείο της στοίβας και προσθέστε το στη λίστα επισκέψεων.
- Δημιουργήστε μια λίστα με τους γειτονικούς κόμβους αυτής της κορυφής. Προσθέστε αυτά που δεν περιλαμβάνονται στη λίστα επισκέψεων στην κορυφή της στοίβας.
- Συνεχίστε να επαναλαμβάνετε τα βήματα 2 και 3 έως ότου η στοίβα είναι άδεια.
Παράδειγμα πρώτης αναζήτησης βάθους
Ας δούμε πώς λειτουργεί ο αλγόριθμος Depth First Search με ένα παράδειγμα. Χρησιμοποιούμε ένα μη κατευθυνόμενο γράφημα με 5 κορυφές.
Μη κατευθυνόμενο γράφημα με 5 κορυφές
Ξεκινάμε από την κορυφή 0, ο αλγόριθμος DFS ξεκινά τοποθετώντας τον στη λίστα Επίσκεψη και βάζοντας όλες τις γειτονικές κορυφές του στη στοίβα.
Επισκεφτείτε το στοιχείο και τοποθετήστε το στη λίστα επισκέψεων
Στη συνέχεια, επισκέπτουμε το στοιχείο στην κορυφή της στοίβας, δηλαδή 1 και πηγαίνουμε στους γειτονικούς κόμβους του. Δεδομένου ότι το 0 έχει ήδη επισκεφθεί, επισκεφθούμε 2.
Επισκεφτείτε το στοιχείο στην κορυφή της στοίβας
Το Vertex 2 έχει μια μη ελεγμένη γειτονική κορυφή στο 4, οπότε το προσθέτουμε στην κορυφή της στοίβας και το επισκεφτούμε.
Το Vertex 2 έχει μια μη ελεγμένη γειτονική κορυφή στο 4, οπότε το προσθέτουμε στην κορυφή της στοίβας και το επισκεφτούμε. 
Το Vertex 2 έχει μια μη ελεγμένη γειτονική κορυφή στο 4, οπότε το προσθέτουμε στην κορυφή της στοίβας και το επισκεφτούμε.
Μετά την επίσκεψη στο τελευταίο στοιχείο 3, δεν έχει παρακείμενους κόμβους που δεν έχουν επισκεφθεί, οπότε ολοκληρώσαμε το Depth First Traversal του γραφήματος.
Μετά την επίσκεψη στο τελευταίο στοιχείο 3, δεν έχει παρακείμενους κόμβους που δεν έχουν επισκεφθεί, οπότε ολοκληρώσαμε το Depth First Traversal του γραφήματος.
Ψευδοκώδικας DFS (αναδρομική εφαρμογή)
Ο ψευδοκώδικας για DFS φαίνεται παρακάτω. Στη συνάρτηση init (), παρατηρήστε ότι εκτελούμε τη συνάρτηση DFS σε κάθε κόμβο. Αυτό συμβαίνει επειδή το γράφημα μπορεί να έχει δύο διαφορετικά αποσυνδεδεμένα μέρη, ώστε να διασφαλίσουμε ότι καλύπτουμε κάθε κορυφή, μπορούμε επίσης να εκτελέσουμε τον αλγόριθμο DFS σε κάθε κόμβο.
DFS (G, u) u.visited = true για κάθε v ∈ G.Adj (u) εάν v.visited == false DFS (G, v) init () (Για κάθε u ∈ G u.visited = false Για κάθε u ∈ G DFS (G, u))
Υλοποίηση DFS σε Python, Java και C / C ++
Ο κωδικός για τον αλγόριθμο πρώτης αναζήτησης βάθους με ένα παράδειγμα φαίνεται παρακάτω. Ο κώδικας έχει απλοποιηθεί ώστε να μπορούμε να επικεντρωθούμε στον αλγόριθμο και όχι σε άλλες λεπτομέρειες.
Python Java C C + # DFS algorithm in Python # DFS algorithm def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph(start) - visited: dfs(graph, next, visited) return visited graph = ('0': set(('1', '2')), '1': set(('0', '3', '4')), '2': set(('0')), '3': set(('1')), '4': set(('2', '3'))) dfs(graph, '0')
// DFS algorithm in Java import java.util.*; class Graph ( private LinkedList adjLists(); private boolean visited(); // Graph creation Graph(int vertices) ( adjLists = new LinkedList(vertices); visited = new boolean(vertices); for (int i = 0; i < vertices; i++) adjLists(i) = new LinkedList(); ) // Add edges void addEdge(int src, int dest) ( adjLists(src).add(dest); ) // DFS algorithm void DFS(int vertex) ( visited(vertex) = true; System.out.print(vertex + " "); Iterator ite = adjLists(vertex).listIterator(); while (ite.hasNext()) ( int adj = ite.next(); if (!visited(adj)) DFS(adj); ) ) 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, 3); System.out.println("Following is Depth First Traversal"); g.DFS(2); ) )
// DFS algorithm in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int v); struct Graph ( int numVertices; int* visited; // We need int** to store a two dimensional array. // Similary, we need struct node** to store an array of Linked lists struct node** adjLists; ); // DFS algo void DFS(struct Graph* graph, int vertex) ( struct node* adjList = graph->adjLists(vertex); struct node* temp = adjList; graph->visited(vertex) = 1; printf("Visited %d ", vertex); while (temp != NULL) ( int connectedVertex = temp->vertex; if (graph->visited(connectedVertex) == 0) ( DFS(graph, connectedVertex); ) temp = temp->next; ) ) // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create 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; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Adjacency list of vertex %d ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); DFS(graph, 2); return 0; )
// DFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list *adjLists; bool *visited; public: Graph(int V); void addEdge(int src, int dest); void DFS(int vertex); ); // Initialize graph Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); visited = new bool(vertices); ) // Add edges void Graph::addEdge(int src, int dest) ( adjLists(src).push_front(dest); ) // DFS algorithm void Graph::DFS(int vertex) ( visited(vertex) = true; list adjList = adjLists(vertex); cout << vertex << " "; list::iterator i; for (i = adjList.begin(); i != adjList.end(); ++i) if (!visited(*i)) DFS(*i); ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.DFS(2); return 0; )
Πολυπλοκότητα της πρώτης αναζήτησης βάθους
Η χρονική πολυπλοκότητα του αλγορίθμου DFS αντιπροσωπεύεται με τη μορφή O(V + E), πού Vείναι ο αριθμός των κόμβων και Eείναι ο αριθμός των άκρων.
Η διαστημική πολυπλοκότητα του αλγορίθμου είναι O(V).
Εφαρμογή του αλγορίθμου DFS
- Για την εύρεση του μονοπατιού
- Για να ελέγξετε εάν το γράφημα είναι διμερές
- Για την εύρεση των ισχυρά συνδεδεμένων στοιχείων ενός γραφήματος
- Για την ανίχνευση κύκλων σε ένα γράφημα
