数据结构严蔚敏最小生成树以书本P174图7.16为例1. 绘制邻接矩阵、邻接表、手工求解最小生成树的过程；2．求解最小生成树的程序

数据结构中，Kruskal's算法（亦称“最小生成树算法”）是一个常用的方法来找到无向图的最小生成树。以严蔚敏《数据结构》书中P174页图7.16为例，这是一个典型的有向边权重图。

**1. 邻接矩阵表示：**
首先，你需要创建一个二维数组，其中行代表顶点，列表示与之相连的顶点及其对应的权重。假设图中有5个顶点A-E，邻接矩阵可以像这样：

| | A | B | C | D | E |
|---|---|---|---|---|---|
| A | - | 4 | 0 | 0 | 0 |
| B | 4 | - | 8 | 0 | 7 |
| C | 0 | 8 | - | 7 | 0 |
| D | 0 | 0 | 7 | - | 9 |
| E | 0 | 7 | 0 | 9 | - |

**2. 邻接表表示：**
邻接表通常用于稀疏图，每个顶点有一个链表，包含与它相邻的所有顶点及其对应权重。例如：

- A: [B(4), E(0)]
- B: [A(4), C(8), E(7)]
- C: [B(8), D(7)]
- D: [C(7), E(9)]
- E: [B(7), D(9)]

**3. 手工求解过程：**
按升序遍历所有边，每次选择权重最小的未加入最小生成树的边，直到所有顶点都被连接。在这个例子中，手动求解可能需要多次尝试组合，直到形成一棵连通且权重和最小的树。

**4. 编程求解最小生成树程序（Python举例）：**

import heapq

def kruskal(graph):
    edges = [(weight, i, j) for i in range(len(graph)) for j in range(i+1, len(graph[i]))]
    mst = []
    heap = []
    
    # 将边按照权重排序并入堆
    heapq.heapify(edges)
    
    while len(mst) < len(graph) - 1:
        weight, u, v = heapq.heappop(edges)
        
        # 检查u和v是否已经通过其他边加入过mst
        if set([u, v]) not in {set(edge[1:3]) for edge in mst}:
            mst.append((u, v, weight))
            
    return mst

# 使用邻接矩阵实例化图，并求解最小生成树
adj_matrix = ... (根据邻接矩阵填充)
min_tree = kruskal(adj_matrix)