相关文章推荐
所谓生成树就是
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
生成树是连通图的包含图中的所有顶点的极小连通子图。
（图的生成树不惟一。从不同的顶点出发进行遍历，...
今天在做题的时候遇到一个问题，如何根据图的邻接表来画出DFS生成树和BFS生成树，有两年的真题中涉及到这个问题，在以前的学习中没注意过此问题，由于严奶奶的书上也只是一带而过，所以对它的理解也不深刻，作...
最小生成树的基本概念
一个有n个结点的连通图的生成树是原图的极小连通子图，它包含原图中的所有n个结点，并且有保持图连通的最少的边。
如果无向连通图是一个带权图，那么它的所有生成...
树（自由树）、无序树和有根树
　自由树就是一个无回路的连通图（没有确定根）(在自由树中选定一顶点做根，则成为一棵通常的树)。
　从根开始，为每个顶点(在树中通常称作结点)的孩子...
1. 图的最小生成树
生成树的定义：如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
生成树是连通图的包含图中的所有顶点的极小连通子图。它并不唯一，从不同的顶点出发进行遍...
#最小生成树
说白了就是连接所有点的然后权值最小的无环连通子图主要有两种算法：Prim算法和Kruskal算法先做一些约定：只考虑连通图（不连通你分开算就行了）
边的权重不一定是表示距离
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Verte...
图结构练习——最小生成树
Time Limit: 1000MS Memory limit: 65536K
有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的...
最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n－1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树的权最小!
头文件Graph.h
#ifndef ...
最小生成树能够保证整个拓扑图的所有路径之和最小，但不能保证任意两点之间是最短路径。
最短路径是从一点出发，到达目的地的路径最小。
二 实现方法
1. 最小生成树
最小生成树有两种算...
他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字) 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
kruskal算法求最小生成树
下载积分：100
内容提示：kruskal算法求最小生成树
文档格式：PDF|
浏览次数：202|
上传日期： 19:52:57|
文档星级：
全文阅读已结束，如果下载本文需要使用
 100 积分
下载此文档
该用户还上传了这些文档
kruskal算法求最小生成树
关注微信公众号[算法系列之三十]Dijkstra单源最短路径算法
单源最短路径问题
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。
单源最短路径问题
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
前面讲了单源最短路径的Bellman-Ford算法(动态规划算法)。这里介绍另外一个更常见的算法Dijkstra算法。
Dijkstra算法和 最小生成树Prim算法最小生成树算法非常类似，大家可以先熟悉下个算法。两个算法都是基于贪心算法。虽然Dijkstra算法相对来说比Bellman-Ford 算法更快，但是不适用于有负权值边的图，贪心算法决定了它的目光短浅。而Bellman-Ford 算法从全局考虑，可以检测到有负权值的回路。
这里模仿MST(Minimum Spanning Tree)的Prim算法，我们创建一个SPT(最短路径树)，最初只包含源点。我们维护两个集合，一组已经包含在SPT(最短路径树)中的顶点S集合,另一组是未包含在SPT内的顶点T集合。每次从T集合中选择到S集合路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
T集合用最小优先队列Q存储，该队列包含所有属于V-S的节点（这些节点尚未确定最短路径的权），且以d值为关键字排列各节点。
初始时，Q包含了除源点src以外的其他节点，这些节点的d值为无穷大。源点src进入S之后，d[src]=0。算法反复从Q中取出d值最小的节点u，u属于V-S，把u插入集合S中，并对u的所有出边进行松弛，这一过程直到Q队列为空为止。
如下图所示的图：
S集合最初为空，然后选取源点0，S集合为 {0}，源点到其它所有点的距离为 {0, INF, INF, INF, INF, INF, INF, INF} 。图中蓝色表示 SPT，迭代的过程如下：
最终得到 SPT(最短路径树) 如下：
The code calculates shortest distance, but doesn’t calculate the path information. We can create a parent array, update the parent array when distance is updated (like prim’s implementation) and use it show the shortest path from source to different vertices.
The code is for undirected graph, same dijekstra function can be used for directed graphs also.
The code finds shortest distances from source to all vertices. If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target (Step 3.a of algorithm).
Time Complexity of the implementation is O(V^2). If the input graph is represented using adjacency list, it can be reduced to O(E log V) with the help of binary heap. We will soon be discussing O(E Log V) algorithm as a separate post.
Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman–Ford algorithm can be used, we will soon be discussing it as a separate post.
时间复杂度分析
算法的执行速度取决于优先队列Q的数据结构。有三种数据结构可供选择。
用一维数组实现优先队列Q。在该算法中，每次都是从最小优先队列Q中取出d值最小的节点需要的时间为O(V),存在|V|次这样的操作，所以最小优先队列Q取出d值最小的节点的全部运行时间为O(V^2)。因为每个节点v属于V仅被插入集合S一次，所以在算法的执行过程中，v的每条邻接边在for循环中仅被考察一次。因为在所有邻接边的总数为|E|，所以在该for循环中总共存在|E|次迭代，每次迭代运行时间为O(1),导致整个算法的运行时间为O(V^2+E)=o(V^2) 。显然对于规模不大的稠密图，可次啊用数组实现优先队列。
用二叉堆实现优先队列Q。在该算法中，每次从最小优先队列Q取出d值最小的节点需要的时间为O(lnV),存在|V|次这样的操作。建立二叉堆需要的时间为O(V)。在relax过程中的赋值语句d[v] &- d[u]+w(u,v)是通过调整节点v在二叉堆的位置来完成的，运行时间为O(lnV)，并且至多存在|E|次这样的操作。因此算法的时间复杂度O((V+E)lnV)。通常情况下，边数|E|都不小于节点数|V|，所以运行时间可以简化为O(ElnV)。显然在稀疏图的情形下用二叉堆来实现优先队列是比较实用。
用Fibonacci堆实现优先队列。运行时间为O(VlnV+E)。
#include &iostream&
#include &climits&
#include &vector&
using namespace std;
int GetMinVertex(int dist[], bool visited[],int v) {
int min = INT_MAX;
for(int i = 0;i &++i){
if(!visited[i] && dist[i] & min){
min = dist[i];
void Print(int dist[],int n){
for(int i = 0;i &++i){
cout&&"距离顶点"&&i&&"最短距离-&"&&dist[i]&&
void Dijkstra(vector&vector&int& & graph,int src) {
int v = graph.size();
int dist[v];
bool visited[v];
for(int i = 0;i &++i){
dist[i] = (graph[src][i] == 0 ? INT_MAX:graph[src][i]);
visited[i] = false;
dist[src] = 0;
visited[src] = true;
for(int i = 1;i &++i){
int u = GetMinVertex(dist,visited,v);
visited[u] = true;
for (int j = 0;j &++j){
if (!visited[j] && graph[u][j] && dist[u] != INT_MAX
&& dist[u] + graph[u][j] & dist[j]){
dist[j] = dist[u] + graph[u][j];
Print(dist,v);
int main() {
vector&vector&int& & graph =
{0, 4, 0, 0, 0, 0, 0, 8, 0 },
{4, 0, 8, 0, 0, 0, 0, 11, 0 },
{0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 0, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
Dijkstra(graph,0);
版权声明：本文内容由互联网用户自发贡献，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至： 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
用云栖社区APP，舒服~
【云栖快讯】2017互联网超级工程阿里双11完美落幕，交易额突破1682亿，但阿里工程师如何玩转“超级工程”，背后黑科技又是如何？12月13-14日，12位大咖直播分享揭秘1682亿背后技术实践，马上预约&&
用于实时预测用户对物品偏好，支持企业定制推荐算法，支持A/B Test效果对比
基于全网公开发布数据、传播路径和受众群体画像，利用语义分析、情感算法和机器学习，分析公众对品牌形象、热点事件和公...
大数据开发套件（Data IDE），提供可视化开发界面、离线任务调度运维、快速数据集成、多人协同工作等功能，为您...
为您提供简单高效、处理能力可弹性伸缩的计算服务，帮助您快速构建更稳定、安全的应用，提升运维效率，降低 IT 成本...
社区之星年度评选，投票可抽奖
Loading...> 问题详情
对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点 a 到其他各顶点的最短路径，则得到的第
悬赏：0&答案豆
提问人：匿名网友
发布时间：
对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点 a 到其他各顶点的最短路径，则得到的第一条最 短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是A.d,e,fB.e,d,fC.f,d,eD.f,e,d请帮忙给出正确答案和分析，谢谢！
为您推荐的考试题库
您可能感兴趣的试题
1下列关于最小生成树的说法中，正确的是最小生成树树的代价唯一II. 权值最小的边一定会出现在所有的最小生成树中III. 用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV. 普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅 IB.仅 IIC.仅 I、IIID.仅 II、IV2设有一棵 3 阶
B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是A.60B.60, 62C.62, 65D.653在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排 序结束都至少能够确定一个元素最终位置的方法是简单选择排序II. 希尔排序III. 快速排序IV 堆排序二路归并排序A.仅 I、III、IVB.仅 II、III、IVC.仅 I、III、VD.仅 III、IV、V4对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是A.排序的总趟数B.使用辅助空间的数量C.元素的移动次数D.元素之间的比较次数
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：