DFS -Depth First Seach

00:14:44
https://www.youtube.com/watch?v=XTf6d0KXvsw

Ringkasan

TLDRThe video introduces the Depth-First Search (DFS) algorithm, focusing on its method of exploring nodes in a graph by navigating deeper into child nodes before examining sibling nodes. It outlines the advantages of DFS, such as low memory usage and relatively quick access to solutions. However, the method may also have drawbacks, including a tendency to miss optimal solutions when multiple are present at different levels of the graph. Practical applications of DFS in programming, including coding examples in Python, illustrate how the algorithm functions in real-world scenarios, such as mapping distances between cities.

Takeaways

  • 🔍 DFS explores child nodes before siblings.
  • 💾 DFS uses less memory than other search algorithms.
  • 🚀 Once a solution is found, DFS halts exploring further paths.
  • ⚠️ DFS may miss optimal solutions if alternatives exist at different levels.
  • ⏪ Backtracking is crucial in DFS when a path doesn't lead to a goal.
  • 🌍 DFS can be applied to urban mapping and route finding.
  • 📈 Implementation of DFS can be done easily in programming languages like Python.

Garis waktu

  • 00:00:00 - 00:05:00

    The video introduces the concept of Depth-First Search (DFS), explaining its function as a search algorithm that explores nodes by going deep into one branch before backtracking. It highlights the method's efficiency in memory usage and its ability to find solutions without testing all possibilities. However, it also discusses the limitations of DFS, such as the risk of missing optimal solutions in trees with infinite branches or multiple solutions at different levels.

  • 00:05:00 - 00:14:44

    The presenter demonstrates the application of DFS in a coding example using Python, where a graph is defined using a dictionary. The code simulates the DFS process, showing how nodes are visited and how the algorithm backtracks when necessary. The example illustrates the practical implementation of DFS, emphasizing its recursive nature and how it operates within a defined graph structure.

Peta Pikiran

Video Tanya Jawab

  • What is DFS?

    DFS stands for Depth-First Search, an algorithm used to explore nodes and find solutions by prioritizing child nodes before sibling nodes.

  • What are the advantages of DFS?

    DFS requires small memory, finds solutions quickly once a goal is reached, and does not need to explore all nodes.

  • What are the disadvantages of DFS?

    DFS may not find the best solution if multiple exist at different levels and can get stuck in infinite trees.

  • How is DFS applied in programming?

    DFS can be implemented in programming languages like Python using recursive functions to traverse and explore graphs.

  • What is an example use case of DFS?

    An example use case is finding the shortest path in a graph representing city maps.

  • How does DFS handle backtracking?

    DFS backtracks when a node does not yield a goal, moving back to explore other potential paths.

Lihat lebih banyak ringkasan video

Dapatkan akses instan ke ringkasan video YouTube gratis yang didukung oleh AI!
Teks
id
Gulir Otomatis:
  • 00:00:00
    Hai
  • 00:00:00
    [Musik]
  • 00:00:27
    the firts atau dfs
  • 00:00:30
    ya overview dari materi kali ini kita
  • 00:00:33
    akan membahas tentang pengertian dave's
  • 00:00:35
    lalu kelebihan dan kekurangan studi
  • 00:00:38
    kasus dfs dan pemrograman yang
  • 00:00:40
    menggunakan DSS Mungkin nanti sore
  • 00:00:42
    pemrograman akan terpisah dari surat ini
  • 00:00:46
    apa sih dfs itu dfstd sebuah algoritma
  • 00:00:49
    pencarian mendalam biasa dvc digunakan
  • 00:00:52
    untuk mencari solusi menggunakan
  • 00:00:54
    metode grab jadi kalau kita punya grab
  • 00:00:57
    lalu kita ingin mencari dimana Soul
  • 00:01:00
    tersebut kita bisa menggunakan namanya
  • 00:01:01
    The First atau metode search Salah satu
  • 00:01:05
    wedevs BFF dan lain lain itu ada banyak
  • 00:01:08
    di grup cuman kali ini kita akan
  • 00:01:10
    membahas pertama tentang dave's lo dfs
  • 00:01:14
    melakukan pencarian mendalam ke anak
  • 00:01:16
    terlebih dahulu ketimbang pada not yang
  • 00:01:18
    satu level contoh misalnya not a Dia
  • 00:01:21
    memiliki anak yaitu b c dan d e
  • 00:01:25
    hai lalu B memiliki anak E itu maka
  • 00:01:29
    ketika dia akan mencari dia akan mencari
  • 00:01:31
    dari a&b keet terlebih dahulu
  • 00:01:36
    baru dia akan mencari ke c dan gede
  • 00:01:40
    terjadi Dia selalu mencari dari sisi
  • 00:01:44
    kiri ketika dia mentok ketika dia mentok
  • 00:01:46
    di kiri tidak menemukan
  • 00:01:48
    solusi maka dia akan kembali ke atasnya
  • 00:01:51
    lalu baru mencari not di sebelah
  • 00:01:54
    kanannya jadi dia akan mencari selalu di
  • 00:01:56
    sebelah kiri terlebih dahulu baru
  • 00:01:59
    mencari ditengah kekanan kekanan dan
  • 00:02:01
    seterusnya itu itu Drs
  • 00:02:05
    lalu apa sih kelebihan dari deface
  • 00:02:08
    beserta dengan kekurangannya sama deface
  • 00:02:11
    hanya membutuhkan memori yang sangat
  • 00:02:12
    kecil kita kenapa ya tadi kalau dia
  • 00:02:14
    sudah ketemu maka dia tidak perlu
  • 00:02:17
    mencari yang lain gitu Ade membutuhkan
  • 00:02:20
    memori yang kecil
  • 00:02:21
    berikutnya dapat menemukan solusi tanpa
  • 00:02:24
    harus menguji Hai Betul sekali kalau
  • 00:02:26
    solusinya sudah ketemu dikirim maka dia
  • 00:02:28
    mau Sebanyak apa di kanan dia tidak
  • 00:02:30
    mempedulikan apa yang ada di kanan jadi
  • 00:02:33
    akan mencari hanya di sebelah kiri
  • 00:02:36
    lalu apa sih kekurangannya gitu
  • 00:02:38
    kekurangannya adalah Jika pohon memiliki
  • 00:02:40
    anak yang tak terhingga itu maka tidak
  • 00:02:43
    ada jaminan menemukan solusinya kita
  • 00:02:45
    atau tidak komplit
  • 00:02:46
    dibayangin Kalau pohon itu memiliki anak
  • 00:02:50
    yang tidak terhingga maka dia akan tidak
  • 00:02:51
    menemukan itu pusat dikirimnya banyak
  • 00:02:54
    banget itu maka dia akan terlalu
  • 00:02:56
    konsentrasi di sebelah kiri itu
  • 00:02:58
    lalu kekurangan berikutnya dari jika
  • 00:03:00
    terdapat lebih dari satu solusi
  • 00:03:03
    tetapi berada pada level yang berbeda
  • 00:03:05
    maka tidak ada jaminan untuk menemukan
  • 00:03:07
    solusi yang terbaik atau bisa disebut
  • 00:03:10
    sebagai tidak optimal jadi misalnya
  • 00:03:12
    contohnya di kiri misalnya di kiri itu
  • 00:03:15
    ada solusi yang panjangnya itu misalnya
  • 00:03:17
    5not giliran sedangkan dikanan itu ada
  • 00:03:21
    solusi yang panjangnya cuman tiga not
  • 00:03:23
    maka solusi bukan bukan yang tiga not
  • 00:03:26
    tetapi yang 5not itu itu tersebut the
  • 00:03:31
    optimal itu karena dia hanya prinsip
  • 00:03:35
    nyari dulu di kiri gituan ori ketemu ya
  • 00:03:38
    udah selesai walaupun ikan mungkin ada
  • 00:03:40
    solusi yang lebih pendek itu nanti ada
  • 00:03:42
    contohnya
  • 00:03:44
    Lalu bagaimana kita melakukan deface Bro
  • 00:03:47
    Sudah ada jelas di depan yang pertama
  • 00:03:49
    diperiksa bahkan laut tersebut merupakan
  • 00:03:51
    goals kalau dia tidak goals itu kan cek
  • 00:03:54
    Apakah dia memiliki keturunan gitu kan
  • 00:03:56
    jika Iya masukin ke dalam notice
  • 00:04:00
    jika kemungkinan dari not sudah habis
  • 00:04:02
    maka dia mundur ke titik sebelumnya
  • 00:04:04
    hingga ke titik pertama
  • 00:04:07
    Hai sebagai contoh defisini ini adalah
  • 00:04:10
    dimulai dari Note S
  • 00:04:15
    Note S ini memiliki anak atau notulis
  • 00:04:19
    itu ada a&b dan C karena tadi Rully
  • 00:04:23
    adalah kita mencari dulu dari sebelah
  • 00:04:26
    kiri itu kan maka dari Aini kedai itu
  • 00:04:30
    kan di mana De itu ada kemungkinan
  • 00:04:32
    modusnya adalah e b dan c kita cek
  • 00:04:36
    Apakah tadi atau mengecek Apakah dia
  • 00:04:39
    goloso ternyata bukan hanya di gede
  • 00:04:41
    ternyata dia itu juga bukan maka dia
  • 00:04:43
    kembali backtrack ke ahli diakui
  • 00:04:47
    diedit cek juga Apakah di Eh ini itu
  • 00:04:51
    punya
  • 00:04:53
    FG
  • 00:04:56
    b&c gituan dicek itu apakah sebuah goals
  • 00:05:00
    potreto Bukan gitu kan dia akan turun
  • 00:05:03
    mencari di f f akan mempunyai not list G
  • 00:05:07
    a b dan c dia tanyalah dieva bakaev ini
  • 00:05:11
    gurau Ternyata bukan gitu dia backtrack
  • 00:05:14
    lagi
  • 00:05:15
    sampai dia ke g&g punya not least
  • 00:05:20
    b&c itu G dicek lagi G Apakah dia punya
  • 00:05:24
    dia adalah gold powder ada Bukan dia
  • 00:05:27
    balik ke dia balik ke ah lalu balik ke
  • 00:05:29
    es Halo dek mulai dari sini balik lagi
  • 00:05:33
    dia punya B Itu kan karena ini sudah
  • 00:05:35
    selesai nih di kiri dengan begitu punya
  • 00:05:39
    not least adalah
  • 00:05:41
    h&c gituan maka dia ke haduh seperti
  • 00:05:45
    seperti sebelumnya role adalah sebelah
  • 00:05:48
    kiri terlebih dahulu nih ah
  • 00:05:51
    lalu Hai itu menyanyi j&c karena hal ini
  • 00:05:56
    mencari lah ke itu punya not least j&t
  • 00:06:02
    Hai itu punya notice adalah j&c becek
  • 00:06:05
    lah Apakah ini sebelah goals kodrata
  • 00:06:07
    bukan itu kan dia balik lagi ke ha
  • 00:06:11
    setelah di Hah gitu kan dia keji dia
  • 00:06:14
    nanya J itu gols atau bukan OTG itu
  • 00:06:18
    girls itu kan maka disini tanin jitu
  • 00:06:20
    goals maka c itu tidak perlu diekspos
  • 00:06:24
    lagi
  • 00:06:25
    [Musik]
  • 00:06:26
    gitu karena sudah ketemu Nah coba
  • 00:06:29
    bayangkan ketika
  • 00:06:31
    ternyata Dika Ini adalah sebuah J itu
  • 00:06:35
    saya yakin bahwa dari ini kan kita kalau
  • 00:06:38
    yang di kita lewatin 12 not ya gitu nah
  • 00:06:41
    kode ini cuma ngelewatin satu Note Gear
  • 00:06:44
    usia pasti akan memiliki jarak yang
  • 00:06:45
    lebih dekat itu kan harusnya ya maka
  • 00:06:49
    karena dia Pak kita pakai dfsd sangat
  • 00:06:51
    konsen mencari di sebelah kiri ke kanan
  • 00:06:54
    maka kita tidak akan mendapatkan data
  • 00:06:57
    yang optimal jika misalnya ada di sini
  • 00:07:00
    nih itu Hai itu yang tadi saya Tuliskan
  • 00:07:03
    di
  • 00:07:04
    sisi kelemahan dari dfs itu sendiri lalu
  • 00:07:08
    harus di kasus
  • 00:07:10
    itu kita mencari ke
  • 00:07:13
    jarak terdekat dari Arab kebuka rezeki
  • 00:07:17
    menjadi titik Arab nanti mohon maaf ya
  • 00:07:20
    kalau saya nyebutin kotak-kotak kota ini
  • 00:07:22
    salah karena sih juga bukan orang
  • 00:07:24
    bukarest jadi saya nggak tahu
  • 00:07:26
    nama kotanya yang benar gitu kan ini
  • 00:07:30
    kita mencari jarak terdekat dari arah ke
  • 00:07:32
    bucharest Apa yang harus kita lakukan
  • 00:07:33
    pertama kali adalah kita mengkonversi
  • 00:07:36
    grapa peta bucharest ini sudah kayak
  • 00:07:40
    graphs Iya itu kan menjadi sebuah graf
  • 00:07:42
    fun disini saya petakan untuk memetakan
  • 00:07:45
    ini gitu kan sebetulnya dilihat kita mau
  • 00:07:48
    sejauh atom melevelkan peta tersebut
  • 00:07:50
    menjadi sebuah grab itu misalnya saya
  • 00:07:53
    menggunakan
  • 00:07:54
    1234 ada lima level itu jadi kita cuma
  • 00:07:58
    terakhir di sini bukarest pada ini kan
  • 00:08:00
    Soalnya ini kan kita lihat Hai teh itu
  • 00:08:03
    Trimo Sora lugoj me hadiah dengan
  • 00:08:07
    doretanh website ini bisa ke c bisa
  • 00:08:10
    kepek Tapi karena kita Sepakat saya
  • 00:08:13
    bersepakat menggunakan lima tuh 2345
  • 00:08:16
    maka grabnya seperti ini gitu kan Nah
  • 00:08:20
    dari sini kita convert nih setiap
  • 00:08:21
    kotanya a-z
  • 00:08:25
    softlenshop22 inilah disini semua
  • 00:08:27
    cukuran
  • 00:08:30
    malu apa yang dilakukan agar kita
  • 00:08:32
    melakukan hal yang sama dari
  • 00:08:35
    contoh yang sebelumnya Nah kita mencari
  • 00:08:38
    Aa itu punya notulis itu Z s&t
  • 00:08:43
    Hai itu kan lalu kita berjalan di kiri
  • 00:08:46
    terlebih dahulu di gitu ada z-trans itu
  • 00:08:49
    punya OS dan teh maka kirinya lagi dua
  • 00:08:51
    oh
  • 00:08:52
    oh itu punya
  • 00:08:55
    SS Dante itu akan
  • 00:08:59
    Hai nih sst Nah kita bekerja dari es
  • 00:09:03
    yang sebelah sini dulu kiri dulu tetap
  • 00:09:05
    dia punya fr-s Dante nah sedangkan F dia
  • 00:09:10
    punya BRS Dante Nah dari lagi apakah
  • 00:09:14
    Benny sebuah goals bukarest ternyata dia
  • 00:09:17
    goals maka er s&t ini tidak perlu dicari
  • 00:09:22
    atau not explain istilahnya nah disini
  • 00:09:25
    terlihat bodi sebelah kiri kita sudah
  • 00:09:27
    menemukan solusinya gitu makanya
  • 00:09:30
    berbasiskan
  • 00:09:31
    peta ini maka kita masukkan angkanya
  • 00:09:34
    disini km dari aku Z Berapa kilo 75 Z ke
  • 00:09:38
    o71 Oke
  • 00:09:41
    151sk
  • 00:09:42
    f99 FB itu 211 totalnya dan 607 KM hasil
  • 00:09:49
    pencarian menggunakan yang namanya dfs
  • 00:09:52
    di sini kalian bisa lihat bahwa ada B di
  • 00:09:56
    level
  • 00:09:57
    halo
  • 00:09:59
    123
  • 00:10:01
    123 Di sini ada B sebenarnya
  • 00:10:05
    Hai
  • 00:10:06
    Nah karena kita menggunakan dfs maka dia
  • 00:10:09
    berkonsentrasi di kiri terlebih dahulu
  • 00:10:12
    baru ke kanan padahal mungkin saja
  • 00:10:14
    jarak dari
  • 00:10:17
    afb1 kita menggunakan misalnya BFC
  • 00:10:19
    mungkin ini justru ini akan yang lebih
  • 00:10:21
    optimal gitu kan jaraknya lebih dekat
  • 00:10:24
    Karena kota yang dilewatin kelihatannya
  • 00:10:26
    dia lebih sedikit gitu kalau kita nanti
  • 00:10:30
    kita coba di pertemuan berikutnya dengan
  • 00:10:32
    kasus yang sama menggunakan
  • 00:10:34
    UBS itu kita dapat Angka berapa di dfs
  • 00:10:38
    kita dia menurut bfs paling jarak paling
  • 00:10:42
    pendeknya adalah
  • 00:10:43
    670 M gitu jadi setiap metode itu pasti
  • 00:10:48
    punya kelemahan dan kekurangan gitu Nah
  • 00:10:50
    ini salah satu kekurangannya deface
  • 00:10:52
    adalah dia terlalu konsentrasi dia
  • 00:10:54
    mencari terlebih dahulu di sisi kiri
  • 00:10:57
    itu studi kasus tentang peta Romania
  • 00:11:00
    Terima kasih telah memperhatikan Selamat
  • 00:11:04
    mencoba membaca ke kembali video ini
  • 00:11:08
    Terima kasih ya setelah tadi melihat
  • 00:11:11
    video tentang
  • 00:11:13
    dasar dari dfs maka saya akan coba masuk
  • 00:11:17
    ke dalam Bagaimana penerapan DSS dalam
  • 00:11:22
    koding item
  • 00:11:24
    jadi kita pada coding ini kita ambil
  • 00:11:28
    contohnya menggunakan bahasa pemrograman
  • 00:11:29
    paketan
  • 00:11:30
    tradfri itu sangat sederhana maka
  • 00:11:32
    kodenya juga
  • 00:11:34
    kodenya juga enggak terlalu ribet gitu
  • 00:11:36
    Jadi pertama kita mendefinisikan sebuah
  • 00:11:39
    grabnya terlebih dahulu grave ini kita
  • 00:11:41
    menggunakan paytren dictionary seperti
  • 00:11:42
    biasa aja gitu ini tanpa menggunakan
  • 00:11:45
    impor
  • 00:11:47
    label khusus kita bisa langsung bikin
  • 00:11:49
    grabnya pakai
  • 00:11:53
    tipe data dictionary di paytren itu
  • 00:11:56
    dalam laci disini xilamuren variabel
  • 00:11:58
    ramai grab di dalam metode nota itu
  • 00:12:01
    punya Z FT jadi saya mengambil dari agan
  • 00:12:05
    brand not yang tadi yang ini
  • 00:12:08
    a memiliki zst itu kan lalu Z itu
  • 00:12:14
    memiliki o gituan Oh memiliki S1 karena
  • 00:12:17
    dia tidak bisa dipakaikan sama dengan
  • 00:12:20
    variabel atau Ki yang sama Gita maka
  • 00:12:23
    saya kasih S1 dan seterusnya kita
  • 00:12:25
    definition semua disini itu
  • 00:12:28
    lalu kita membikin sebuah set untuk
  • 00:12:32
    menyimpan data-data not yang telah
  • 00:12:36
    dilewati namanya saya sebut sebagai
  • 00:12:37
    visited itu jadi kita Ran aja
  • 00:12:40
    pelan-pelan gitaran satu nah kita bikin
  • 00:12:43
    visited itu isinya set
  • 00:12:46
    sentron juga lalu saya membikin sebuah
  • 00:12:49
    fungsi namanya dfs dia mengajak memiliki
  • 00:12:52
    parameter visited grab dan not tadi sini
  • 00:12:55
    dibilang jika not-not visited jika
  • 00:12:58
    notnya belum pernah ke visit maka dia
  • 00:13:01
    cetak notnya terus kita tambahin datanya
  • 00:13:03
    ke visit hai lalu dia ngecek euy Bora
  • 00:13:08
    tangganya dari grab tersebut lalu dia
  • 00:13:10
    memanggil fungsi yang sama ini
  • 00:13:12
    menggunakan fungsi rekursif namanya tuh
  • 00:13:16
    jadi kitaran lalu kitaran laut rezeki
  • 00:13:21
    Taran kita mulai dari
  • 00:13:23
    visited ya ini lalu grabnya lalu kita
  • 00:13:27
    molen dari not berapa akan dimulai kita
  • 00:13:30
    mulai dari not a
  • 00:13:32
    kita Ran Nah di sini terlihat bagaimana
  • 00:13:36
    dia berjalannya a set of 1fb
  • 00:13:41
    RS nah ini sesuai dengan dia berjalannya
  • 00:13:45
    sebuah dfs a-z
  • 00:13:49
    co-ass
  • 00:13:52
    1fb lalu dia balik lagi ke er gitu kan
  • 00:13:56
    ini kita anggap drum ada kita tidak
  • 00:13:59
    mencari solusi ya kita mensimulasikan
  • 00:14:01
    bagaimana dfr itu bekerja itu ir hai
  • 00:14:05
    lalu dari Er Di langsung ke es dari es
  • 00:14:09
    dia ke o1 karena disini dadao dan
  • 00:14:12
    seterusnya gitu Jadi ini
  • 00:14:14
    program ini mensimulasikan bagaimana dfs
  • 00:14:18
    itu bekerja vlognya Mas Hai
  • 00:14:21
    yaitu contoh dari rap penerapan
  • 00:14:25
    algoritma dfs di dalam bahasa
  • 00:14:28
    pemrograman Python terima kasih
  • 00:14:31
    [Musik]
  • 00:14:43
    hai hai
Tags
  • DFS
  • algorithm
  • depth-first search
  • programming
  • graph traversal
  • backtracking
  • case study
  • coding examples
  • advantages
  • disadvantages