Algoritma Pencarian Pertama Kedalaman (DFS)

Dalam tutorial ini, anda akan belajar mengenai algoritma carian pertama mendalam dengan contoh dan pseudocode. Anda juga akan belajar menerapkan DFS di C, Java, Python, dan C ++.

Depth first Search atau Depth first traversal adalah algoritma rekursif untuk mencari semua bucu graf atau struktur data pokok. Traversal bermaksud melawat semua nod graf.

Algoritma Pencarian Pertama Kedalaman

Pelaksanaan DFS standard meletakkan setiap titik grafik menjadi salah satu daripada dua kategori:

  1. Dikunjungi
  2. Tidak Dikunjungi

Tujuan algoritma adalah untuk menandakan setiap bucu sebagai dikunjungi sambil mengelakkan pusingan.

Algoritma DFS berfungsi seperti berikut:

  1. Mulakan dengan meletakkan salah satu bucu grafik di atas timbunan.
  2. Ambil item teratas timbunan dan tambahkan ke senarai yang dikunjungi.
  3. Buat senarai nod bersebelahan bucu itu. Tambahkan yang tidak ada dalam senarai yang dikunjungi ke bahagian atas timbunan.
  4. Terus ulangi langkah 2 dan 3 sehingga timbunan kosong.

Contoh Pencarian Pertama Kedalaman

Mari lihat bagaimana algoritma Depth First Search berfungsi dengan contoh. Kami menggunakan graf tidak terarah dengan 5 bucu.

Graf tak tentu dengan 5 bucu

Kita mulakan dari bucu 0, algoritma DFS bermula dengan memasukkannya ke dalam senarai Dikunjungi dan meletakkan semua bucu bersebelahan dalam timbunan.

Lawati elemen tersebut dan masukkan ke dalam senarai yang dikunjungi

Seterusnya, kami melawat elemen di bahagian atas timbunan iaitu 1 dan pergi ke nod bersebelahan. Oleh kerana 0 telah dilawati, kami hanya mengunjungi 2 orang.

Lawati elemen di bahagian atas timbunan

Vertex 2 mempunyai bucu bersebelahan yang tidak dikunjungi dalam 4, jadi kami menambahkannya ke bahagian atas timbunan dan mengunjunginya.

Vertex 2 mempunyai bucu bersebelahan yang tidak dikunjungi dalam 4, jadi kami menambahkannya ke bahagian atas timbunan dan mengunjunginya. Vertex 2 mempunyai bucu bersebelahan yang tidak dikunjungi dalam 4, jadi kami menambahkannya ke bahagian atas timbunan dan mengunjunginya.

Selepas kita mengunjungi elemen terakhir 3, ia tidak mempunyai simpul bersebelahan yang tidak dikunjungi, jadi kita telah melengkapkan Traversal Depth First grafik.

Selepas kita mengunjungi elemen terakhir 3, ia tidak mempunyai simpul bersebelahan yang tidak dilawati, jadi kita telah melengkapkan Traversal Depth First grafik.

DFS Pseudocode (pelaksanaan berulang)

Kod pseudok untuk DFS ditunjukkan di bawah. Dalam fungsi init (), perhatikan bahawa kita menjalankan fungsi DFS pada setiap nod. Ini kerana grafik mungkin mempunyai dua bahagian yang terputus yang berbeza sehingga untuk memastikan bahawa kita merangkumi setiap bucu, kita juga dapat menjalankan algoritma DFS pada setiap simpul.

 DFS (G, u) u.visited = true untuk setiap v ∈ G.Adj (u) jika v.visited == false DFS (G, v) init () (Untuk setiap u ∈ G u.visited = false Untuk setiap u ∈ G DFS (G, u))

Pelaksanaan DFS di Python, Java dan C / C ++

Kod untuk Algoritma Pencarian Pertama Kedalaman dengan contoh ditunjukkan di bawah. Kodnya telah dipermudahkan sehingga kita dapat memfokuskan pada algoritma daripada perincian lain.

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

Kerumitan Pencarian Pertama Kedalaman

Kerumitan masa algoritma DFS ditunjukkan dalam bentuk O(V + E), di mana Vbilangan nod dan Ebilangan tepi.

Kerumitan ruang algoritma adalah O(V).

Aplikasi Algoritma DFS

  1. Kerana mencari jalan
  2. Untuk menguji sama ada grafnya adalah dua bahagian
  3. Untuk mencari komponen grafik yang saling berkaitan
  4. Untuk mengesan kitaran dalam graf

Artikel menarik...