有向图php,【小龙的资结演算法秘籍】(8)有向图(directedgraph)及DAG(directedacyclicgraph)的详细介绍...

哈啰~ 大家好&＃xff0c; 之前在【小马的资结演算法秘笈】(6)超好懂的图(gragh)与树(tree) 的观念介绍介绍过什幺是graph&＃xff0c; 那什幺是directed graph呢? 其实很简单&＃xff0c;undirec...

哈啰~ 各位好&＃xff01;&＃xff0c;

以前在【小龙的资结演算法秘籍】(6)非常好懂的图(gragh)与树(tree) 的意识详细介绍详细介绍过什幺是graph&＃xff0c;

那什幺是directed graph呢?

其实不是很难&＃xff0c;undirected graph的边是沒有分方位的&＃xff0c;

边所相互连接的2个端点是相通的

譬如说这张地形图(北- 新北、桃- 桃源、竹- 新竹):

「新北」与「桃源」邻近&＃xff0c;画一条线连起來&＃xff0c;

「桃源」与「新竹」邻近&＃xff0c;画一条线连起來&＃xff0c;

相互是能够 相通的

可是如果是directed graph&＃xff0c;

大家便会把边标上方位&＃xff0c;

意味着能够 从哪儿来到哪儿&＃xff0c;

例如画成那样:

那幺含意就变为桃源跟新北是能够 相通的&＃xff0c;

可是只能桃源能够 去新竹&＃xff0c;新竹不能去桃源

由于directed graph&＃xff0c;是有专一性的&＃xff0c;

就很合适用于表达有单行线的地形图&＃xff0c;

或者用于表述有依次关係的办事次序&＃xff0c;

讨论一下一些生活上的事例协助了解吧

一、用餐次序

你来饭店用餐的情况下&＃xff0c;

餐食将会会依照一定的次序出去&＃xff0c;

用端点 A->B 表达 A要先吃了&＃xff0c;B餐食才会出現

譬如说本图表达要先吃了开胃小菜才可以吃汤和主餐&＃xff0c;

汤和主餐都吃完了才可以吃甜品

对于饮品沒有限定&＃xff0c;什幺情况下吃都能够

二、修课次序

譬如说在修课的情况下&＃xff0c;一部分课程内容会规定「先修课程内容」&＃xff0c;

还可以用有向图表述修课依次关係&＃xff0c;

譬如说图上表达要修「学习英语」以前要先修好「基础英文一」和「基础英文二」才能够 修&＃xff0c;

通识课程内容则不用先修课程内容

DAG(directed acyclic graph)

简易详细介绍完directed graph&＃xff0c;

那什幺是directed acyclic graph呢?

acyclic是沒有环的&＃xff0c;

假如一个directed graph里边沒有cycle&＃xff0c;

就称之为是一个DAG

cycle简易而言&＃xff0c;是你能够 从一个点考虑&＃xff0c;

历经一条相对路径后又回到原点&＃xff0c;

譬如说这幅图你能从A考虑&＃xff0c;

走A->B->C->D->A绕一圈返回A&＃xff0c;

这幅图便是有cycle的

相反&＃xff0c;若把图改为那样就沒有cycle

形象化而言&＃xff0c;假如用directed graph表达办事次序得话&＃xff0c;

DAG能够 确保寻找一个次序把事儿做了&＃xff0c;

要不是DAG就没法做(表达有环&＃xff0c;会相互之间把事儿卡死)&＃xff0c;

打个比方:

是我很多东西爱吃&＃xff0c;

吃鱼以前要先吃豆腐花

吃饮品以前要先吃鱼

吃苹果以前要先吃饮品

吃饮品以前要先吃豆腐花

那样的话就没法寻找考虑所述标准的进食次序

简易详细介绍topological sort

topological sort(汉语译者拓扑排序)与DAG拂面有关&＃xff0c;

即然姓名都称为sort了&＃xff0c;

表达是某类排列

topological sort便是寻找一种次序&＃xff0c;

促使你可以圆满把事儿把表达事儿顺序的directed graph做了&＃xff0c;

譬如说这幅图是用餐次序

先吃了开胃小菜才可以吃汤和主餐&＃xff0c;

汤和主餐都吃完了才可以吃甜品

饮品沒有限定&＃xff0c;什幺情况下吃都能够

那幺「开胃小菜」->「汤」->「主餐」->「甜品」->「饮品」是一个合理合法的拓扑排序&＃xff0c;

「开胃小菜」->「饮品」 ->「主餐」->「汤」->「甜品」也是一个合理合法的拓扑排序&＃xff0c;

拓扑排序有很多种多样将会排法&＃xff0c;要是不违背依次顺序的都能够

怎么知道一张有向图有木有cycle呢?

我们可以思索一个难题&＃xff0c;让你一个directed graph&＃xff0c;

你怎样可以用程序分辨这幅图有木有cycle呢?

这就留到下一章讲要怎么写程序做topological sort的情况下一併讲吧

参考文献