Algoritma Depth First Search (DFS)

Daftar Isi

Algoritma Pencarian Kedalaman Pertama
Contoh Penelusuran Kedalaman Pertama
Pseudocode DFS (implementasi rekursif)
Implementasi DFS dengan Python, Java dan C / C ++
Kompleksitas Penelusuran Pertama Kedalaman
Penerapan Algoritma DFS

Dalam tutorial ini, Anda akan belajar tentang algoritma pencarian kedalaman pertama dengan contoh dan pseudocode. Selain itu, Anda akan belajar mengimplementasikan DFS di C, Java, Python, dan C ++.

Depth first Search atau Depth first traversal adalah algoritma rekursif untuk mencari semua simpul dari suatu grafik atau struktur data pohon. Traversal berarti mengunjungi semua node dari sebuah grafik.

Algoritma Pencarian Kedalaman Pertama

Implementasi DFS standar menempatkan setiap simpul grafik ke dalam salah satu dari dua kategori:

Dikunjungi
Tidak Dikunjungi

Tujuan dari algoritma ini adalah untuk menandai setiap simpul sebagai telah dikunjungi sambil menghindari siklus.

Algoritme DFS bekerja sebagai berikut:

Mulailah dengan meletakkan salah satu simpul grafik di atas tumpukan.
Ambil item teratas dari tumpukan dan tambahkan ke daftar yang dikunjungi.
Buat daftar simpul yang berdekatan pada simpul itu. Tambahkan yang tidak ada dalam daftar yang dikunjungi ke bagian atas tumpukan.
Terus ulangi langkah 2 dan 3 hingga tumpukan kosong.

Contoh Penelusuran Kedalaman Pertama

Mari kita lihat bagaimana algoritma Depth First Search bekerja dengan sebuah contoh. Kami menggunakan grafik tidak berarah dengan 5 simpul.

Grafik tidak berarah dengan 5 simpul

Kita mulai dari simpul 0, algoritma DFS dimulai dengan meletakkannya di daftar yang Dikunjungi dan meletakkan semua simpul yang berdekatan di tumpukan.

Kunjungi elemen dan letakkan di daftar yang dikunjungi

Selanjutnya, kami mengunjungi elemen di bagian atas tumpukan yaitu 1 dan pergi ke node yang berdekatan. Karena 0 telah dikunjungi, kami mengunjungi 2 sebagai gantinya.

Kunjungi elemen di bagian atas tumpukan

Simpul 2 memiliki simpul bersebelahan yang belum dikunjungi di 4, jadi kami menambahkannya ke atas tumpukan dan mengunjunginya.

Setelah kita mengunjungi elemen 3 terakhir, tidak ada node yang berdekatan yang belum dikunjungi, jadi kita telah menyelesaikan Traversal Pertama Kedalaman grafik.

Setelah kita mengunjungi elemen terakhir 3, tidak ada node yang berdekatan yang belum dikunjungi, jadi kita telah menyelesaikan Traversal Pertama Kedalaman grafik.

Pseudocode DFS (implementasi rekursif)

Pseudocode untuk DFS ditampilkan di bawah. Dalam fungsi init (), perhatikan bahwa kita menjalankan fungsi DFS pada setiap node. Ini karena grafik mungkin memiliki dua bagian terputus yang berbeda sehingga untuk memastikan bahwa kita mencakup setiap simpul, kita juga dapat menjalankan algoritma DFS pada setiap simpul.

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

Implementasi DFS dengan Python, Java dan C / C ++

Kode untuk Algoritma Pencarian Kedalaman Pertama dengan contoh ditampilkan di bawah ini. Kode tersebut telah disederhanakan sehingga kita dapat fokus pada algoritme daripada detail lainnya.

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