<jupyter_start><jupyter_text>1、DFS： 使用Stack栈来实现，append(新的节点)，pop(尾巴节点)<jupyter_code>def dfs(graph, start):
    stack = [start]
    seen = {start}
    while stack:
        vertex = stack.pop() # 尾巴元素
        for node in graph[vertex]:
            if node not in seen:
                stack.append(node)
                seen.add(node)
        print(vertex)
    return seen
dfs(graph, 'A')<jupyter_output>A
C
E
D
F
B<jupyter_text>2、BFS: 使用队列实现，append(新的节点)，pop(首元素)<jupyter_code>def bfs(graph, start):
    queue = [start]
    seen = {start}
    while queue:
        vertex = queue.pop(0) # 首元素
        for node in graph[vertex]:
            if node not in seen:
                queue.append(node)
                seen.add(node)
        print(vertex)
    return seen
def bfs(graph, start):
    queue = [start]
    seen = {start}
    parent = {start:None}
    while queue:
        vertex = queue.pop(0) # 首元素
        for node in graph[vertex]:
            if node not in seen:
                queue.append(node)
                seen.add(node)
                parent[node] = vertex
        print(vertex)
    return seen, parent
bfs(graph, 'A')<jupyter_output>A
B
C
D
E
F<jupyter_text>3、Dijkstra: 每个节点之间都有相应的权重，可以用于求从一个节点出发到另外节点的最短路径<jupyter_code>graph = {
    'A': {'B': 5, 'C': 1},
    'B': {'A': 5, 'C': 2, 'D': 1},
    'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
    'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
    'E': {'C': 8, 'D': 3},
    'F': {'D': 6}
}
graph['A']['B']
import heapq

def dijkstra(graph, start):
    seen = set()
    pqueue = []
    heapq.heappush(pqueue, (0, start))
    parent = {start:None} # 从起始点出发到各个点的最短距离
    dist = {start:0}
    
    while pqueue:
        dis, node = heapq.heappop(pqueue)
        seen.add(node)
        
        for w in graph[node].keys():
            if w not in seen:
                new_dis = dis + graph[node][w]
                if new_dis < dist.get(w, float('inf')):
                    dist[w] = new_dis
                    heapq.heappush(pqueue, (new_dis, w))
                    parent[w] = node
    return parent, dist
parent, dist = dijkstra(graph, 'A')
print(parent, dist)
end = 'E'
path = []
while end:
    path.append(end)
    end = parent[end]
print(path)<jupyter_output>['E', 'D', 'B', 'C', 'A']
{'fraction_non_alphanumeric': 0.15946547884187082, 'fraction_numerical': 0.010244988864142539, 'mean_word_length': 2.0767123287671234, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '642376', 'license': 'Apache-2.0', 'n_tokens_mistral': 920, 'n_tokens_neox': 911, 'n_words': 205, 'path': 'Dynamic Programming/DFS-BFS-Dijkstra.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '2245'}