图的存储结构

下面简要介绍一些图的存储的基本知识：

1.邻接矩阵

　　邻接矩阵是表示图的数据结构中的最简单的一种，这个矩阵的第i行第j列的数值即表示节点i和节点j的距离。这种存储方式简单直观、方便查询，但是复杂度较高，而且不能存储具有重边的图。

2.前向星

　　前向星是一种通过存储边信息的方式存储图的数据结构。它的构造方式非常简单，读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完成了。为了查询方便，经常会有一个数组存储起点为v_{i ^{的第一条边的位置。}}

　　代码如下：

 1 //所需数据结构如下：
 2 //maxn 节点数；maxm 边数
 3 
 4 int head[maxn];//存储起点为Vi的第一条边的位置
 5 struct Node
 6 {
 7     int from,to,w;//起点，终点，权值
 8 }；
 9 Node edge[maxm];
10 
11 //排序
12 
13 bool cmp(Node a,Node b)
14 {
15     if(a.from==b.from&&a.to==b.to)return a.w<b.w;
16     else if(a.from==b.from)return a.to<b.to;
17     else return a.from<b.from;
18 }
19 
20 //读入数据
21 
22 cin>>n>>m;
23 for(int i=0;i<m;i++)cin>>edge[i].from>>edge[i].to>>edge[i].w;
24 sort(edge,edge+m,cmp);
25 memset(head,-1,sizeof(head));
26 head[edge[0].from]=0;
27 for(int i=1;i<m;i++)
28 if(edge[i].from!=edge[i-1].from)head[edge[i].from]=i;
29 
30 //图的遍历
31 
32 for(int i=1;i<=n;i++)
33 {
34     for(int k=head[i];edge[k].from==i&&k<m;k++)
35     {
36         ……//这里可以读出每条边的信息
37     }
38 }

View Code

　　时间复杂度：O（mlog m).优点在于可以处理点非常多的情况，可以存储重边，但是不能判断任意两个点之间是否有边。

3.邻接表

　　邻接表是图的一种链式存储结构。对于图G中的每个顶点，把所有邻接于该点的顶点链接成一个单链表，这个单链表就称为该顶点的邻接表。

　　邻接表有三种实现办法，分别为动态建表、使用STL中的vector建表和静态建表。

　　3.1动态建表

　　邻接表中每个节点有三个属性：其一为邻接点序号to，用以存放与顶点 v_i相邻接的顶点的序号；其二为边上的权值w；其三为指针next。另外为每个顶点Vi的邻接表设置一个具有两个属性的表头节点：一个是顶点序号from；另一个是指向其邻接表的指针first。

　　代码如下：

 1 struct EdgeNode //邻接表节点
 2 {
 3     int to,w;
 4     EdgeNode * next;
 5 };
 6 
 7 struct VNode   //起点表节点
 8 {
 9     int from;
10     EdgeNode *first;
11 };
12 
13 VNode Adjlist[maxn]; //邻接表
14 
15 //读入数据
16 
17 cin>>i>>j>>w;
18 EdgeNode * p=new EdgeNode();
19 p->to=j;
20 p->w=w;
21 p->next=Adjlist[i].first;
22 Adjlist[i].first=p;
23 
24 //图的遍历
25 
26 for(int i=1;i<=n;i++)
27 {
28     for(EdgeNode * k=Adjlist[i].first;k!=NULL;k=k->next)
29     {
30         ……//输出起点为i的边的所有信息
31     }
32 }

View Code

　　时间复杂度O（m）,动态建表每次随机申请内存消耗的时间较多，内存的释放需要处理。对于无向图的处理，需要把边拆成两条有向边。

　　3.2STL中的vector模拟链表实现

　　代码如下：

 1 struct Node
 2 {
 3     int to,w;
 4 };
 5 vector <Node> map[maxn];
 6 
 7 Node e;
 8 cin>>i>>j>>w;
 9 e.to=j;
10 e.w=w;
11 map[i].push_back(e);
12 
13 for(int i=1;i<=n;i++)
14 {
15     for(vector< Node >::iterator k=map[i].begin();k!=map[i].end();k++)
16     {
17         Node t=*k;
18         cout<<i<<" "<<t.to<<" "<<t.w<<endl;
19     }
20 }

View Code

　　内存的申请与释放都不需要处理。

　　3.3静态建表（链式前向星）

　　链式前向星采用数组模拟链表的方式实现邻接表的功能，并且使用很少的额外空间，可以说是目前建图和遍历效率最高的存储方式。

　　数组模拟链表的主要方式是记录下一个节点在数组中的哪个位置。head数组存储描述点Vi边信息的链的起点在Edges数组的位置。构造链式前向星就是将新加入的节点链在对应链的最开始并修改head数组的对应位置的值。

代码如下：

 1 int head[n];
 2 struct EdgeNode
 3 {
 4     int to,w,next;
 5 };
 6 EdgeNode Edges[m];
 7 
 8 //边存储，其中k表示当前输入第k条边
 9 cin>>i>>j>>w;
10 Edges[k].to=j;
11 Edges[k].w=w;
12 Edges[k].next=head[i];
13 head[i]=k;
14 
15 //遍历
16 for(int i=1;i<=n;i++)
17 {
18     for(int k=head[i];k!=-1;k=Edges[k].next)
19     {
20         ……//输出起点为i的所有边的信息
21     }
22 }

View Code

　　链式前向星除了不能直接确定边的存在与否外几乎是完美的。使用较多。

参考文献：《图论及应用》哈尔滨工业大学出版社。

特此声明：严禁转载

2014-02-16