Graph & BFS/DFS

# graph: A-B, A-C, B-D, C-D
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
# directed = เส้นมีทิศ; weighted = เส้นมีน้ำหนัก (ระยะทาง/ค่าใช้จ่าย)

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D']

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(graph, "A")   # A B D C  (ลงลึกก่อน)

def count_components(graph):
    visited = set()
    count = 0
    for node in graph:
        if node not in visited:
            count += 1
            # ท่องทุก node ที่เชื่อมถึงด้วย BFS/DFS
            stack = [node]
            while stack:
                n = stack.pop()
                if n not in visited:
                    visited.add(n)
                    stack.extend(graph[n])
    return count