graph是什么,graph和graphy

　　Graph)——是算法中最强大的框架之一。树结构只是图的一个特例。

　　如果我们可以将我们的工作解释为一个图问题，那么这个问题至少接近解。而我们，我们的问题例子，可以用树形结构来解释，所以我们基本上有一个真正有效的解决方案。

　　邻接表及加权邻接字典

　　实现图结构最直观的方法之一就是使用邻接表。基本上，为每个节点设置一个邻接表。让我们实现最简单的一个：假设我们有n个节点，编号为0，…，n-1。

　　当然，节点可以是任何对象，可以被赋予任何标签或名称。但是，使用0，…，n-1范围内的整数会简单得多。因为如果可以用数字来表示节点，显然对我们来说索引要方便得多。

　　然后，每个邻接(邻居)列表只是一个数字列表。我们可以将它们编译成一个大小为N的主列表，并用节点号对它们进行索引。因为这些链表中节点的顺序是任意的，实际上我们是用链表来实现邻接集的。这里之所以还用列表这个术语，主要是因为传统。幸运的是，Python本身提供了独立的set类型。

　　相关：《Python基础教程》

　　让我们以下面的图为例来说明图结构的各种表示方法(当我们进行与图相关的工作时，我们需要反复遵循一个主题思想，即一个图的最佳表示方法应该取决于我们想用它做什么):

　　a，b，c，d，e，f，g，h=范围(8)

　　N=[

　　{b，c，d，e，f}，

　　{c，e}，

　　{d}，

　　{e}，

　　{f}，

　　{c，g，h}，

　　{f，h}，

　　{f，g}

　　]在图论中，N(v)表示v的邻居节点集；

　　binN[a]#邻里成员

　　真实的

　　Len(N[f])#out-degree: degree

　　3加权邻接字典

　　用字典类型代替集合或列表来表示邻接集。在dict类型中，每个邻居节点都会有一个键和一个额外的值，用来表示其邻居节点(或传出边)之间的关联，比如边的权重。

　　a，b，c，d，e，f，g，h=范围(8)

　　N=[

　　{b:2，c:1，d:3，e:9，f:4}，

　　{c:4，e:4}，

　　{d:8}，

　　{e:7}，

　　{f:5}，

　　{c:2，g:2，h:2}，

　　{f:1，h:6}，

　　{f:9，g:8}

　　]客户电话：

　　binN[a]#邻里成员

　　真实的

　　len(N[f])#出度

　　三

　　n[a][b]#边权重for(a，b)

　　2邻接矩阵

　　邻接矩阵是图的另一种表示。这种表示的主要区别在于，它不再列出每个节点的所有相邻节点。

　　a，b，c，d，e，f，g，h=范围(8)

　　N=[

　　[0,1,1,1,1,1,0,0],

　　[0,0,1,0,1,0,0,0],

　　[0,0,0,1,0,0,0,0],

　　[0,0,0,0,1,0,0,0],

　　[0,0,0,0,0,1,0,0],

　　[0,0,1,0,0,0,1,1],

　　[0,0,0,0,0,1,0,1],

　　[0,0,0,0,0,1,1,0],

　　]关于邻接矩阵：

　　(1)主对角线是从自我到自我，为0。

　　(2)线和不合度。

　　(3)列和为-度。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。