算法与数据结构——图的表示法与常用的转化算法【图文】

朱雀 2023-03-04 15:29 131阅读 0赞

《图的表示方法》

### （i）邻接矩阵表示法 ###

如图：

![format_png][]

![format_png 1][]

也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 个元素中，只有 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。

同样，对于网络中的权，也可以用类似邻接矩阵的 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。

### （ii）关联矩阵表示法 ###

![format_png][]

![format_png 2][]

也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为 -1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个 1，一个-1）可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有mn 个元素中，只有 2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。

同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。

### （iii）弧表示法 ###

![format_png][]

![format_png 3][]

例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如上：

为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储的。

### （iv）邻接表表示法 ###

邻接表表示法将图以邻接表（adjacency  lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻接表表示为

![format_png][]

![format_png 4][]

### （v）星形表示法 ###

星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点 出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。

例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下：

![format_png 5][]

![format_png][]

### 《星形表示法详解及其转化算法》 ###

注意：上面的第一张表实际上有个错误，仔细看的童鞋应该能发现，起始地址point(i) : 1 , 3 , 4 , 5 , 7 , 9 ,那个6应该是5

通常情况下会设置一个st\[i\] 数组，和STL类似， \[st\[i\],st\[i+1\]) 恰好为以结点i开头的边下标。对应于上个例子的第一张表，则该数组为：

void star2lsrs ()
     {
         memset (son , 0 , sizeof (son )); /*清零， 为零代表链表为空son */
         for(i = 1; i <= n; i ++)
         /*按逆序考虑各个结点，则最后的链表是顺序的*/
         for(j = st[i +1] -1; j >= st[i ]; j --)
             {
                 bro[j ] = son[i];
                 son[i ] = v[j ]; /*插到链表首部*/
             }
    }

图最常用的表示法是邻接矩阵和邻接表。对于静态图（建图完毕后不再修改图的结构）往往用前向星来代替邻接表，节省空间和时间。

邻接矩阵不管输入格式如何，总是很容易得到邻接矩阵，只需要注意平行边的情况。  
前向星邻接矩阵本身就包含了顶点序，因此很容易转化为前向星：

**把邻接矩阵转换为前向星表示法：**

void matrix2star ()
    {
    /*上一条的第一端点初始化为（表示未出现），边数初始化为u0m0 */
    u = m = 0;
    for(i = 1; i <= n; i ++)
    for(j = 1; j <= n; j ++)
    {
    if(a[i][j])
    {
    [++m ] = j;
    while (u < i)
    st [++u ] = m;
    }
    }
    }
     /*
    在程序中，u代表上一条边的第一个顶点编号，当u < i时代表这条边的第一端点还没有出现过，设置st[u + 1] : : : st[i]为m。
    */

把边列表转化成前向星的方法类似，只需要把第一顶点相同的结点串成链表，用计数器法进行结点编号分配，和前向星转化成左儿子-右兄弟一样每次插入到链表首部，在O(m)时间内可以建立前向星表示。当然，也可以按第一顶点为关键字直接进行快速排序，不过速度稍微慢一些。

--------------------

原文转载地址：[https://www.cnblogs.com/liushang0419/archive/2011/05/06/2039386.html][https_www.cnblogs.com_liushang0419_archive_2011_05_06_2039386.html]

[format_png]: /images/20230208/dfab1b19b5064c22a289f0a97f7ce596.png
[format_png 1]: /images/20230208/3b588318cc204f7fbe987f7e490d50b9.png
[format_png 2]: /images/20230208/cef29c629cb549b1bb1dcc2130321b1f.png
[format_png 3]: /images/20230208/2f71c996a4184ab8a5b25ad06a2c7775.png
[format_png 4]: /images/20230208/0a2f3c5a77b74fb0ac2bc8d80c7d16f6.png
[format_png 5]: /images/20230208/3415f5690ae6465e880492ac34f6cfdd.png
[https_www.cnblogs.com_liushang0419_archive_2011_05_06_2039386.html]: https://www.cnblogs.com/liushang0419/archive/2011/05/06/2039386.html