{"id":4251,"date":"2026-10-02T23:41:52","date_gmt":"2026-10-02T16:41:52","guid":{"rendered":"https:\/\/focusnic.com\/blog\/?p=4251"},"modified":"2026-10-02T23:41:55","modified_gmt":"2026-10-02T16:41:55","slug":"pengertian-dfs","status":"publish","type":"post","link":"https:\/\/focusnic.com\/blog\/pengertian-dfs\/","title":{"rendered":"Depth First Search (DFS): Pengertian, Teori, Pseudocode, dan Contoh Implementasi"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><strong>Depth First Search (DFS)<\/strong> adalah salah satu <strong>algoritma<\/strong> dasar untuk menjelajah atau mencari jalur pada struktur data <strong>graf<\/strong> maupun <strong>pohon<\/strong>. Algoritma ini bekerja dengan prinsip menelusuri sedalam mungkin satu cabang sebelum kembali (backtrack) untuk menelusuri cabang lain. DFS menggunakan <strong>rekursi<\/strong> atau <strong>stack<\/strong> sebagai media penyimpanan simpul yang akan diproses selanjutnya.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Algoritma DFS pertama kali diperkenalkan pada era awal pengembangan teori <strong>graf<\/strong> oleh matematikawan seperti Konrad Zuse dan kemudian dipopulerkan dalam literatur algoritma komputer. DFS banyak digunakan dalam berbagai aplikasi komputasi, mulai dari pencarian jalur, pemecahan teka-teki, hingga analisis jaringan sosial dan pemrosesan bahasa alami.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_88 counter-hierarchy ez-toc-counter ez-toc-light-blue ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Dasar_Teori_dan_Karakteristik_Depth_First_Search\" >Dasar Teori dan Karakteristik Depth First Search<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Implementasi_dan_Aplikasi_DFS_dalam_Pemrograman\" >Implementasi dan Aplikasi DFS dalam Pemrograman<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Contoh_Implementasi_di_Python\" >Contoh Implementasi di Python<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Aplikasi_Nyata_DFS\" >Aplikasi Nyata DFS<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Kelebihan_dan_Kekurangan_Depth_First_Search\" >Kelebihan dan Kekurangan Depth First Search<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Kelebihan_DFS\" >Kelebihan DFS<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/focusnic.com\/blog\/pengertian-dfs\/#Kekurangan_DFS\" >Kekurangan DFS<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Dasar_Teori_dan_Karakteristik_Depth_First_Search\"><\/span>Dasar Teori dan Karakteristik Depth First Search<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Prinsip utama DFS adalah <strong>masuk sedalam mungkin<\/strong> ke dalam struktur graf sebelum kembali ke simpul sebelumnya. Langkah umum DFS meliputi:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Kunjungi simpul awal dan tandai sebagai telah dikunjungi.<\/li>\n\n\n\n<li>Pilih salah satu simpul tetangga yang belum dikunjungi.<\/li>\n\n\n\n<li>Ulangi proses (rekursif) pada simpul tetangga tersebut.<\/li>\n\n\n\n<li>Jika simpul tidak memiliki tetangga yang belum dikunjungi, <strong>backtrack<\/strong> ke simpul sebelumnya.<\/li>\n\n\n\n<li>Proses selesai ketika semua simpul yang dapat dijangkau telah dikunjungi.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dalam notasi Big O, kompleksitas waktu DFS pada graf dengan <em>V<\/em> simpul dan <em>E<\/em> sisi adalah <strong>O(V + E)<\/strong>. Kompleksitas memori bergantung pada kedalaman maksimum jalur DFS. Jika menggunakan <strong>rekursi<\/strong>, kedalaman rekursi dapat mencapai O(V) pada graf linier. Dengan implementasi <strong>stack<\/strong> eksplisit, penggunaan memori juga mencapai O(V) untuk menyimpan simpul dalam antrian.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Implementasi_dan_Aplikasi_DFS_dalam_Pemrograman\"><\/span>Implementasi dan Aplikasi DFS dalam Pemrograman<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Berikut adalah pseudocode DFS menggunakan pendekatan rekursif:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>DFS(simpul):<\/li>\n\n\n\n<li>\u00a0\u00a0 Tandai simpul sebagai <strong>diklik<\/strong> atau <strong>visited<\/strong>.<\/li>\n\n\n\n<li>\u00a0\u00a0 Untuk setiap tetangga simpul yang belum dikunjungi, panggil DFS(tetangga).<\/li>\n\n\n\n<li> Selesai.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">Varian menggunakan <strong>stack<\/strong> eksplisit:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Push simpul awal ke dalam stack dan tandai visited.<\/li>\n\n\n\n<li>Sementara stack tidak kosong:<\/li>\n\n\n\n<li>\u00a0\u00a0 Pop simpul dari stack.<\/li>\n\n\n\n<li>\u00a0\u00a0 Proses simpul tersebut.<\/li>\n\n\n\n<li>\u00a0\u00a0 Untuk setiap tetangga yang belum dikunjungi, tandai visited dan push ke stack.<\/li>\n\n\n\n<li> Selesai.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Contoh_Implementasi_di_Python\"><\/span>Contoh Implementasi di Python<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Contoh sederhana DFS pada graf tak berarah direpresentasikan dengan dictionary:<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:python decode:true \" >def dfs(graph, start, visited=None):\n    if visited is None:\n        visited = set()\n    visited.add(start)\n    print(start)\n    for neighbor in graph[start]:\n        if neighbor not in visited:\n            dfs(graph, neighbor, visited)\n    return visited\n\n# Contoh penggunaan\ngraph = {\n    'A': ['B', 'C'],\n    'B': ['A', 'D', 'E'],\n    'C': ['A', 'F'],\n    'D': ['B'],\n    'E': ['B', 'F'],\n    'F': ['C', 'E']\n}\n\nvisited_nodes = dfs(graph, 'A')\nprint(\"Simpul terkunjungi:\", visited_nodes)<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Aplikasi_Nyata_DFS\"><\/span>Aplikasi Nyata DFS<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">DFS banyak diaplikasikan di berbagai bidang, antara lain:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Pencarian Jalur<\/strong> pada game atau simulasi: Menemukan rute dari titik A ke B.<\/li>\n\n\n\n<li><strong>Pemecahan Teka-Teki<\/strong> seperti Sudoku atau labirin.<\/li>\n\n\n\n<li><strong>Analisis Struktur Data<\/strong>: Menentukan komponen terhubung pada graf.<\/li>\n\n\n\n<li><strong>Topological Sorting<\/strong> pada graf berarah asiklik (DAG).<\/li>\n\n\n\n<li><strong>Web Crawling<\/strong>: Menjelajahi halaman web secara mendalam.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Kelebihan_dan_Kekurangan_Depth_First_Search\"><\/span>Kelebihan dan Kekurangan Depth First Search<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Kelebihan_DFS\"><\/span>Kelebihan DFS<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Implementasi Sederhana<\/strong>: Rekursi atau stack eksplisit memudahkan kode.<\/li>\n\n\n\n<li><strong>Penggunaan Memori Efisien<\/strong> pada graf besar dengan banyak cabang sempit.<\/li>\n\n\n\n<li><strong>Deteksi Siklus<\/strong>: Mudah mengetahui apakah graf mengandung siklus.<\/li>\n\n\n\n<li><strong>Pencarian Mendalam<\/strong>: Berguna untuk menemukan solusi yang menuntut eksplorasi mendalam.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Kekurangan_DFS\"><\/span>Kekurangan DFS<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Risiko Stack Overflow<\/strong> saat rekursi terlalu dalam pada graf besar.<\/li>\n\n\n\n<li><strong>Tidak Optimal<\/strong> untuk menemukan jalur terpendek jika bobot sisi sama.<\/li>\n\n\n\n<li><strong>Backtracking Berlebihan<\/strong> dapat menghabiskan waktu pada graf dengan banyak cabang bercabang.<\/li>\n\n\n\n<li><strong>Beban Memori<\/strong> meningkat pada graf yang sangat lebar (banyak simpul pada satu level).<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Dengan pemahaman mendalam tentang <strong>Depth First Search<\/strong>, Anda dapat memilih atau memodifikasi algoritma ini sesuai kebutuhan aplikasi, baik untuk keperluan akademis maupun industri.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Depth First Search (DFS) adalah salah satu algoritma dasar untuk menjelajah atau mencari jalur pada struktur data graf maupun pohon. Algoritma ini bekerja dengan prinsip menelusuri sedalam mungkin satu cabang sebelum kembali (backtrack) untuk menelusuri cabang lain. DFS menggunakan rekursi atau stack sebagai media penyimpanan simpul yang akan diproses selanjutnya. Algoritma DFS pertama kali diperkenalkan [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":4334,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[114],"class_list":["post-4251","post","type-post","status-publish","format-standard","has-post-thumbnail","category-informasi","tag-programming"],"_links":{"self":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4251","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/comments?post=4251"}],"version-history":[{"count":1,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4251\/revisions"}],"predecessor-version":[{"id":4335,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/posts\/4251\/revisions\/4335"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/media\/4334"}],"wp:attachment":[{"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/media?parent=4251"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/categories?post=4251"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/focusnic.com\/blog\/wp-json\/wp\/v2\/tags?post=4251"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}