数据结构系列内容的学习目录
→
\rightarrow
→浙大版数据结构学习系列内容汇总。
1. 什么是图1.1 图的概述1.2 抽象数据类型定义1.3 常见术语1.4 怎么在程序中表示一个图1.4.1 邻接矩阵1.4.2 邻接表
1.5 图的建立1.5.1 使用邻接矩阵表示图1.5.2 使用邻接表表示图
1. 什么是图
1.1 图的概述
图（Graph）：
∙
\bullet
∙ 表示“多对多”的关系
∙
\bullet
∙ 包含
⋄
\diamond
⋄ 一组顶点：通常用 V（Vertex）表示顶点集合
⋄
\diamond
⋄ 一组边：通常用 E（Edge）表示边的集合
⋅
\cdot
⋅ 边是顶点对：（v, w）
∈
∈
∈ E，其中 v,w
∈
∈
∈ V
⋅
\cdot
⋅ 有向边
⋅
\cdot
⋅ 不考虑重边和自回路
1.2 抽象数据类型定义
类型名称： 图（Graph） 数据对象集： G(V，E)由一个非空的有限顶点集合 V 和一个有限边集合 E 组成 操作集： 对于任意图 G
∈
∈
∈ Graph，以及 v
∈
∈
∈ V，e
∈
∈
∈ E，主要操作有：
Graph Crate()：建立并返回空图；Graph InsertVertex(Graph G,Vertex v)：将v插入G；Graph InsertEdge(Graph G,Edge e)：将e插入G；void DFS(Graph G,Vertex v)：从顶点v出发深度优先遍历图G；void BFS(Graph G,Vertex v)：从顶点v出发宽度优先遍历图G；void shortestPath (Graph G, vertex v, int Dist[])：计算图G中顶点v到任意其他顶点的最短距离；void MST (Graph G)：计算图G的最小生成树。
1.3 常见术语
无向图：图中所有的边无所谓方向。有向图： 图中的边可能是双向，也可能是单向的，方向是很重要的。权值： 给图中每条边赋予的值，可能有各种各样的现实意义。网络： 带权值的图。邻接点： 有边直接相连的顶点。出度： 从某顶点发出的边数。入度： 指向某顶点的边数。稀疏图： 顶点很多而边很少的图。稠密图： 顶点多边也多的图。完全图： 对于给定的一组顶点，顶点间都存在边。
1.4 怎么在程序中表示一个图
1.4.1 邻接矩阵
邻接矩阵：
G
[
N
]
[
N
]
G[N][N]
G[N][N]——N个顶点从0到N-1编号
G
[
i
]
[
j
]
=
{
1
若
<
v
i
,
v
j
>
是
G
中
的
边
0
否
则
G[i][j]=\left\{\begin{matrix} 1 \ _{}\ _{}若
G[i][j]={1 若
问题： 对于无向图的存储，怎样可以省一半空间? 方法： 用一个长度为N(N+1)/2的1维数组A存储
{
G
00
,
G
10
,
G
11
,
.
.
.
.
.
.
,
G
n
−
1
0
,
.
.
.
.
.
.
,
G
n
−
1
n
−
1
}
\{G_{00},G_{10},G_{11},......,G_{n-1 \ _{}0} ,......,G_{n-1\ _{} n-1}\}
{G00,G10,G11,......,Gn−1 0,......,Gn−1 n−1}，则
G
i
j
G_{ij}
Gij在A中对应的下标是
(
i
∗
(
i
+
1
)
/
2
+
j
)
(i*(i+1)/2 +j)
(i∗(i+1)/2+j)。
对于网络，只要把
G
[
i
]
[
j
]
G[i][j]
G[i][j]的值定义为边
<
v
i
,
v
j
>
v
i
v_{i}
vi和
v
j
v_{j}
vj之间若没有边该怎么表示?
优点： 1. 直观、简单、好理解； 2. 方便检查任意一对顶点间是否存在边； 3. 方便找任一顶点的所有“邻接点”（有边直接相连的顶点) 4. 方便计算任一顶点的“度”(从该点发出的边数为“出度”，指向该点的边数为“入度”) ● 无向图：对应行（或列）非0元素的个数 ● 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”。
缺点： 1. 浪费空间：存稀疏图（点很多而边很少)有大量无效元素； ● 对稠密图（特别是完全图)还是很合算的 2. 浪费时间：统计稀疏图中一共有多少条边。
1.4.2 邻接表
邻接表： G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。
下图左边所示的图的邻接表如右边所示。
对于网络，结构中要增加权重的域。
特点： 1. 方便找任一顶点的所有“邻接点”； 2. 节约稀疏图的空间； ● 需要N个头指针＋2E个结点（每个结点至少2个域) 3. 方便计算任一顶点的“度”? ● 对无向图：是的 ● 对有向图：只能计算“出度”，需要构造“逆邻接表”（存指向自己的边)来方便计算“入度” 4. 方便检查任意一对顶点间是否存在边? No
1.5 图的建立
对于图1所示的图，分别用邻接矩阵和邻接表表示法建立图。
图1
1.5.1 使用邻接矩阵表示图
使用邻接矩阵表示法建立图的代码实现如下所示。
#include
using namespace std;
/* 图的邻接矩阵表示法 */
#define MaxVertexNum 100 // 最大顶点数设为100
typedef int Vertex; // 用顶点下标表示顶点,为整型
typedef int WeightType; // 边的权值设为整型
typedef char DataType; // 顶点存储的数据类型设为字符型
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // 有向边
WeightType Weight; // 权重
};
typedef PtrToENode Edge;
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // 顶点数
int Ne; // 边数
WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
DataType Data[MaxVertexNum]; // 存顶点的数据
/* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现 */
};
typedef PtrToGNode MGraph; // 以邻接矩阵存储的图类型
// 初始化图
MGraph CreateGraph(int VertexNum)
{
Vertex V, W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); // 建立图
Graph->Nv = VertexNum;
Graph->Ne = 0;
/* 初始化邻接矩阵 */
/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
for (V = 0; V < VertexNum; V++)
for (W = 0; W < VertexNum; W++)
Graph->G[V][W] = 0;
return Graph;
}
// 插入边
void InsertEdge(MGraph Graph, Edge E)
{
// 插入边
Graph->G[E->V1][E->V2] = E->Weight;
// 如果是无向图，还需要插入边
Graph->G[E->V2][E->V1] = E->Weight;
}
// 建图
MGraph BuildGraph()
{
MGraph Graph;
Edge E;
Vertex V;
int Nv, i;
cin >> Nv; // 读入顶点数
Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图
cin >>(Graph->Ne); // 读入边数
if (Graph->Ne != 0) // 如果有边
{
E = (Edge)malloc(sizeof(struct ENode)); // 建立边结点
for (i = 0; i < Graph->Ne; i++)
{
cin >> E->V1 >> E->V2 >> E->Weight;// 读入边，格式为"起点 终点 权重"，插入邻接矩阵
InsertEdge(Graph, E);
}
}
// 如果顶点有数据的话，读入数据
for (V = 0; V < Graph->Nv; V++)
cin >> (Graph->Data[V]);
return Graph;
}
// 遍历图
void Print(MGraph Graph)
{
Vertex V, W;
for (V = 0; V < Graph->Nv; V++)
{
for (W = 0; W < Graph->Nv; W++)
cout << Graph->G[V][W];
cout << endl;
}
}
int main()
{
MGraph Graph;
Graph = BuildGraph();
Print(Graph);
system("pause");
return 0;
}
对于图1所示的图，使用邻接矩阵表示法建立图的测试效果如下图所示。
1.5.2 使用邻接表表示图
使用邻接表表示法建立图的代码实现如下所示。
#include
using namespace std;
/* 图的邻接表表示法 */
#define MaxVertexNum 100 // 最大顶点数设为100
typedef int Vertex; // 用顶点下标表示顶点,为整型
typedef int WeightType; // 边的权值设为整型
typedef char DataType; // 顶点存储的数据类型设为字符型
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // 有向边
WeightType Weight; // 权重
};
typedef PtrToENode Edge;
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
Vertex AdjV; // 邻接点下标
WeightType Weight; // 边权重
PtrToAdjVNode Next; // 指向下一个邻接点的指针
};
/* 顶点表头结点的定义 */
typedef struct Vnode {
PtrToAdjVNode FirstEdge; // 边表头指针
DataType Data; // 存顶点的数据
/* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum]; // AdjList是邻接表类型
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // 顶点数
int Ne; // 边数
AdjList G; // 邻接表
};
typedef PtrToGNode LGraph; // 以邻接表方式存储的图类型
LGraph CreateGraph(int VertexNum) // 初始化一个有VertexNum个顶点但没有边的图
{
Vertex V;
LGraph Graph;
Graph = (LGraph)malloc(sizeof(struct GNode)); // 建立图
Graph->Nv = VertexNum; // 初始化边
Graph->Ne = 0; // 初始化点
/* 初始化邻接表头指针 */
/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
for (V = 0; V < Graph->Nv; V++)
Graph->G[V].FirstEdge = NULL;
return Graph;
}
void InsertEdge(LGraph Graph, Edge E) // 插入一条边到邻接表的顶点指针之后
{
PtrToAdjVNode NewNode;
/* 插入边
// 为V2建立新的邻接点
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->AdjV = E->V2;
NewNode->Weight = E->Weight;
// 将V2插入V1的表头
NewNode->Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
/* 若是无向图，还要插入边
// 为V1建立新的邻接点
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->AdjV = E->V1;
NewNode->Weight = E->Weight;
// 将V1插入V2的表头
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}
// 建图
LGraph BuildGraph()
{
LGraph Graph;
Edge E;
Vertex V;
int Nv, i;
cin >> Nv; // 读入顶点个数
Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图
cin >> (Graph->Ne); // 读入边数
if (Graph->Ne != 0) // 如果有边
{
E = (Edge)malloc(sizeof(struct ENode)); // 建立边结点
for (i = 0; i < Graph->Ne; i++) {
cin >> E->V1 >> E->V2 >> E->Weight; // 读入边，格式为"起点 终点 权重"，插入邻接矩阵
InsertEdge(Graph, E);
}
}
// 如果顶点有数据的话，读入数据
for (V = 0; V < Graph->Nv; V++)
cin >> (Graph->G[V].Data);
return Graph;
}
// 打印
void Print(LGraph Graph)
{
Vertex v;
PtrToAdjVNode temp;
for (v = 0; v < Graph->Nv; v++)
{
temp = Graph->G[v].FirstEdge;
cout << v << " ";
while (temp)
{
cout << temp->AdjV << " ";
temp = temp->Next;
}
cout << endl;
}
}
int main()
{
LGraph Graph;
Graph = BuildGraph();
Print(Graph);
system("pause");
return 0;
}
对于图1所示的图，使用邻接表表示法建立图的测试效果如下图所示。