佑佑的語言

[Python]BFS(廣度優先搜尋) 、 DFS(深度優先搜尋)

分享教學來源:https://youtu.be/oLtvUWpAnTQ

影片大大教得不錯，比起在學校老師講得天花亂墜又不會實作，所以看完就想要實作一次看看~~

首先講BFS是如何搜索呢?

如同名字定義要"廣度"先

如果A是起始點，那他所連到的點有(B、C)；(B在連到D、C連到E)；(D在連到F)

A->B->C->D->E->F(這是其中一個答案)

所以我覺得要知道兩件事:

1.照順序一層一層下去，樹畫出來

2.走過別再走

在舉例，如果起始在E，則是 E->C->D->A->B->F

另外一個DFS

那就是要"深度"，一次走到底，到底再回頭看哪裡沒走過

一樣從A開始走，A->B->D->F，到底再回頭走沒走的，E->C(這是其中一個答案)

所以我又知道2件事:

1.每一層走一點和一遍最好

2.到底層爬回去上層找沒走過的

那來時做看看吧

目前用python比較好講，C++蠻麻煩的，有空我再來聊

BFS

會用到一個概念Queue(佇列)、先進先出(First-in-First-out)

多用在 排隊問題

從起點把點從左到右塞進去，保證層的順序

code:

graph = {
    "A":["B","C"],
    "B":["A","C","D"], 
    "C":["A","B","D","E"],
    "D":["B","C","E","F"],
    "E":["C","D"],
    "F":["D"],      
}
def BFS(graph,s):
    queue = []
    queue.append(s)
    seen = set()
    seen.add(s)
    while(len(queue)>0):
        vertex = queue.pop(0)
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                queue.append(w)
                seen.add(w)
        print(vertex)
BFS(graph,'E')

output:

E
C
D
A
B
F

DFS

這也會用到一個概念，Stack(堆疊)、具有後進先出(Last-in-First-out)或先進後出(First-in-Last-out)的有序串列

多用在發牌問題、走迷宮、疊盤子

規則就是有下個點拿出來，下個點放進去，直到沒有再依序把裡面的東西從上面一 一拿出來

code:

graph = {
    "A":["B","C"],
    "B":["A","C","D"], 
    "C":["A","B","D","E"],
    "D":["B","C","E","F"],
    "E":["C","D"],
    "F":["D"],      
}
def BFS(graph,s):
    stack = []
    stack.append(s)
    seen = set()
    seen.add(s)
    while(len(stack)>0):
        vertex = stack.pop()
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                stack.append(w)
                seen.add(w)
        print(vertex)
BFS(graph,'E')

output:

E
D
F
B
A
C

關於程式碼的語法可以看我分享的教學來源，他有系列的講解，真的講超好der。

感恩收看 \030/