如何求有向图的最小生成树？

课本中只给出了无向图的最小生成树的算法过程，请教有向图的最小生成树的算法过程是什么样的？

16 个解决方案

#1

最小生成树只是针对无向图而言的，有向图上的这类问题叫做最小树形图。
只是听说而已，具体没研究过。楼主如果感兴趣可以去搜一下关于这方面的资料。  

#2

求的方法跟无向图一样,只是要注意路径的方向.

#3

引用 2 楼 shimanyin 的回复:

求的方法跟无向图一样,只是要注意路径的方向.

这个可不一样，要麻烦得多

#4

你看是不是可以这样，从某一定点出发以它为弧尾进行深度优先遍历，如果碰到回路就返回上一个顶点再找其他途径，把所有的完整遍历的生成树找到后取一个最小的。

#5

这个有点难度

---
推荐个学习的网站  电子软件开发网 特别适合嵌入式linux方向的同仁

#6

关注

#7

up

#8

up

#9

引用 1 楼 dlyme 的回复:

最小生成树只是针对无向图而言的，有向图上的这类问题叫做最小树形图。 
只是听说而已，具体没研究过。楼主如果感兴趣可以去搜一下关于这方面的资料。  

继续跟老大学习。

#10

并不是任一有向图都有最小树形图的。
如果判定一个有向图有最小树形图呢？
是个问题（没有实用价值，就pass...）

#11

严蔚敏数据结构30后i

#12

好多垃圾回复，我都不想说了，没点实际的效果。
是来捞分的就直接说撒，看不贯一副大老的样子，其实什么都不懂！

#13

小弟看了楼主的贴以后很认真的翻了翻数据结构有关最小生成树那一章。求最小生成树是为了解决城市之间架设通讯线路求最低成本的通信网络这类问题的，所以抽象出来它解决的对象就是带权图（即网络），而网络是无向的带权的图，所以楼主说求有向图的最小生成树的问题是书上不存在的，也是求最小生成树所办不到的。小弟才疏学浅也只是了解到这些，不过这个问题我开学后会和老师讨论讨论的^_^

#14

建议你看看北大的离散数学，那里边讲得很清楚

#15

Kleinberg的Algorithm Design书中第四章第九节就是讲这个问题~~~~~~找到除根节点外每个节点最便宜的入边e，所有入边减去e的权值，会得到一些边的权值为0，若所有权值为0的边构成一颗有向生成树，则结束，否则找到所有边都为0的圈c，将c缩成一个超节点w，对应改变图中的边，重复开头的方法，直到找到一颗生成树~~~~~
不过我现在在郁闷为什么书上不用prime解决这个问题，我觉得prime稍微改改就可以了呀？求指导！

#16

带权的吧！先随便找一个顶点，再找权最小的邻接顶点，由这个顶点再继续找，直到找到为止