find leaves

 # ans1:

from collections import defaultdict

tree = [[], [2, 3], [4, 5], [6], [], [], []]

td = defaultdict(list)

for i in range(len(tree)):

td[i] = tree[i] # 無論是否有子節點，都加入到字典中

# 找到葉節點

def find_leaves(td):

return [node for node in td if not td[node] and node!=0]

print(find_leaves(td))

# ans2

def find_leaves2(tree):

return [i for i,child in enumerate(tree) if not child and not i==0 ]

print(find_leaves2(tree))

dfs bfs tree_height sample

 from collections import deque

tree = [[],[2,3],[4,5],[6],[],[],[]]

def bfs(tree,root):

q = deque([root])

while q:

node = q.popleft()

print(node,end=' ')

for child in tree[node]:

q.append(child)

bfs(tree,1)

print()

def dfs(tree,node):

print(node,end=' ')

for child in tree[node]:

dfs(tree,child)

dfs(tree,1)

def tree_height(tree,node):

if not tree[node]:return 0

return 1+max(tree_height(tree, child) for child in tree[node] )

print(tree_height(tree, 1))

combinations

 import itertools

d = list('abcd')

for j in range(4+1):

  cs = itertools.combinations(d,j)

  for i in cs:

    print(''.join(i))

  print()

Output:

a
b
c
d

ab
ac
ad
bc
bd
cd

abc
abd
acd
bcd

abcd

Python 應用鄰接表實作圖的簡易教材

 

Python 應用鄰接表實作圖的簡易教材

---

目標

1. 了解圖的基本概念與應用場景。
2. 使用鄰接表表示圖的結構。
3. 學習圖的基本操作（如遍歷、最短路徑等）。

---

1. 圖的基本概念

什麼是圖？

• 圖是由節點（Node）和邊（Edge）組成的數據結構。
  • 節點：用來表示物體。
  • 邊：用來表示節點之間的關係。

圖的類型：

1. 無向圖：節點間的邊沒有方向，如好友關係。
2. 有向圖：節點間的邊有方向，如追隨關係。
3. 加權圖：邊有數值權重，如距離或成本。

---

2. 使用鄰接表表示圖

鄰接表是用字典表示圖的方法，節點的鄰居存儲在列表中。

無向圖：

# 用字典表示圖
graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
}

# 範例：節點 1 連接節點 2 和節點 3
print(graph)

輸入建構無向圖：

from collections import defaultdict

graph = defaultdict(list)
n = int(input("輸入節點數量: "))
for _ in range(n - 1):
    a, b = map(int, input("輸入一條邊: ").split())
    graph[a].append(b)
    graph[b].append(a)

print("鄰接表：", dict(graph))

---

3. 圖的基本操作

操作 1：深度優先搜尋（DFS）

DFS 是什麼？

• 深度優先搜尋是沿著一條路徑一直走到底，然後回頭找其他路徑。

DFS 實作：

def dfs(node, graph, visited):
    print(node, end=" ")  # 訪問節點
    visited.add(node)  # 標記為已訪問
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

# 測試
visited = set()
dfs(1, graph, visited)  # 從節點 1 開始

範例輸入：

4
1 2
1 3
2 4

範例輸出：

1 2 4 3

---

操作 2：廣度優先搜尋（BFS）

BFS 是什麼？

• 廣度優先搜尋是先訪問所有相鄰節點，再逐層深入。

BFS 實作：

from collections import deque

def bfs(start, graph):
    q = deque([start])
    visited = set()
    visited.add(start)
    while q:
        node = q.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)

# 測試
bfs(1, graph)

範例輸出：

1 2 3 4

---

操作 3：判斷是否連通

問題描述：

• 圖是否為連通圖（所有節點是否都能到達）？

解法：使用 DFS：

def is_connected(graph, n):
    visited = set()
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(1)  # 從任意節點開始
    return len(visited) == n  # 是否訪問了所有節點

# 測試
print("圖是否連通：", is_connected(graph, n))

範例輸出：

圖是否連通： True

---

操作 4：尋找最短路徑

無權圖中的最短路徑：

• 使用 BFS 找到從起點到終點的最短路徑長度。

實作：

def shortest_path(graph, start, end):
    from collections import deque
    q = deque([(start, 0)])  # (節點, 路徑長度)
    visited = set()
    visited.add(start)

    while q:
        node, dist = q.popleft()
        if node == end:
            return dist  # 找到目標
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append((neighbor, dist + 1))
    return -1  # 無法到達

# 測試
print("最短路徑長度：", shortest_path(graph, 1, 4))

範例輸出：

最短路徑長度： 2

---

4. 綜合應用：圖的問題解決

應用 1：找到所有連通分量

連通分量是互相連通的一組節點。

實作：

def connected_components(graph, n):
    visited = set()
    components = []

    def dfs(node, component):
        visited.add(node)
        component.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, component)

    for node in range(1, n + 1):
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)
    return components

# 測試
print("圖的連通分量：", connected_components(graph, n))

範例輸出：

圖的連通分量： [[1, 2, 4, 3]]

---

總結

1. 使用鄰接表表示圖：節省空間，結構清晰。
2. 掌握遍歷方法：DFS 和 BFS 是解決圖問題的基礎。
3. 圖的基本操作：
   • 判斷連通性。
   • 找最短路徑。
   • 計算連通分量。
4. 實用性強：這些操作能解決地圖導航、社交網絡等實際問題。

Python 應用鄰接表實作樹的教材

 

以 Python 應用鄰接表實作樹的教材

---

教材目標

1. 了解什麼是鄰接表以及其在樹結構中的應用。
2. 學習如何使用鄰接表表示樹。
3. 掌握基於鄰接表的基本樹操作，如遍歷、計算高度與直徑等。
4. 通過實際問題練習，鞏固樹的基礎知識與鄰接表操作。

---

1. 鄰接表的介紹

什麼是鄰接表？

• 鄰接表是一種高效表示圖和樹的數據結構。
• 每個節點存儲一個列表，其中包含與該節點直接相連的節點。

為什麼用鄰接表來表示樹？

• 占用空間少，特別適合稀疏圖或樹。
• 適合於樹的遍歷操作（例如 DFS、BFS）。

鄰接表的表示方法：

• 使用 Python 的 defaultdict 實現鄰接表。

from collections import defaultdict

# 範例樹的鄰接表表示
tree = defaultdict(list)
tree[1] = [2, 3]
tree[2] = [1, 4, 5]
tree[3] = [1]
tree[4] = [2]
tree[5] = [2]

print(tree)  # {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}

---

2. 使用鄰接表建構樹

輸入樹的節點與邊：

• 節點數量 n。
• 接下來輸入 n−1 條邊，描述樹的父子關係。

Python 實作：

from collections import defaultdict

# 建構樹
tree = defaultdict(list)
n = int(input("輸入節點數量: "))
for _ in range(n - 1):
    a, b = map(int, input("輸入邊 (空格分隔): ").split())
    tree[a].append(b)
    tree[b].append(a)

print("鄰接表表示的樹：", dict(tree))

範例輸入：

5
1 2
1 3
2 4
2 5

範例輸出：

鄰接表表示的樹： {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}

---

3. 樹的基本操作

操作 1：深度優先搜尋（DFS）

DFS 的應用場景：

• 遍歷樹的所有節點。
• 計算樹的高度或查找某節點。

DFS 實作：

def dfs(node, parent):
    print(node, end=" ")  # 訪問節點
    for neighbor in tree[node]:
        if neighbor != parent:  # 避免回到父節點
            dfs(neighbor, node)

# 測試
dfs(1, -1)  # 從節點 1 開始

範例輸出：

1 2 4 5 3

---

操作 2：計算樹的高度

樹的高度：

• 根節點到最遠葉子節點的距離。

DFS 計算樹的高度：

def tree_height(node, parent):
    height = 0
    for neighbor in tree[node]:
        if neighbor != parent:
            height = max(height, tree_height(neighbor, node))
    return height + 1

# 測試
print("樹的高度：", tree_height(1, -1))  # 從節點 1 開始計算

範例輸出：

樹的高度： 3

---

操作 3：計算樹的直徑

樹的直徑：

• 樹中兩個節點間的最長距離。

兩次 DFS 計算樹的直徑：

1. 第一次 DFS：從任意節點開始，找到最遠的節點。
2. 第二次 DFS：從該最遠節點開始，再次找到最遠節點，這段距離即為樹的直徑。

Python 實作：

def dfs_diameter(node, parent, depth):
    farthest_node = node
    max_depth = depth
    for neighbor in tree[node]:
        if neighbor != parent:
            new_depth, new_farthest = dfs_diameter(neighbor, node, depth + 1)
            if new_depth > max_depth:
                max_depth = new_depth
                farthest_node = new_farthest
    return max_depth, farthest_node

# 第一次 DFS
_, farthest = dfs_diameter(1, -1, 0)

# 第二次 DFS
diameter, _ = dfs_diameter(farthest, -1, 0)
print("樹的直徑：", diameter)

範例輸出：

樹的直徑： 3

---

4. 綜合應用：解決問題

應用 1：找出所有葉子節點

葉子節點是沒有子節點的節點。

Python 實作：

def find_leaves():
    leaves = []
    for node in tree:
        if len(tree[node]) == 1:  # 只有一個鄰接節點的就是葉子
            leaves.append(node)
    return leaves

# 測試
print("樹的葉子節點：", find_leaves())

範例輸出：

樹的葉子節點： [4, 5, 3]

---

應用 2：找到某節點的子節點

給定節點，找出其所有直接子節點。

Python 實作：

def find_children(node, parent):
    return [neighbor for neighbor in tree[node] if neighbor != parent]

# 測試
print("節點 2 的子節點：", find_children(2, 1))

範例輸出：

節點 2 的子節點： [4, 5]