图是什么玩意, 怎么表示它?

数据结构

谈到数据结构，我觉得创造一种数据结构的初衷，应该是通过该数据结构完成对现实问题的建模和处理，最后当然能用数学或者计算机对这些问题进行处理和分析。 其中一种建模的过程就是使用数据结构去表示问题，而处理就是相应的算法。 

比如你要算卦，那么大师需要知道你的生辰年月。 那么它可能需要一个数据结构(一个点)去保存这个生辰年月，并且能够在它复杂的算法中随时调用到这个数据。假如大师需要给你解签的话，那么大师的大脑数据库里面肯定需要有某某签的相应信息，这时候很可能就需要一个线性表去保存和查找解签的信息。

但是大师并不是世界上拥有最复杂数据结构的人，你的三姑六大妈才拥有最复杂的数据结构。想想每年过年的时候,她们能够给你如数家珍般地数出你三表哥的大姨夫又和姑丈的儿子发生了矛盾之类的。 这种复杂的关系，只能用一种更高级的数据结构去表示它，而且还要保证能够去操纵和运算，这时候，你就需要图这种东西了。

1.1 我们遇到过什么样的数据结构?

• 点(Vertex)  就是单独的一个数据表示。可以用来表示一个人的年龄，一只猪的重量...

  点的最简单集合是线性表(Linear structure)，线性表就是一堆点首尾相接在一块的集合，形象一点看就是一直线。直线上的每个节点只和他前后一个节点有关联。（关联度非常低了）。堆栈，队列，数组都是线性表的一些特殊形式。

• 树(Tree) 线性表的一种集合就是树（具体解释看下图）。 一棵树可以看成由好几个线性表组成的集合。

• 图(Tree)  就是点，线，树的集合。在图中，任意两个点和点之间可以存在或者不存在关联，自由度很大。

1.2 一些描述图的习惯与分类

图的表示为G(V,E)，G为表示图的最大集合，V为表示图中所有点的集合，E为边集，表示G中所有的边。所以理解图是什么，也可以理解为 给了对已给出节点的所有关联的集合。G的本身是很抽象的数据结构，但是本质是为了表示 点与点之间复杂关联的数据结构，用途取决于如何把点和这些关联映射到现有的生活中，例如点可以映射为人，边映射为人和人之间是否认识， 这就是一张人际网络图，如果点代表路由器，边代表了连通的网线，这就是一种设备网络图，如果点是具体的事件，边是事件之间的需因果关系，这就是事件因果图。

图的分类上分为有向图和无向图，有向和无向是针对边的，字面即可理解，边有方向就是有向图，反之亦然。有向图的应用更广泛，因为无向图可以被表示为双向的有向图，所以图的算法经常采用有向图最为输入数据。

1.3 图的基本储存结构

一个图需要保存在我们的计算机中, 就需要建立在一些已有的基本数据结构上，比如说C语言中常见的 数组 和 链表。

图经常用的是两种储存结构：图链表(Graph link list) 和 图矩阵(Graph matrix)。

1.3.1 图链表(Graph link list)

假设一个图中有v个结点。 那么可以用v个链表去表示，每个链表的开头是V集合中的一个点，链表的后续内容就是与这个点有关联的点。例如存在边(u,a), (u,b),(u,c),那么以u 开头的链表里 就会储存三个节点 分别是a,b,c，

该储存结构的空间复杂度是O(V+E)，因为存在V个链表，需要V个节点去作为V个链表的头需要O(V)的储存空间，再看每个链表存的实际上存在的边的信息所以整体上看除去头的位置 还需要O(E）的空间去储存所有的边，只不过被分散到了每个链表里，但是整体看就是O(E）个节点，所以是O(V+E)的空间复杂度.

1.3.2 图矩阵(Graph matrix)

为一个V x V的矩阵，这种储存办法的空间复杂度为O（V^2），即这个矩阵的大小，假设矩阵为C,Cij 如果为1，即存在ij这条边，如果为0 则不存在。 当然Cij的值也可以不是01，是另外的信息 例如边的权重。

最后我们比较一下这两种数据结构，先分析一下E和V的关系，考虑一个全互联的图，就是图中每两个点都互相连接，这是边最多的情况。此时E=O(V^2)，这属于密集图，那么图链表的储存为O(V+E)，也就是O(V+V^2)  = O（V^2），而图矩阵呢 也是O(V^2)。   

如果是稀松图呢，就是没有那么多边的图，E没有达到O(V^2)这种级别，link lists 就是O(V+E)，可以写成O(V)， 而matrix还是O(V^2)。

所以说图链表的存储复杂度会更低, 当对存储空间敏感的时候可以使用图链表，以减少空间的开销。 当然图矩阵方便的地方在于，可以将图作为矩阵对待，一些对图的运算可以简化为对矩阵的运算，这时候强大的线性代数可以派上用场了。

1.4 一些关于图的有趣问题

一些趣题选摘(from 算法导论)！

1.4.1 名人问题

在一次Party中， 有V个人，其中可能会有一些高傲的社交名媛(名人)出现, 所有人都认识他, 但他不认识所有人。 问题是，如何在O(V)的时间内，通过问每个人问题(比如，你认不认识某人),确定一个Party里面有名人出现。

(精确的问题描述如下图...名词解释: 1. adjacency-matrix: 其实就是图矩阵  2. universal sink: 全局汇, 也就是"名人" 3. in-degree: 指向它的关系  4. out-degree: 它指向别的点的关系)

这个问题有趣的地方在于，使用图矩阵表示的Party人群关系时，空间复杂度为O(V^2). 但是如何能在O(V)的时间里面确定有没有名人(universal link)出现? 甚至都不用把全图的关系遍历。

解决问题的关键在于如何充分利用每个问题的信息。当你问A，你认不认识B，如果A说不认识B, 那么直接可以说B不是名人, 就不用再去询问其他人是不是认识B了,因为名人谁都知道(减少了询问量)。如果A回答是他认识B，这代表了什么呢，这代表了两点A不是名人，因为名人不认识其他人，这样无论A回答认识还是不认识，都排除了一个可能!!

总共有V个人，每问一次能排查一个，那么最坏的情况也就是问V-1次.所以这个问题可以根据每次问答的信息进行减小搜索空间,从而在O(V)时间里求解名人是否出现的问题。

(伪代码,is here)

Find_Universal_Sink(Graph Matrix m[V][V}){
i=0;            // i是我们正在问的那个家伙 就是上面说的A；
j=0;            // j 是我们问的i 是不是认识的那个家伙 就是上面说的B;
while(i!=V&&j!=V)
    if(m[i][j] =0 &&i !=j) // 这是表示 i 不认识 j, 所以 j 肯定不是名人，跳过该 j
           j++;
    else if(m[i][j] =1 &&i !=j)      // i 认识 j, 那么i肯定不是名人，跳过该 i. 因为他已经将自己排除, 继续问他没有意义，别人照样能提供名人的信息，可以不追究他了
           i++;
    else // i=j 就是问了自己是不是认识自己这种问题。。。
           j++;
}
if i =V
       print j
else 
       print i;
//输出即为unversial_sink
}

 假如是 图是用 图链表的方式存储的，那么这个问题又怎么解决呢?

1.4.2 计算有向图的In-degree

  在链表存储中， 一个节点的out-degree 很容易被计算，就从这个节点出发，计算链表的长度就可以了。 计算所有节点的out-degree 只需要遍历图链表的时间O(V+E)。

  但是in-degree的话需要遍历全图(V个链表)才能计算出一个，于是时间需要O(V(V+E)). 有没有更好的办法? 按经验来说，要减少时间复杂度就增加一个空间度试试.

于是假设我们用个数组Indgree[V]去储存每个V的indgree次数，这样遍历一次就够了.

(写一下算法伪代码)

Calculate_Outdegree(){
    for(all vertex u in G.V)
    for(all vertex v of u.adj)  //adj means u's adjacency
              u.outdegree+;
}
 
Calculate_Indegree(){
    Put all G.V in hash table Indegree[V];
    for(all vertex u in G.V)
    for(all vertex v of u.adj)  //adj means u's adjacency
             Indegree[v]++;
}

先到这里

转载本站文章《图是什么玩意, 怎么表示它?》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/519.html