数据结构——图（二、图的存储和基本操作）

一、邻接矩阵

1、邻接矩阵定义

一个一维数组存储图中顶点的信息，一个二维数组存储图中边的信息（各顶点之间的邻接关系）。

邻接矩阵可用来存储无向图、有向图

若图中有n个顶点，则邻接矩阵A是nn

邻接矩阵采用顺序存储结构

空间复杂度为O(|V|²)

与边数无关

存储顶点信息使用O(|V|)，存储边信息使用O(|V|²)

更多用于稠密图

1）无向图的邻接矩阵

注：对称矩阵且唯一，对称矩阵在实际存储时只需要存储上（下）三角矩阵中的元素

如右表黄色区域，有向图的邻接矩阵。 G[i][j]=0，两顶点间不存在边 G[i][j]=1，两顶点间存在边			0	1	2	3	4
			A	B	C	D	E
	0	A	0	1	1	1	0
	1	B	1	0	0	0	1
	2	C	1	0	0	1	0
	3	D	1	0	1	0	0
	4	E	0	1	0	0	0

对于无向矩阵

度遍历行或列

顶点A的度 = 邻接矩阵第0行（或第0列）的非零元素（或非∞元素）的个数之和

时间复杂度为O(|V|)

2）有向图的邻接矩阵

注：唯一，但是由于两个点之间的边是双向的，因此并不对称

如右表黄色区域，有向图的邻接矩阵。 G[i][j]=0，顶点i到顶点j不存在弧 G[i][j]=1，顶点i到顶点j存在弧			0	1	2	3	4
			A	B	C	D	E
	0	A	0	1	1	1	0
	1	B	1	0	0	0	0
	2	C	0	0	0	1	0
	3	D	0	0	0	0	0
	4	E	0	1	0	0	0

对于有向矩阵

出度遍历行，入度遍历列

顶点A的度 = 出度+入度 = 邻接矩阵第0行的非零元素（或非∞元素）的个数 + 邻接矩阵第0列的非零元素   （或非∞元素）的个数 = 3+1 = 4

时间复杂度为O(|V|)+O(|V|)

3）带权图的邻接矩阵

无穷∞表示两个顶点之间不存在边（也可以使用0表示）

2、邻接矩阵性质

用邻接矩阵存储图

1、很容易确定图中任意两个顶点之间是否有边相连

比如无向图中，判断A与D之间是否相连，检查G[0][3]==1或G[3][0]==1

2、若要确定图中有多少条边，必须按行、按列对每个元素进行遍历，时间复杂度为O(|V|²)

3、若要确定顶点的度，必须按行、按列对每个元素进行遍历，时间复杂度为O(|V|)

3、邻接矩阵存储结构（算法实现）

#define INFININITY //最大int值，即无穷
#define MAXVertexNum 100	//最大顶点数
 
typedef char VerTexType;	//顶点对应的数据类型 
typedef int ArcType;	//边对应的数据类型 

typedef struct{
	VerTexType vexs[MAXVertexNum];	//顶点表
	ArcType arcs[MAXVertexNum][MAXVertexNum];	//邻接矩阵,边表
	int vexnum,arcnum;	//图的当前点数和边数
}MGraph;

1、在简单应用中，可以直接使用二维数组作为图的邻接矩阵（顶点信息可忽略）

2、当邻接矩阵的元素仅表示相应边是否存在时，EdgeType可用值为0或1的布尔类型

邻接矩阵具体算法操作查看

图——邻接矩阵基本操作算法实现-CSDN博客

4、邻接矩阵的相关计算

[1][1] = 顶点B到顶点B的长度为2的路径的数目

=第2行*第2列

=

=2

[0][3] = 顶点A到顶点D的长度为2的路径的数目

=第1行*第4列

=

=1

二、邻接表

1、邻接表定义

对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点i的边（对于有向图则是以顶点i为尾的弧），称为边表（对于有向图则是出边表）

边表的头指针和顶点的数据信息采用顺序存储，即顶点表

结合顺序存储和链式存储

若G为无向图，则所需存储空间为O(|V|)+O(2|E|)，因为每条边在邻接表出现两次

若G为有向图，则所需存储空间为O(|V|)+O(|E|)

2、邻接表的存储结构（算法实现）

#define MAXVertexNum 100	//最大顶点数

typedef struct ArcNode{    //边表结点 
 	int adjvex;  //该边所指向的顶点的位置 
 	struct ArcNode *nextarc;//指向下一条边的指针 
 	Otherinfo info;  //网的边权值 
}ArcNode;

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

typedef struct{    
 	AdjList vertices;    //邻接表
 	int vexnum,arcnum;    //图的当前顶点数和弧数
}ALGraph;

关于邻接表更多具体基础操作算法查看附件

图——邻接表基本操作算法实现-CSDN博客

3、邻接表性质

1、对于稀疏表（边数较少的表），采用邻接表将极大节省空间

2、图的邻接表不唯一，在每个顶点对应的边表中，各边结点的链接次序可以是任意的，取决于建立邻接表的算法及边的输入次序。

1、给定一个顶点，极其容易找出它的所有邻边（对于有向图，则是出边）

遍历该顶点的单链表，最差时间复杂度为O(|V|)

2、对于有向图，找一个顶点A的入边，需要遍历所有顶点（除该顶点A外）的边表，找到结点A，时间复杂度为O(|E|)

3、若要确定两个顶点间是否存在边，找到相应结点对应的边表中查找另一个结点

对于有向图，如果出边未找到，还需要遍历所有顶点（除自身）的边表，找到自身结点。

4、在有向图的邻接表中，求某个顶点的出度只需要计算其邻接表中的边表个数，但求某个顶点x的入度则需要遍历全部邻接表，统计邻接点域为x的边表结点个数。

三、十字链表

是有向图的一种链式存储结构

有向图的每条弧用一个结点（弧节点）表示，每个顶点用一个（顶点结点）表示

解决入边难寻的问题，同时节省存储空间，空间复杂度为O(|V|+|E|)

顶点结点之间是顺序存储，弧结点省略了info域

图的十字链表不是唯一的，但是一个十字链表表示唯一确定的一个图

在十字链表中，既容易找到以V为尾的弧，也容易找到以V为头的弧，因而容易求得顶点的出度和入度

四、邻接多重表

邻接多重表是无向图的一种链式存储

解决邻接表中求两个顶点之间是否存在边而执行删除边等操作时，需要分别遍历两个顶点的边表的问题。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中

因为每条边依附于两个顶点，所以每个边结点同时链接在两个链表中

邻接多重表和邻接表的区别

同一条便在邻接表中用两个结点表示，在邻接多重表中只有一个结点

五、图的基本操作

Adjacent(G,x,y) 判断图是否存在边<x,y>或(x,y)

Neighbors(G,x) 列出图中与结点x邻接的边

InsertVertex(G,x) 在图中插入顶点x

DeleteVertex(G,x) 在图中删除顶点x

AddEdge(G,x,y) 若无向边（x,y)或有向边<x,y>不存在，则向图G中添加该边

RemoveEdge(G,x,y) 若无向边（x,y)或有向边<x,y>存在，则从图G中删除该边

FirstNeighbor(G,x) 求图中顶点x的第一个邻接点，若有则返回定点好，若x没有邻接点或图中不存在x，则返回-1

NextNeighbor(G,x) 假设图中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

Get_edge_value(G,x,y) 获取图中边（x,y) 或 <x,y>对应的权值

Set_edge_value(G,x,y,v) 设置图中边（x,y) 或 <x,y>对应的权值为v

图的遍历算法见附件

数据结构——图（三、图的 广度/深度 优先搜索）-CSDN博客

六、图的四种存储方式总结对比