图的五种存储结构

作者: advanced_slowly | 来源:发表于2019-08-05 20:32 被阅读0次

1.邻接矩阵

图的邻接矩阵（Adjacency Matrix）：图的邻接矩阵用两个数组来表示图。一个一维数组存储图中顶点信息，另一个二维数组（一般称之为邻接矩阵）来存储图中的边或者弧的信息。从邻接矩阵中我们自然知道一个顶点的度（对于无向图）或者有向图中一个顶点的入度出度信息。

假设图G有n个顶点，则邻接矩阵是一个n*n的方阵。
1.对于如果图上的每条边不带权值来说，那么我们就用真（一般为1）和假（一般为0）来表示一个顶点到另一个顶点存不存在边。下面是一个图的邻接矩阵的定义：

每条边不带权值的图的邻接矩阵的定义.png
2.对于图上每条边都带权值（我们称图为网图），就将权值存进二维数组中，如下：

每条边都带权值的图的邻接矩阵的定义.png

邻接矩阵实现图的创建结构示意图.png

邻接矩阵法实现带权值的无向图的创建如下：

#pragma once
#define MAXVER 4            //最大定点数
#define INFINI 65535        //表示一个顶点到另一个顶点不存在边
typedef char VertexType;    //顶点类型可由用户定义
typedef int EdgeType;       //边类型可由用户定义

typedef struct
{
    VertexType vers[MAXVER];        //存放顶点的数组
    EdgeType edge[MAXVER][MAXVER];  //存放边的数组
    size_t verNum,edgeNum;          //当前用户顶点数和边数
}Graph;

//创建一个无向图
Graph* createGraph(Graph * graph,size_t verNum, size_t edgeNum);
//遍历权值
void traverseVer(Graph* graph);

#include "AdjacentMatrix.h"
#include <cstdio>
#include <iostream>

//创建一个无向图
Graph* createGraph(Graph* graph,size_t verNum,size_t edgeNum )
{
    //图中的顶点集合有穷非空
    if (verNum == 0)
    {
        return nullptr;
    }
    if (!graph)
    {
        return nullptr;
    }

    //无向图最大边数
    size_t maxEdge = MAXVER * (MAXVER - 1) / 2;
    if (verNum > MAXVER || edgeNum > maxEdge)
    {
        return nullptr;
    }

    graph->verNum = verNum;
    graph->edgeNum = edgeNum;
    
    //录入各个顶点值
    for (size_t i = 0 ; i < verNum ; i ++)
    {
        printf("请输入顶点值:");
        scanf("%c",&graph->vers[i]);
        getchar();
    }
    //初始化各条边的值
    for (size_t i = 0 ; i < verNum ; i ++)
    {
        for (size_t j = 0 ; j < verNum ; j ++)
        {
            //先初始化图中不存在边
            graph->edge[i][j] = INFINI;
        }
    }
    //接受用户录入的下标和权值
    int i, j, w;
    //录入各条边的值
    for (size_t k = 0 ; k < edgeNum ; k ++)
    {
        printf("请输入边(Vi,Vj)上的下标i和j和权值:");
        std::cin >> i >> j >> w;
        graph->edge[i][j] = w;
        //因为是无向图矩阵对称，无向边（V，V '）和（V',V）是一样的
        graph->edge[j][i] = graph->edge[i][j];
    }

    return graph;
}

//遍历权值
void traverseVer(Graph* graph)
{
    for (size_t i = 0; i < graph->verNum; i++)
    {
        for (size_t j = 0 ; j < graph->verNum ; j++)
        {
            printf("%d\t",graph->edge[i][j]);
        }
        printf("\n");
    }
}

按照如图输入各边（不重复）

测试的无向图.png

测试程序如下：

#include "AdjacentMatrix.h"

int main()
{
    Graph graph;
    Graph * ptr = createGraph(&graph,4,4);
    if (ptr)
    {
        traverseVer(ptr);
    }
    return 0;
}

结果可得该矩阵，证明创建树成功。假设n个顶点e条边的创建，createGraph算法的时间复杂度为O（n+n*n+e）。如果需要创建一个有向图，那么和上面一样一个一个录入边下标和权值。

邻接矩阵这种存储结构的优缺点：缺点是对于边数相对顶点较少的稀疏图来说会存在极大的空间浪费。假设有n个顶点,优点是对于有向完全图和无向完全图来说邻接矩阵是一种不错的存储结构，浪费的话也只浪费了n个顶点的容量。

2.邻接表

在树的存储结构一节中我们提到对于孩子表示法的第三种：用一段连续的存储单元（数组）存储树中的所有结点，利用一个单链表来存储数组中每个结点的孩子的信息。对于图的存储结构来说，我们也可以利用这种方法实现图的存储

邻接表(Adjacency List):这种数组与链表相结合的存储方法叫做邻接表。1.为什么不也用单链表存储图的结点信息呢？原因就是数组这种顺序存储结构读取结点信息速率快。对于顶点数组中，每个数据元素还需要存储一个指向第一个邻接顶点的指针，这样才可以查找边的信息2.图中每个顶点Vi(i > 0)的所有邻接点构成一个线性表（在无向图中这个线性表称为Vi的边表，有向图中称为顶点作为弧尾的出边表），由于邻接点的不确定性，所以用链表存储，有多少个邻接点就malloc一个空间存储邻接点，这样更不会造成空间的浪费（与邻接矩阵相比来说）。3.对于邻接表中的某个顶点来说，用户关心的是这个顶点的邻接点，完全可以遍历用单链表设计成的边表或者出边表得到，所以没必要设计成双链表。

邻接表的存储结构：
假设现在有一无向图G，如下图：

邻接表之无向图.png
则用邻接表来存储图G的邻接表存储结构为：

无向图的邻接表结构.png

从邻接表结构中，知道一个顶点的度或者判断两个顶点之间是否存在边或者求一个顶点的所有邻接顶点是很容易的。

假设现在有一有向图G，如下图：

邻接表之有向图.png
则用邻接表来存储图G的邻接表存储结构为：

有向图的邻接表结构.png
从该邻接表结构中，我们是以顶点为弧尾来存储出边表的，也可以知道一个顶点的出度信息。但是有的时候需要知道一个顶点的入度信息，这时我们可以建立一个有向图的逆邻接表，即对每个顶点Vi都建立一个链接为Vi弧头的表。其逆邻接表结构如下图所示：

有向图的逆邻接表结构.png
如果对于带权值的网图，则可以在出边表的结点中增加一个权值数据域，存储权值信息。

无向图的邻接表创建示例如下：

#pragma once
#define MAXVER 4        //最大顶点数
typedef char VertexType;    //顶点类型
//存储某个顶点的邻接点的单链表
typedef struct EdgeNode
{
    size_t adjVex;          //存储某个顶点的邻接点在数组中的下标
    struct EdgeNode* next;  //存储某个顶点的下一邻接点的地址
}EdgeNode;

//存储无向图中的所有顶点
typedef struct VertexNode
{
    VertexType data;                //存放顶点信息
    EdgeNode* firstEdge;            //存储第一个邻接点的地址
}VertexNode, AdjList[MAXVER];       //AdjList为顶点数组类型

typedef struct
{
    AdjList adjList;
    size_t verNum, edgeNum;         //无向表当前定点数和边数
}AdjListGraph;

//邻接表法存储无向图
AdjListGraph* create(AdjListGraph* graph,size_t verNum,size_t edgeNum);
//遍历无向图中所有顶点的邻接点信息
void traverseAdjVer(AdjListGraph* graph);

#include "AdjListGraph.h"
#include <cstdlib>
#include <iostream>
#include <cassert>

//邻接表法存储无向图
AdjListGraph* create(AdjListGraph* graph, size_t verNum, size_t edgeNum)
{
    //图中的顶点集合有穷非空
    if (verNum == 0)
    {
        return nullptr;
    }

    //无向图最大边数
    size_t maxEdge = MAXVER * (MAXVER - 1) / 2;
    if (verNum > MAXVER || edgeNum > maxEdge)
    {
        return nullptr;
    }

    graph->verNum = verNum;
    graph->edgeNum = edgeNum;

    //初始化顶点信息
    for (size_t i = 0 ; i < verNum ; i++)
    {
        std::cout << "请输入顶点值：";
        std::cin >> graph->adjList[i].data;
        graph->adjList[i].firstEdge = nullptr;
    }

    int i, j;   //邻接顶点的下标值
    //初始化边表信息
    for (size_t k = 0 ; k < edgeNum ; k++)
    {
        std::cout << "请输入边(Vi,Vj)上i和j的下标：";
        std::cin >> i >> j;

        //初始化顶点Vi的第一个邻接点Vj的信息
        EdgeNode* edgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
        assert(edgeNode != nullptr);

        edgeNode->adjVex = j;
        edgeNode->next = graph->adjList[i].firstEdge;
        graph->adjList[i].firstEdge = edgeNode;

        //初始化顶点Vj的第一个邻接顶点Vi的信息
        edgeNode = (EdgeNode*)malloc(sizeof(EdgeNode));
        assert(edgeNode != nullptr);

        edgeNode->adjVex = i;
        edgeNode->next = graph->adjList[j].firstEdge;
        graph->adjList[j].firstEdge = edgeNode;
    }

    return graph;

}

//遍历无向图中所有顶点的邻接点信息
void traverseAdjVer(AdjListGraph* graph)
{
    for (size_t i = 0 ; i < graph->verNum ; i++)
    {
        EdgeNode* workNode = graph->adjList[i].firstEdge;
        std::cout << "当前的顶点：" << graph->adjList[i].data << ",其邻接顶点值为：";
        while (workNode)
        {
            std::cout << graph->adjList[workNode->adjVex].data;
            workNode = workNode->next;
        }
        std::cout << std::endl;
    }
}

假设在上图（无向图）中的V0V1V2V3顶点值为ABCD，则依据下面测试程序可得结果：

#include <iostream>
#include "AdjListGraph.h"

int main()
{
    AdjListGraph graph;
    AdjListGraph* ptr = create(&graph,4,5);
    if (ptr)
    {
        traverseAdjVer(ptr);
    }
    return 0;
}

运行图3.png
根据各个顶点的邻接点的值可知用邻接表法成功实现无向图的创建。假设顶点数为n,边数为e，其create算法时间复杂度为O(n+e).利用内置的静态数组来存储图的顶点信息是很容易因为用户输入的顶点数比静态数组容量大导致存储图失败，所以我们可以动态分配一段连续的存储空间来存储顶点的信息。这里就不实现了。

邻接表的优缺点：优点是：邻接表存储图，既能够知道一个顶点的度和顶点的邻接结点的信息，并且更不会造成空间的浪费。缺点是邻接表存储有向图时，如果关心的是顶点的出度问题自然用邻接表结构，但是想了解入度需要遍历图才知道（需要考虑逆邻接表）。

3.十字链表

十字链表(Orthogonal List)：有向图的一种存储方法，它把邻接表和逆邻接表结合起来，因此在十字链表结构中可以知道一个顶点的入度和出度情况。
重新定义顶点表的结点如下图：

顶点表中结点结构.png
其中data是顶点的值，firstin指向入边表的第一个结点（头指针），firstout指向出边表的第一个结点。
边表结点结构为：

边表结点结构.png
其中tailvex是弧尾在顶点表的下标，headvex是弧头在顶点表的下标。headlink是指入边表指针域，指向终点相同（弧头相同）的下一条边，taillink是出边表指针域，指向起点相同的下一条边。

现在有一有向图如下图：

十字链表之有向图.png

则它的存储结构示意图为：

十字链表存储结构示意图.png

其定义如下：

#pragma once
typedef char VertexType;
#define VerNum 4
//定义边表结构
typedef struct EdgeTable
{
    size_t tailVex; //弧尾在顶点表中的下标
    size_t headVex; //弧头在顶点表中的下标
    struct EdgeTable* headLink; //入边表指针域，指向弧头相同的下一条边
    struct EdgeTable* tailLink; //出边表指针域，指向弧尾相同的下一条边
}EdgeTable;

//顶点表结构
typedef struct
{
    VertexType data;    //顶点值
    EdgeTable* firstIn; //指向入边表第一个结点
    EdgeTable* firstOut;//指向出边表第一个结点
}VertexTable;

typedef struct
{
    VertexTable vertxt[VerNum]; //顶点数组
    size_t verNum, edgeNum;     //当前顶点数和边数
}Graph;

十字链表是用来存储有向图的，这样可以看出一个顶点的出入度信息。对于无向图来说完全没必要用十字链表来存储。

4.邻接多重表(adjacency multilist)

在无向图中，因为我们关注的是顶点的信息，在考虑节约空间的情况下我们利用邻接表来存储无向图。但是如果我们关注的是边的信息，例如需要删除某条边对于邻接表来说是挺繁琐的。它需要操作两个单链表删除两个结点。因此我们仿照十字链表的方式对边表结点结构重新定义如下图：

邻接多重表之边表结点结构.png
其中ivex和jvex是与某条边依附的两个顶点在顶点表的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构了。现在有一无向图：

示例无向图.png

它的邻接多重表结构为：

邻接多重表结构.png

多重邻接表的优点：对于边的操作相比于邻接表来说更加方便。比如说我们现在需要删除(V0,V2)这条边，只需将69步骤中的指针改为nullptr即可。

5.边集数组

边集数组(edgeset array)：边集数组是由两个数组组成，一个存储顶点信息，另一个存储边的信息，这个边数组中的每个数据元素由起点下标，终点下标，和权组成（如果边上含有权值的话）。
边数组结构如下图：

边数组结构.png

边集数组实现图的存储的优缺点：优点是对于边的操作方便快捷，操作的只是数组元素。比如说删除某条边，只需要删除一个数组元素。缺点是：对于图的顶点信息，我们只有遍历整个边数组才知道，这个费时。因此对于关注边的操作来说，边集数组更加方便。

图的五种存储结构

1.邻接矩阵

2.邻接表

3.十字链表

4.邻接多重表(adjacency multilist)

5.边集数组

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读