【数据结构】图2——图的存储结构_有向图的邻接矩阵

---

图的逻辑结构：多对多

图的存储结构介绍

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系：
数组表示法——邻接矩阵
多重链表——邻接表、邻接多重表、十字链表

邻接矩阵（数组）

邻接矩阵表示法

1、无向图的邻接矩阵

建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间关系)。

分析：
① 无向图的邻接矩阵是对称的；
② 顶点i的度=第i行(列)中1的个数；
特别：完全图的邻接矩阵中，对角元素为0，其余为1。

2、有向图的邻接矩阵

在有向图的邻接矩阵中，
第i行含义：以结点Vi为尾的弧(即出度边)；
第i冽含义：以结点Vi为头的弧(即入度边)。

分析：
① 有向图的邻接矩阵可能是不对称的。
② 顶点的出度=第i行元素之和
顶点的入度=第i列元素之和
顶点的度=第i行元素之和+第i列元素之和

3、网（即有权图）的邻接矩阵

邻接矩阵的建立

1、邻接矩阵的存储表示

用两个数组分别存储顶点表和邻接矩阵

#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;//Adjacency Matrix Graph
1
2
3
4
5
6
7
8
9
10

2、采用邻接矩阵表示法创建无向网

【算法思想】
① 输入总顶点数和总边数。
② 依次输入点的信息存入顶点表中。
③ 初始化邻接矩阵，使每个权值初始化为极大值。
④ 构造邻接矩阵。

int LocateVex(AMGraph G,VertexType u){//图中查找顶点算法
//在图G中查找顶点u，存在则返回顶点表中的下标；否则返回-1
	int i;
	for(i=0;i<G.vexnum;++i)
		if(u==G.vexs[i];
		return i;
	return -1;
}

Status CreateUDN(AMGraph &G){//采用邻接矩阵表示法，创建无向图G
	cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
	for(i=0;i<G.vexnum;++i)
		cin>>G.vexs[i];//依次输入点的信息
	for(i=0;i<G.vexnum;++i)//初始化邻接矩阵
		for(j=0;j<G.vexnum;++j)
			G.arcs[i][j]=MaxInt;//边的权值均置为极大值
	for(k=0;k<G.arcnum;++k)//构造邻接矩阵
		cin>>v1>>v2>>w;//输入一条边所依附的顶点及边的权值
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);//确定v1和v2在G中的位置
		G.arcs[i][j]=w;//边<v1,v2>的权值置为w
		G.arcs[j][i]=G.arcs[i][j];//置为<v1,v2>的对称边<v2,v1>的权值为w
	return OK;
}//CreateUDN

空间复杂度：O(n*n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3、采用邻接矩阵表示法创建有向网

在创建无向网的基础上修改：
邻接矩阵是非对称矩阵，仅为G.arcs[i][j]赋值，无需为G.arcs[j][i]赋值。

4、采用邻接矩阵表示法创建有无向图

在创建无向网的基础上修改：
① 初始化邻接矩阵时，w均为0；
② 构造邻接矩阵时，w为1。

5、采用邻接矩阵表示法创建有有向图

在创建无向网的基础上修改：
① 初始化邻接矩阵时，w均为0；
② 构造邻接矩阵时，w为1。
③ 邻接矩阵是非对称矩阵，仅为G.arcs[i][j]赋值，无需为G.arcs[j][i]赋值。

邻接矩阵的优缺点

1、优点
① 直观、简单、好理解。
② 方便检查任意一对顶点间是否存在边。
③ 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
③ 方便计算任一顶点的"度” (从该点发出的边数为“出度”，指向该点的边数为“入度" )
无向图：对应行(或列)非0元素的个数；
有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是"入度”。

2、缺点
① 不便于增加和删除顶点。
② 浪费空间：
稀疏图(点很多而边很少)有大量无效元素；
稠密图(特别是完全图)还是很合算的。
③ 浪费时间：计稀疏图中一共有多少条边。

邻接表（链式）

邻接表表示法

1、无向图

顶点：按编号顺序将顶点数据存储在一维数组中；
关联同一顶点的边(以顶点为尾的弧)：用线性链表存储。
data：存放顶点数据元素信息。
firstarc：指向第一条边或弧的地址。
adjvex：邻接点域，存放与Vi，邻接的顶点在表头数组中的位置。
nextarc：链域（指针域），指示下一条边或弧。|
info：存放权值信息。

特点：
① 边的顺序不确定，所以邻接表不唯一。
② 若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。
③ 无向图中顶点Vi的度为第i个单链表中的结点数。

2、有向图

邻接表找出度容易，找入度难。
特点：
① 顶点Vi的出度为第i个单链表中的结点个数。
② 顶点Vi的入度为整个单链表中邻接点域值是i-1的结点个数。

逆邻接表找入度容易，找出度难。
特点：
① 顶点Vi的入度为第i个单链表中的结点个数。
② 顶点Vi的出度为整个单链表中邻接点域值是i-1的结点个数。

当邻接表的存储结构形成后，图便唯一确定！

邻接表的建立

1、图的邻接表存储表示

顶点的结点结构：

typedef struct VNode{
	VerTexType data;//顶点信息
	ArcNode *first;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];//AdjList表示邻接表类型
1
2
3
4

弧（边）的结点结构：

#define MVNum 100//最大顶点数
typedef struct ArcNode{//边结点
	int adjvex;//该边所指向的顶点的位置
	struct ArcNode *nextarc;//指向下一条边的指针
	OtherInfo info;//和边相关的信息
}ArcNode;
1
2
3
4
5
6

图的结构定义：

typedef struct{
	AdjList vertices;//vertice是vertex的复数
	int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
1
2
3
4

例：

2、采用邻接表表示法创建无向网

【算法思想】
① 输入总顶点数和总边数。
② 建立顶点表：
依次输入点的信息存入顶点表中；
使每个表头结点的指针域初始化为NULL。
③ 创建邻接表：
依次输入每条边依附的两个顶点；
确定两个顶点的序号i和j，建立边结点；
将此边结点分别插入到Vi和Vj对应的两个边链表的头部（头插法）。

Status CreateUDG(ALGraph &G){//采用邻接表表示法，创建无向图G
	cin>>G,vexnum>>G.arcnum;//输入总顶点数，总边数
	for(i=0;i<G.vexnum;++i)//输入各点，构造表头结点表
		cin>>G.vertices[i].daya;//输入顶点值
		G.vertices[i].firstarc=NULL;//初始化表头结点的指针域
	for(k=0;k<G.arcnum;++k)//输入各边，构造邻接表
		cin>>v1>>v2;//输入一条边依附的两个顶点
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		
//如果建立的是有向网的逆邻接表，则删掉下面这四行
		p1=new ArcNode;//生产一个新的边结点*p1
		p1->adjvex=j;//邻接点序号为j
		p1->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p1;//将新结点*p1插入顶点vi的边表头部
		
//如果建立的是有向网的邻接表，则删掉下面这四行
		p2=new ArcNode;//生成另一个对称的新的边结点*p2
		p2->adjvex=i;//邻接点序号为i
		p2->nextarc=G.vertices[j].firstarc;
		G.vertices[j].firstarc=p2;//将新结点*p2插入顶点vj的边表头部
	return OK;
}//CreateUDG
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

邻接表的特点

① 方便找任一顶点的所有“邻接点"；
② 节约稀疏图的空间：
需要N个头指针+2E个结点(每个结点至少2个域)；
③ 方便计算任一顶点的"度”：
对无向图：方便计算任一顶点的"度”，每条边都要存储两遍；
对有向图：求结点的度困难，只能计算"出度”；需要构造“逆邻接表”(存指向自己的边) 来方便计算“入度”。
④ 不方便检查任意一对顶点间是否存在边。

邻接矩阵与邻接表表示法的关系

1、联系：
邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

2、区别：
① 对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关) 。
②邻接矩阵的空间复杂度为O(n*n)，而邻接表的空间复杂度为O(n+e)，n表示n个顶点，e表示e条边。

3、用途：
邻接矩阵多用于稠密图；
而邻接表多用于稀疏图。

十字链表

解决邻接表存储有向图求结点的度困难的问题。

十字链表(Orthogonal List)是有向图的另一种链式存储结构。

我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

邻接多重表

解决邻接表存储无向图中存储边两遍的问题。

---