图的存储表示

Published on 2016 - 12 - 28

图的存储表示方法有很多种,常用的有3种:邻接矩阵(Adjacency Matrix)、邻接表(Adjacency List)、邻接多重表(Adjacency Multilists)。本文只介绍前面两种。

邻接矩阵

有向图和无向图的邻接矩阵

在邻接矩阵存储方法中,除了一个记录各个顶点信息的顶点数组外,还有一个表示各个顶点之间关系的矩阵,称为邻接矩阵。设G(V,E)是一个具有n个顶点的图,则图的邻接矩阵是一个n×n的二维数组,用Edge[n][n]表示,它的定义为:

例如,在图1中,为了表示顶点信息,特意将顶点的标号用字母A、B、C、D、E和F表示,各顶点的信息存储在顶点数组中,如图1(b)所示,注意在C/C++语言中,数组元素下标是从0开始计起的。G1的邻接矩阵如图1(c)所示,从图中可以看出,无向图的邻接矩阵是沿主对角线对称的。

为了表示顶点信息,在图2中特意将顶点的标号用字母A、B、C、D、E、F和G表示,各顶点的信息存储在顶点数组中,如图2(b)所示。G2的邻接矩阵如图2(c)所示,从该图中可以看出,有向图的邻接矩阵不一定是沿主对角线对称的。

注意:如果图中存在自身环(Self Loop,连接某个顶点自身的边)和重边(Multiple Edge),多条边的起点一样,终点也一样,也称为平行边(Parallel Edge)的情形,则无法用邻接矩阵存储。

从图的邻接矩阵可以获得什么信息?对无向图的邻接矩阵来说,如果Edge[i][j]=1,则表示顶点i和顶点j之间有一条边。因此,邻接矩阵Edge第i行所有元素中元素值为1的个数表示顶点i的度数,第i列所有元素中元素值为1的个数也表示顶点i的度数,即:

而对有向图的邻接矩阵来说,如果Edge[i][j]=1,则表示存在从顶点i到顶点j有一条有向边,i是起点,j是终点。因此,邻接矩阵Edge第i行所有元素中元素值为1的个数表示顶点i的出度,第i列所有元素中元素值为1的个数表示顶点i的入度,即:

说明:由于在C/C++语言中,数组元素下标是从0开始计起的,而图的顶点序号通常是从1开始计起的,所以数组元素下标i与第i+1个顶点对应。例如,例1的分析中提到邻接矩阵中第i行与第i+1个顶点对应。

例1 用邻接矩阵存储有向图,并输出各顶点的出度和入度。

  • 输入描述:

输入文件中包含多个测试数据,每个测试数据描述了一个无权有向图。每个测试数据的第一行为两个正整数n和m,1≤n≤100,1≤m≤500,分别表示该有向图的顶点数目和边数,顶点的序号从1开始计起。接下来有m行,每行为两个正整数,用空格隔开,分别表示一条边的起点和终点。每条边出现一次且仅一次,图中不存在自身环和重边。输入文件最后一行为0 0,表示输入数据结束。

  • 输出描述:

对输入文件中的每个有向图,输出两行:第1行为n个正整数,表示每个顶点的出度;第2行也为n个正整数,表示每个顶点的入度。每两个正整数之间用一个空格隔开,每行的最后一个正整数之后没有空格。

  • 分析:

在程序中可以使用一个二维数组Edge存储表示邻接矩阵。输入文件中顶点的序号是从1开始计起的,所以在将有向边<u,v>存储表示到邻接矩阵Edge时,需要将元素Edge[u-1][v-1]的值置为1。

本题中的有向图都是无权图,邻接矩阵中每个元素要么为1,要么为0。第i+1个顶点的出度等于邻接矩阵中第i行所有元素中元素值为l的个数,把第i行所有元素值累加起来,得到的结果也是该顶点的出度。同理,在计算第i+l个顶点的入度时,也只需将第i列所有元素值累加起来即可。

题目要求在输出n个顶点的出度(和入度)时,每两个正整数之间用一个空格隔开,最后一个正整数之后没有空格。可以采取的策略是:输出第0个顶点的出度时前面没有空格,输出后面n-1个顶点的出度时都先输出一个空格。

代码如下:

#define MAXN 100 //顶点个数最大值
int Edge[MAXN][MAXN]; //邻接矩阵
int main() 
{
    int i,j; //循环变量
    int n,m; //顶点个数、边数
    int u,v; //边的起点和终点
    int od, id; //顶点的出度和入度
    while(1) 
    {
        scanf("%d%d", &n, &m); //读入顶点个数n和边数m
        if(n == 0 && m == 0 ) break; //输入数据结束
        memset(Edge,0,sizeof(Edge));
        for(i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v); //读入边的起点和终点
            Edge[u-1][v-1] = 1; //构造邻接矩阵
        }
        for(i=0; i<n; i++) //求各顶点的出度
        {
            od = 0;
            for(j=0; j<n; j++) od += Edge[i][j]; //累加第i行
            if(i == 0) printf("%d",od);
            else printf(" %d",od);
        }
        printf("\n");
        for(i=0; i<n; i++) //求各顶点的入度
        {
            id = 0;
            for(j=0; j<n; j++) id += Edge[j][i]; //累加第i列
            if(i==0) printf("%d", id);
            else printf(" %d",id);
        }
        printf("\n");
    }
    return 0;
} 

例2 青蛙的邻居(Frogs' Neighborhood)

  • 题目来源:

POJ Monthly-2004.05.15, POJ1659

  • 题目描述:

未名湖附近共有n个大小湖泊L1,L2,…,Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1≤i≤n)。如果湖泊Li和Lj之间有水路相连,则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目为x1,x2,…xn,请给出每两个湖泊之间的相连关系。

  • 输入描述:

第一行是测试数据的组数t(0≤t≤20)。每组数据包括两行,第一行是整数n(2≤n≤10),第二行是n个整数,x1,x2,…,xn(0≤xi<n)。

  • 输出描述:

对输入的每组测试数据,如果不存在可能的相连关系,输出"NO";否则输出"YES",并用n×n的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

  • 分析:

本题的意思实际上是给定一个非负整数序列,问是不是一个可图的序列,也就是说能不能根据这个序列构造一个图。这需要根据Havel-Hakimi定理(定理2)中的方法来构图,并在构图中判断是否出现了不合理的情形。有以下两种不合理的情形。

  1. 某次对剩下序列排序后,最大的度数(设为d1)超过了剩下的顶点数。
  2. 对最大度数后面的d1个度数各减1后,出现了负数。

一旦出现了以上两种情形之一,即可判定该序列不是可图的。

如果一个序列是可图的,本题还要求输出构造得到的图的邻接矩阵,实现思路如下。

  1. 为了确保顶点序号与输入时的度数顺序一致,特意声明了一个vertex结构体,包含了顶点的度和序号两个成员。
  2. 每次对剩下的顶点按度数从大到小的顺序排序后,设最前面的顶点(即当前度数最大的顶点)序号为i、度数为d1,对后面d1个顶点每个顶点(序号设为j)度数减1,并连边,即在邻接矩阵Edge中设置Edge[i][j]和Edge[j][i]为1。

代码如下:

#define N 15
struct vertex
{
    int degree; //顶点的度
    int index; //顶点的序号
} v[N];

int cmp(const viod *a, const viod *b)
{
    return ((vertex*)b)->degree - ((vertex*)a)->degree;
}

int main()
{
    int r,k,p,q; //循环变量
    int i,j; //顶点序号(用于确定图中边的两个顶点;
    int dl;
    int T,n; //测试数据个数,湖泊个数
    int Edge[N][N], flag; //邻接矩阵,是否存在合理相邻关系的标志
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%d", &v[i].degree);
            v[i].index = i; //按输入顺序给每个湖泊编号
        }
        memset(Edge,0,sizeof(Edge));
        flag = 1;
        for(k=0; k<n&&flag; k++)
        {
            //对v数组后n-k个元素按非递增顺序排序
            qsort(v+k,n-k,sizeof(vertex),cmp);
            i = v[k].index; //第k个顶点的序号

有向网和无向网的邻接矩阵

对于网络(即带权值的图),邻接矩阵的定义为:

在编程实现时,可以用一个比较大的常量表示无穷大∞。

在无向网的邻接矩阵中,如果0<Edge[i][j]<∞,则顶点i和顶点j之间有一条无向边,其权值为Edge[i][j]。从图中可以看出,无向网的邻接矩阵也是沿主对角线对称的。

在有向网的邻接矩阵中,如果0<Edge[i][j]<∞,则从顶点i到顶点j有一条有向边,其权值为Edge[i][j]。从图中可以看出,有向网的邻接矩阵不一定是沿对主角线对称的。

邻接表

尽管ACM/ICPC中绝大多数图论题目在求解时可以采用邻接矩阵存储图,但由于邻接矩阵无法存储带自身环(或重边)的图,所以有时不得不采用邻接表来存储图。另外,当图的边数(相对于邻接矩阵中的元素个数,即n×n)较少时,使用邻接矩阵存储会浪费较多的存储空间,而用邻接表存储可以节省存储空间。

所谓邻接表(Adjacency list),就是把从同一个顶点发出的边连接在同一个称为边链表的单链表中。边链表的每个结点代表一条边,称为边结点。每个边结点有2个域:该边终点的序号,以及指向下一个边结点的指针。在邻接表中,还需要一个用于存储顶点信息的顶点数组。

例如,图3(a)所示的有向图对应的邻接表如图3(b)所示。在顶点数组中,每个元素有两个成员:一个成员用来存储顶点信息;另一个成员为该顶点的边链表的表头指针,指向该顶点的边链表。如果没有从某个顶点发出的边,则该顶点没有边链表,因此表头指针为空,如图3(b)中的顶点G。在该图中,如果指针为空,则用符号“∧”表示。

在邻接表每个顶点的边链表中,各边结点所表示的边都是从该顶点发出的边,因此这种邻接表也称为出边表。采用邻接表存储图时,求顶点的出度很方便,只需要统计每个顶点的边链表中边结点的个数即可,但在求顶点的入度时就比较麻烦。

在图3(b)中,顶点B的边链表有3个边结点,分别表示边<B,F>、<B,E>和<B,C>,因此顶点B的出度为3;顶点C的边链表中只有1个边结点,表示边<C,E>,因此顶点C的出度为1。

如果需要统计各顶点的入度,可以采用逆邻接表存储表示图。所谓逆邻接表,也称为入边表,就是把进入同一个顶点的边链接在同一个边链表中。

例如,图4(a)所示的有向图对应的逆邻接表如图4(b)所示。在图4(b)中,顶点B的边链表有2个边结点,分别表示边<E,B>和<A,B>,因此顶点B的入度为2;顶点C的边链表中也有2个边结点,分别表示边<D,C>和<B,C>,因此顶点C的入度也为2。

因为无向图中的边没有方向性,所以无向图的邻接表没有入边表和出边表之分。在无向图的邻接表中,与顶点v相关联的边都链接到该顶点的边链表中。无向图的每条边在邻接表里出现两次。例如,图5(a)所示的无向图对应的邻接表如图5(b)所示。

在图5(b)中,顶点B的边链表中有5个边结点,分别表示边(B,F)、(B,E)、(B,D)、(B,C)和(B,A),因此顶点B的度为5;顶点C的边链表中有4个边结点,分别表示边(C,E)、(C,D)、(C,B)和(C,A),因此顶点C的度为4。边(B,C)分别出现在顶点B和顶点C的边链表中。

说明:如果用邻接表存储有向网或无向网,则在边结点中还应增加一个成员,用于存储边的权值。

接下来以有向图为例介绍邻接表的实现方法。为了方便求解顶点的出度和入度,在实现时,把出边表和入边表同时包含在图的邻接表结构中。

有向图的邻接表用一个结构体LGraph存储表示,其中包含3个成员:顶点数组vertexs,顶点数vexnum和边的数目arcnum,其中顶点数组vertexs中每个元素都是VNode结构体变量。VNode结构体变量存储图中每个顶点,它包含3个成员:顶点信息、出边表的表头指针和入边表的表头指针,其中后面两个成员都是ArcNode结构体类型的指针。ArcNode结构体存储边链表中的边结点,它包含两个成员:边的另一个邻接点的序号,以及指向下一个边结点的指针。

上述提及的3个结构体声明如下。

声明了有向图的邻接表结构体LGraph后,构造有向图G可以采取全局函数CreateLG()来实现,代码如下。在CreateLG()函数中,约定:构造邻接表时,先输入顶点个数和边数,然后按“起点/终点”的格式输入每条有向边,详见例3的输入/输出描述;注意在输入数据时,顶点序号从1开始计起,而在存储时顶点序号从0开始计起。

构造有向图邻接表(出边表)的过程,可以用图6所示的过程来表示。在读入边“2 3”后,申请一个边结点,并链入到顶点1的表头指针后面。再读入边“2 5”,又申请一个边结点,再插入到顶点1的表头指针后面。如图6(b)所示,在顶点1表头指针与边结点<1,2>之间插入了一个边结点<1,4>。请注意输入数据中顶点序号是从1开始计起的,在处理时先减1再构造边结点。

使用完有向图G的邻接表后,应该释放图G各顶点的出边表和入边表中所有边结点所占的存储空间,可以使用全局函数DeleteLG实现,代码详见例3。

以上声明的邻接表及定义的全局函数使用方法详见例3。

例3 用邻接表存储有向图,并输出各顶点的出度和入度。

  • 输入描述:

输入文件中包含多个测试数据,每个测试数据描述了一个无权有向图。每个测试数据的第一行为两个正整数n和m,1≤n≤100,1≤m≤500,分别表示该有向图的顶点数目和边数,顶点的序号从1开始计起。接下来有m行,每行为两个正整数,用空格隔开,分别表示一条边的起点和终点。每条边出现一次且仅一次,图中不存在自身环和重边。输入文件最后一行为0 0,表示输入数据结束。

  • 输出描述:

对输入文件中的每个有向图,输出两行:第1行为n个正整数,表示每个顶点的出度;第2行也为n个正整数,表示每个顶点的入度。每两个正整数之间用一个空格隔开,每行的最后一个正整数之后没有空格。

  • 分析:

用邻接表存储图,可以表示重边和自身环的情形。例如,样例输入中第2个测试数据所描述的有向图及对应的邻接表如图7所示,该有向图既包含重边,又包含自身环。在图7(a)中,有向边<2,2>为自身环,对应到图7(b)所示的邻接表中,顶点1的入边表和出边表都有一个边结点,其adjvex分量均为1。另外,在图7(a)中,<2,3>和<2,3>为重边,对应到图7(b),在顶点1的出边表中,有两个边结点的adjvex分量均为2;以及在顶点2的入边表中,有两个边结点的adjvex分量均为1。

统计第i个顶点的出度的方法是在其出边表中统计边结点的个数,统计第i个顶点的入度的方法是在其入边表中统计边结点的个数。

注意,为了实现“当读入的顶点个数n为0时,输入结束,退出main函数”,下面的代码将设置邻接表的vexnum成员和arcnum成员,以及读入顶点个数的处理代码由CreateLG函数移至main函数的while循环中。

代码如下:


关于邻接矩阵和邻接表的进一步讨论

存储方式对算法复杂度的影响

时间复杂度:邻接表里直接存储了边的信息,浏览完所有的边,对有向图来说,时间复杂度是O(m),对无向图时间复杂度是O(2×m)。而邻接矩阵是间接存储边,浏览完所有的边,复杂度是O(n2)。

空间复杂度:邻接表里除了存储m条边所对应的边结点外,还需要一个顶点数组,存储各顶点的顶点信息及各边链表的表头指针,总的空间复杂度为O(n+m)(或O(n+2m));而用邻接矩阵存储图,需要n×n规模的存储单元,其空间复杂度为O(n2)。当边的数目相对于n×n比较小时,邻接矩阵里存储了较多的无用信息,用邻接表可以节省较多的存储空间。

在求解问题时可以灵活地存储表示图

在求解实际问题时,有时并不需要严格采用邻接矩阵或邻接表来存储图。例如,当图中顶点个数确定以后(这里假设顶点序号是连续的),图的结构就唯一地取决于边的信息,因此可以把每条边的信息(起点、终点、权值等)存储到一个数组里,在针对该图进行某种处理时只需要访问边的数组中每个元素即可。

参考文档