构建复杂网络的几种方法（邻接矩阵，邻接表，十字链表，邻接多重表）

通常意义下的链表有单链表，双向链表，循环链表等，而复杂网络每个节点可能会同时指向任意个节点，从数据结构上来说两者是不同的。

所以首先我们先认识一下数据结构有哪些。

1. 数据结构

数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。

• 线性结构

简单地说，线性结构就是表中各个结点具有线性关系。

如果从数据结构的语言来描述，线性结构应该包括如下几点：

1）线性结构是非空集。

2）线性结构有且仅有一个开始结点和一个终端结点。

3）线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点。

线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。

• 非线性结构

简单地说，非线性结构就是表中各个结点之间具有多个对应关系。

如果从数据结构的语言来描述，非线性结构应该包括如下几点：

1）非线性结构是非空集。

2）非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点。

在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。

而此处要讲到的网络结构就是一种非线性结构，常见的网络结构有以下几种：

2. 复杂网络的数组表示

我们一般使用数组（邻接矩阵）表示上面相应的网络（其中+∞可以用很大的数实现）： 

//图的邻接矩阵存储表示
#define MaxInt 32767      //表示极大值，即∞
#define MVNum 100         //最大顶点数
typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;      //假设边的权值类型为整形
typedef struct    
{
  VerTexType vexs[MVNum]; //顶点表
  ArcType arcs[MVNum][MVNum];   //邻接矩阵
  int vexnum,arcnum;      //图的当前点数和边数
}AMGraph;

 

3. 复杂网络的邻接表表示

使用邻接表（在表示树数据结构中，也称为孩子表示法）表示有向网络（图），有两种方法，一个是以起点存储，一个是以终点存储，后一种可以叫做逆邻接表（后面还会介绍）。

使用起点存储时，我们可以把一个双向网络表示如下：

由上可见邻接表的结构由顺序节点和每个节点下的相连节点组成，后者使用链表储存，由上可以看出邻接表相当于一个列数伸缩可调的数组。

相应的，在有权重的网络中可以在链表的数据中再添加一个权重项：

邻接表是一个二维容器，第一维描述某个点，使用顺序存储（数组），第二维描述这个点所对应的边集们，使用链式存储（链表）。

网络的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。

如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。

对于无向网络来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

实现邻接表的方法绝对有100种以上。

即使是前向星这种东西也是邻接表，因为它还是描述某个点和这个点所对应的边集们。

常用的邻接表在c++中必须有开O1以及以上编译的条件，不然没有测试的效率无任何意义。

第一维是描述点的。

在c++中可以用vector,list，forward_list，deque，map，multimap，unordered_map，unordered_multimap等（一般不能用set，mutiset，unordered_set，unordered_multiset ）。

按照你的要求去选择。

一般来讲存完图以后不涉及点的加入与删除优先使用vector.map，multimap，unordered_map，unordered_multimap。

第二维是描述这个点的边集，可以用全部的容器。

也是的一般来讲存完图以后,不涉及点的加入与删除优先使用vector，空间充足可以考虑deque。

涉及点的删除用forward_list或者是list，map，multimap，unordered_map，unordered_multimap。

下面先对有向无权网络进行编程，分别使用c和c++：

//c
//顶点的结构体
typedef struct VNode     //对结构体使用 typedef 来定义一个新的数据类型名字；
                         //然后使用这个新的数据类型来直接定义结构变量；
{
  VertType data;   //顶点的信息
  ArcNode *first;  //顶点的第一条边；
}VNode;

//边链表的结构体
typedef struct ArcNode
{
  int adjvex;     //边指向的顶点（与上述顶点相连）的数组下标（伪指针）；
  InfoType info;  //边相关的信息（权值）；
  struct ArcNode *next   //指向下一条边的指针；
}ArcNode;

//图的结构体
typedef struct
{
  VNode vexs[MAXVNUM];    //顶点的数组；
  int vexnum,arcnum;      //图的顶点数|V|和边数|E|；
}ALGraph;

//c++
using namespace std
struct GraphNode{
  int label;  //网络节点
  vector neighbors; //存储与节点相邻的节点指针
};

int main(){
  GraphNode G[4];  //创建长度为4的网络节点结构体数组
  //0、1、2、3四个顶点就对应了G[0]、G[1]、G[2]、G[3]四个结构体
  for (int i=0;i<4;i++){  //使用循环为表头中的label赋值
    G[i].label=i;  //节点编号赋值为0、1、2、3
  }
  //添加0到2和3的边
  G[0].neighbors.push_back(&G[2]);
  G[0].neighbors.push_back(&G[3]);
  //添加1到0和2的边
  G[1].neighbors.push_back(&G[0]);
  G[1].neighbors.push_back(&G[2]);
  //添加2到3的边
  G[2].neighbors.push_back(&G[3]);
  //添加3到0的边
  G[3].neighbors.push_back(&G[0]);

  //输出打印邻接表
  printf("G:\n");
  for (int i=0;i<4;i++){
    printf("Label(%d):",i);
    for (int j=0;jlabel);
    }
    printf("\n");
  }
  return 0;
}

4. 邻接矩阵与邻接表的比较

总的来说，存储网络的时候可以使用数组（邻接矩阵），也可以使用链表（邻接链表），后者可以看作一种比较特殊的数组，其实都是数据存储的结构。

相较前者，链表具有的优势有：

• 不需要连续的内存存储，所以可以存储更大的网络；
• 删除添加节点的 *** 作灵活，且设计的内存 *** 作小，数组改变长度的时候，需要平移某个位置后面的所有内存；

	邻接表	邻接矩阵
空间复杂度	无向图O(|V|+2|E|)，有向图O(|V|+|E|)，适合存储稀疏图	O(|V|2)，适合存储稠密图
表示方式	边链表结点的顺序是任意的，不唯一	矩阵是固定的，唯一
求度、出度、入度	求无向图的度和有向图的出度的时间复杂度为O(1)，求有向图的入度为O(|E|)	遍历矩阵的行或列，时间复杂度为O(|V|)

那么在表示网络中，数组与链表之间如何做出选择呢？

如果把存储空间多少作为标准，首先判断网络是否稀疏（E表示边的条数，V表示顶点个数）：

 一般使用邻接表表示稀疏图，而用数组表示稠密图：

 如果把判断两个节点是否相连接作为标准，则使用数组（复杂度为O(1)）：

 

 另外上述讲到的都是以节点为主要存储对象，其实还可以构建专门存储边的数组，当然会遗漏点（没有边的情况）：

	起点	终点	权重
1	0	4	20
2	0	2	30
3	1	0	10
4	1	2	40
5	2	3	50
6	3	4	70
7	4	3	60

这种存储方法在稠密网络情形下，其数量级为O(2)，数组的数量级为O(2)，邻接表也数量级也为O(2)；在稀疏网络的情形下，只有数组的数量级还是O(2)，其余两种方法会有所减小。

5. 复杂网络的其他表示方法

到此对于网络的构建已经差不多了，但是对于某些所需功能，需要对邻接表做一下拓展：

• 逆邻接表

上面是以起点做邻接表的，当我们搜索某个节点的出度时（也就是以此节点作为起点时），我们可以直接找到某个节点及其容器下的链表，而当我们搜索某个节点的入度时（也就是以此节点作为终点时），需要一个一个节点去搜索，这样时比较麻烦的，为了解决这一点，我们可以在构建含起点的邻接表之外，构建含终点的邻接表，此时被称为逆邻接表

•  十字链表

上述讲到我们可以使用邻接表和逆邻接表表示网络，但是这种双份的存储显得非常冗余，为了解决这个问题，需要引进一种新的数据结构，即十字链表。

创建节点数据结构的时候，其数量与节点的数量一致，而创建边的数据结构的时候，其为有向边的数量。

节点的数据结构里面包含了Data，firstIn，firstOut三种类型，Data为节点的值，firstIn为指向终点为该节点的边的指针，firstOut为指向起点为该节点的边的指针，在边的数据结构里面有四项，start为边的起点，end为边的终点，nextIn为指向终点为该节点的下一个边的指针，nextOut为指向起点为该节点的下一个边的指针。

由上可见边的数据结构会被两个节点指向，所以称为十字链表。

值得一提的是，之所以需要建立边的数据结构有两个目的，一个是存储边是否连接以及与谁的信息，第二个是可以在上述结构中增加一项权重数据。

•  邻接多重表

上面讲到的是有向图，在普通的邻接表表示无向图的时候，可能会造成同一条边被两重存储的现象：

 为了解决这个问题，我们引入邻接多重表：

 

 

创建节点数据结构的时候，其数量与节点的数量一致，而创建边的数据结构的时候，其数量为无向边的数量。

节点的数据结构里面包含了Data，first两种类型，Data为节点的值，first为指向与该节点相连的边的指针，在边的数据结构里面有四项，Vi和Vj为相连节点，ViNext为指向与节点Vi相连的下一条边的指针，VjNext为指向与节点Vj相连的下一条边的指针。

5.各种数据结构的比较 

	边链表总数	空间复杂度	求顶点出度的 时间复杂度	求顶点入度的 时间复杂度
无向图邻接表	2|E|	O(|V|+2|E|)	O(1)
有向图邻接表	|E|	O(|V|+|E|)	O(1)~O(|E|)	O(1)~O(|E|)
十字链表	|E|	O(|V|+|E|)	O(1)~O(|E|)	O(1)~O(|E|)
邻接多重表	|E|	O(|V|+|E|)

其中出度为某节点指向其他节点，入度为某节点被其他节点指向。

• 总结一下：

	数据结构	特点
图的存储	邻接矩阵	顺序存储（数组）
	邻接表	顺序存储+链式存储（数组+链表）
	十字链表	适用于有向图
	邻接多重表	适用于无向图

参考文献：

邻接表_百度百科

看动画，彻底理解数据结构中图的知识，图的邻接表和邻接矩阵_哔哩哔哩_bilibili

50-图-1.图的逻辑结构和邻接矩阵存储法_哔哩哔哩_bilibili

图的存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）_哔哩哔哩_bilibili

严蔚敏 - 数据结构（c语言版 第2版）-人民邮电出版社 (2015)