type
status
date
slug
summary
tags
category
icon
password
前言：
算法与数据结构第四次作业
目录：
一、给出下图的邻接矩阵、邻接表、逆邻接表表示。
答案：
二、给出下图的邻接矩阵、邻接表表示。什么是最小生成树？构造最小生成树的算法有哪些?给出下图的最小生成树。
答案：邻接矩阵：
邻接表：
上道题看懂了无需多言
最小生成树（MST）：
1.定义
在连通的无向带权图中，生成树是包含所有顶点的子图，且是树（无环，边数 = 顶点数 - 1）；最小生成树是所有生成树中，边权之和最小的生成树。
2.构造算法
Prim 算法：从一个顶点出发，逐步选择“当前与生成树集合相连的最小权边”，加入生成树，直到包含所有顶点。适合稠密图（边多）。
Kruskal 算法：将所有边按权值升序排序，依次选边，若加入后不形成环（用并查集判断），则加入生成树，直到选够 n-1 条边。适合稀疏图（边少）。
3.构造具体图的最小生成树
需分别对上下两图构造 MST，以下用 Kruskal 算法演示（按边权升序选边，避环）
（1）图 1（，共 7 顶点，需 6 条边）
步骤：
1. 排序所有边（升序）
、
、
、
、
、
、
、
、
2. 依次选边（避环）：
选 ：无环，生成树含 。
选 ：无环，生成树含 。
选 ：无环，生成树含 。
选 ：无环（ 新， 已在），生成树含 。
选 ：无环（ 新， 已在），生成树含 。
选 ：无环（ 在 ， 在 ，合并后含所有顶点）。
最终 MST 边为：、、、、、，总权值 30+40+42+45+50+50=257。
（2）图 2（，共 8 顶点，需 7 条边）
步骤：
1. 排序所有边（升序）
、
、
、
、
、
、
、
、
、
、
、
、
、
。
2. 依次选边（避环）：
选 ：无环，生成树含。
选 ：无环，生成树含 。
选 ：无环（e 新，f 已在），生成树含 。
选 ：无环（b 新，a 已在），生成树含 。
选 ：无环，生成树含 。
选 ：无环（b 在 ，d 在 ，合并后含 ）。
选 ：无环（d 在 ，g 在 ，合并后含所有顶点）。
最终 MST 边为：，总权值 2+3+3+4+4+5+5=26。
三、什么是拓扑排序? 给出下图的一个拓扑有序序列。
拓扑排序：
指对有向无环图（DAG）中的节点进行线性排序，使得对于每条有向边 u v，节点 u 总是出现在 v 之前。
拓扑有序序列为：（拓扑序列不唯一，只要满足“前驱在前、后继在后”即可）
四、写出下图的深度优先搜索遍历序列和广度优先搜索遍历序列，并解释其遍历思想。
深度优先搜索（DFS）遍历序列：
（注：这里分行仅仅是为了手机屏幕显示正常，没别的含义）
遍历思想：
DFS 遵循“深度优先，回溯搜索”的原则，类似“走迷宫时一条路走到头，走不通再回头换路”。
1. 从起始节点 出发，优先选择一条路径（如 ）深入到底；
2. 沿 深入，直到 无未访问邻接节点，触发回溯；
3. 回溯到 （无其他邻接）→ 回溯到 ，选择下一个邻接 ，重复深度优先（，但 已访问，继续回溯）；
4. 回溯到 ，选择下一个邻接 ，沿 深入，直到所有节点访问完毕。
广度优先搜索（BFS）遍历序列：
（注：这里分行仅仅是为了手机屏幕显示正常，没别的含义）
遍历思想：
BFS 遵循“分层遍历，先广后深”的原则，类似“涟漪扩散，先访问同一层所有节点，再访问下一层”。
1. 从起始节点 出发，先访问其所有直接邻接节点（、，即“第1层”）；
2. 再依次访问 、 的邻接节点（、、、，即“第2层”）；
3. 最后访问 、 的邻接节点 （即“第3层”）。
五、什么是最小生成树的MST性质？两个构造最小生成树的经典算法是什么？
MST 性质：假设 N = ( V, E ) 是一个连通网，U 是顶点集 V 的一个非空子集。若 ( u , v )是一条具有最小权值（代价）的边，其中 u ∈ U，v ∈ V - U，则必存在一棵包含边 ( u , v ) 的最小生成树。
普里姆算法和克鲁斯卡尔算法是两个利用 MST 性质构造最小生成树的经典贪心算法。
<ins/>
- 作者:EageYren
- 链接:https://eageyren.edu.deal/learning/algorithm4
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
