最小生成树与最短路径算法

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

1. 最小生成树——Prime算法


从初始结点开始，依次找最短的边连接各结点。

2. 最小生成树——Kruskal算法


两两连接最小边，再并入结点

3. 最短路径——Dijkstra算法



最小子树

1 2 10 10

①1 5 5 5

②5 4 2 7

③5 2 3 8

④2 3 1 9

并查集（树）

①1—5:5

②1—5—4:7

③1—5—2:8

④1—5—2—3:9

4. 最短路径——Floyd算法


写出邻接矩阵，逐个加入点更新矩阵

5. AOV网及拓扑排序

DAG：有向无环图

AOV：顶点表示活动，边表示先后关系


依次去掉出发结点

7. AOE网及关键路径

AOE:顶点表示事件、边表示活动、权值表示开销


Ve(i):头结点到各个结点的最大距离，比如Ve(4)=a2+a5=2+4=6

Vl(i):倒序写，依次用最大距离减去临近的边长（注意最近的问题）比如：Vl(3)=V4-a5=6-4=2

e(i):将Ve(i)按结点划分写（最后一个结点不用写）

V1 | V2 | V3 | V4 | V5

a1 a2 | a3 a4 | a5 a6 | a7 | a8

0 0 3 3 2 2 6 6   

l(i):最近一个结点减去边长，例l(5) = V4-4

l-e=0为关键结点

广度优先搜索（BFS）



深度优先搜索（DFS）



总结：

BFS一层一层来

DFS一条路走到黑，不撞南墙不回头

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：广度优先搜索 深度优先搜索 最小生成树 有向无环图 最短路径

kruskal算法中结点的自由度什么时候限制为2，什么时候不用限制？

kruskal算法中结点的自由度什么时候限制为2，什么时候不用限制？

kruskal算法中结点的自由度什么时候限制为2，什么时候不用限制？