Algoritma Mencari Laluan (BFS, DFS)
Terokai algoritma seperti Carian Lebar Dahulu dan Carian Dalam Dahulu untuk mencari laluan serta sambungan dalam graf.
Algoritma Mencari Laluan (BFS, DFS) ialah pelajaran Asas Pangkalan Data Graf Neo4j percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Asas Pangkalan Data Graf Neo4j, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Asas Pangkalan Data Graf Neo4j merangkumi sejumlah 4 pelajaran.
Mencari Laluan dalam Graf
Graf berkisar tentang hubungan! Bayangkan peta yang mempunyai bandar sebagai titik dan jalan sebagai garisan. Mencari laluan terbaik dari satu bandar ke bandar lain ialah masalah klasik "pencarian laluan".
Dalam pelajaran ini, kami akan meneroka dua algoritma asas untuk mencari laluan dalam graf: Carian Mendalam Dahulu (BFS) dan Carian Lebar Dahulu (DFS).
Apakah Graf? Ulang Kaji Pantas
Sebelum kita mendalami algoritma, mari ulang kaji secara ringkas maksud graf:
- Nod: Entiti atau titik dalam graf anda, contohnya orang, bandar dan produk.
- Hubungan: Sambungan antara nod, contohnya "FRIENDS_WITH" dan "LOCATED_IN".
- Laluan: Urutan nod dan hubungan yang bersambung dari satu nod ke nod yang lain.
BFS: Meneroka Lapisan demi Lapisan
Carian Mendalam Dahulu (BFS) adalah seperti meneroka sesebuah sesat dengan memeriksa semua jalan keluar serta-merta dari bilik semasa, kemudian semua jalan keluar dari bilik-bilik tersebut, dan seterusnya.
Ia meneroka graf secara sistematik mengikut aras, dan memastikan laluan terpendek ditemui berdasarkan bilangan hubungan antara dua nod dalam graf tidak berwajaran.
Cara BFS Berfungsi
BFS menggunakan "baris gilir" seperti barisan di kedai, iaitu masuk dahulu, keluar dahulu, untuk menjejak nod yang perlu dilawati seterusnya.
- Ia bermula pada nod yang diberikan.
- Ia melawati semua jiran langsung nod tersebut terlebih dahulu.
- Kemudian, ia melawati semua jiran yang belum dilawati bagi jiran-jiran tersebut.
- Ia menjejak nod yang telah dilawati untuk mengelakkan gelung dan kerja berulang.
Contoh Kod BFS
Mari lihat contoh Python mudah bagi BFS pada graf kecil. Kami mewakili graf menggunakan kamus yang kuncinya ialah nod dan nilainya ialah senarai jiran nod tersebut.
def bfs_path(graph, start_node):
visited = []
queue = [start_node]
visited.append(start_node)
path = []
while queue:
current_node = queue.pop(0) # Get first node
path.append(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.append(neighbor)
queue.append(neighbor)
return path
if __name__ == "__main__":
# A simple graph:
# A -- B
# | |
# C -- D
graph_data = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
print("BFS path from 'A':")
print(bfs_path(graph_data, 'A'))DFS: Menyelam Lebih Dalam
Carian Lebar Dahulu (DFS) menggunakan pendekatan yang berbeza. Daripada meneroka lapisan demi lapisan, ia bergerak sedalam mungkin pada setiap cabang sebelum berundur.
Bayangkan anda menavigasi sesat dengan sentiasa memilih satu laluan dan mengikutinya hingga ke penghujung. Jika laluan itu buntu, anda berundur dan mencuba laluan lain.
Cara DFS Berfungsi
DFS biasanya menggunakan "tindanan" masuk terakhir, keluar dahulu atau rekursi untuk mengurus penerokaannya.
- Ia bermula pada nod yang diberikan.
- Ia memilih satu jiran yang belum dilawati dan bergerak ke nod itu.
- Ia mengulangi proses ini untuk bergerak semakin jauh ke dalam graf.
- Jika ia menemui jalan buntu atau nod yang telah dilawati, ia berundur ke nod terakhir yang mempunyai jiran belum dilawati.
Contoh Kod DFS
Berikut ialah contoh Python bagi DFS. Kami akan menggunakan pendekatan rekursif, yang menggunakan tindanan panggilan secara semula jadi untuk mencapai penelusuran secara mendalam dahulu.
def dfs_path(graph, start_node, visited=None, path=None):
if visited is None:
visited = set()
if path is None:
path = []
visited.add(start_node)
path.append(start_node)
for neighbor in graph[start_node]:
if neighbor not in visited:
dfs_path(graph, neighbor, visited, path)
return path
if __name__ == "__main__":
# A simple graph:
# A -- B
# | |
# C -- D
graph_data = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
print("DFS path from 'A':")
# Note: DFS path can vary based on neighbor order
print(dfs_path(graph_data, 'A'))BFS berbanding DFS: Perbezaan Utama
BFS dan DFS kedua-duanya berkuasa, tetapi sesuai untuk masalah yang berbeza:
- BFS: Menjamin laluan terpendek berdasarkan bilangan hubungan. Sangat sesuai untuk mencari rakan terdekat dan lokasi terhampir.
- DFS: Berguna untuk menyemak keterhubungan, mencari semua laluan atau melakukan pengisihan topologi. Ia mungkin lebih cekap dari segi memori untuk graf yang sangat dalam.
- Memori: BFS boleh menggunakan lebih banyak memori untuk graf yang lebar dan mempunyai banyak jiran. DFS boleh menggunakan lebih banyak ruang tindanan untuk graf yang dalam.
Semakan Pantas: Pilihan Pencarian Laluan
Anda sedang membina ciri rangkaian sosial yang perlu mencari hubungan terpendek, iaitu bilangan rakan paling sedikit, antara dua pengguna. Algoritma manakah yang paling sesuai untuk tugasan ini dalam graf tidak berwajaran?
Imbas Kembali & Langkah Seterusnya
Syabas! Dalam pelajaran ini, anda telah mempelajari dua algoritma asas penelusuran graf:
- Carian Mendalam Dahulu (BFS): Meneroka lapisan demi lapisan dan sesuai untuk mencari laluan terpendek.
- Carian Lebar Dahulu (DFS): Menyelam jauh ke dalam graf dan berguna untuk menyemak keterhubungan atau mencari semua laluan.
Memahami algoritma ini penting untuk menyelesaikan banyak masalah graf dan membantu anda menghargai cara pangkalan data graf mencari hubungan dengan cekap.
Pelajari Asas Pangkalan Data Graf Neo4j dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 12
- Pelajaran
- 48
Soalan Lazim
Adakah pelajaran “Algoritma Mencari Laluan (BFS, DFS)” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran Asas Pangkalan Data Graf Neo4j, termasuk “Algoritma Mencari Laluan (BFS, DFS)”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus Asas Pangkalan Data Graf Neo4j merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Algoritma Mencari Laluan (BFS, DFS)”?
Terokai algoritma seperti Carian Lebar Dahulu dan Carian Dalam Dahulu untuk mencari laluan serta sambungan dalam graf. Anda berlatih Asas Pangkalan Data Graf Neo4j menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Asas Pangkalan Data Graf Neo4j?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Asas Pangkalan Data Graf Neo4j di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.
Berapa lamakah pelajaran “Algoritma Mencari Laluan (BFS, DFS)” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Asas Pangkalan Data Graf Neo4j ini?
Ya. Setiap pelajaran Asas Pangkalan Data Graf Neo4j menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Algoritma Mencari Laluan (BFS, DFS)
- Algoritma Kesentralan (PageRank)
- Algoritma Pengesanan Komuniti
- Algoritma Keserupaan dan Ramalan Pautan