第六章 图（上）【图的基本概念和存储】

1. 图的基本概念

 1.1 图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系 (边) 集合。若V={V, V2,...,Vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u, v) l uV, vV}，用|E|表示图G中边的条数。

 注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

1.2 相关概念 

• 无向图：若E是无向边 （简称边) 的有限集合时，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)，因为（v,w)=(w,v)，其中v、w是顶点。可以说顶点w和顶点v互为邻援点。边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v、w相关联。
•  有向图：若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为，其中v、w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。 。
• 简单图：① 不存在重复边； ② 不存在顶点到自身的边。
• 多重图：图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联,则G为多重图。
• 顶点的度 、入度、出度

       ① 对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)

在具有n个顶点、e条边的无向图中，

即：无向图的全部顶点的度的和等于边数的2倍
       ② 对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v);出度是以顶点v为起点的有向边的数目，记为OD(v)，顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

在具有n个顶点、e条边的有向图中，

即：有向图的全部顶点的入度的和与出度的和都等于边数，全部顶点的度的和等于边数的2倍。

其他的概念

• 连通图：若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
• 强连通图：若图中任何一对顶点都是强连通的，则称此图为强连通图。
• 子图：设有两个图G = (V, E)和G’ = (V‘, E’)，若V‘是V的子集，且E’是E的子集，则称G‘是G的子图。
• 
• 连通分量：无向图的极大连通子图称为连通分量。要求：子图必须连通，且包含
  尽可能多的顶点和边

• 强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。要求：子图必须强连通，同时保留尽可能多的边。

• 极小连通子图：边尽可能的少， 但要保持连通
• 连通图的生成树（不唯一）：连通图的生成树是包含图中全部顶点的一个极小连通子图。要求：若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

• 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林

• 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
• 带权图/网：边上带有权值的图称为带权图，也称网。
• 带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
• 无向完全图——无向图中任意两个顶点 之间都存在边，共条边
• 有向完全图——有向图中任意两个顶点 之间都存在方向相反的两条弧,共n(n-1)条
• 稀疏图：边数很少的图称为稀疏图，反之称为稠密图，没有绝对的界限，

 特殊形态的树：

树——不存在回路，且连通的无向图

有向树——一个顶点的入度为0、其余顶点的 入度均为1的有向图，称为有向树。

n个顶点的树，必有n-1条边。

2. 图的存储

2.1 邻接矩阵法

2.1.1 图的邻接矩阵定义

• 图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
• 只要确定了顶 点编号，图的 邻接矩阵表示 方式唯一

无向图的度：第i个结点的度 = 第i行（或第j列）的非零元素个数；
有向图的出度：第i行的非零元素个数；
有向图的入度：第 i列的非零元素个数。

有向图的度:第i行的非零元素个数+  第 i列的非零元素个数。

2.1.2 邻接矩阵法代码实现

#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY INT_MAX    // 定义无穷值
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;	//带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum];	//顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表
	int vexnum, arcnum;	//图的当前顶点数和弧树
}MGraph;

 2.1.3 性能分析：

数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
（1）空间复杂度：，只和顶点数相关，和实际的边数无关。，邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)
（2）适合用于存储稠密图。
（3）无向图的邻接矩阵是对称矩阵，可以压缩存储 (只存储上三角区或者下三角区)。

 邻接矩阵法的性质

设图G的邻接矩阵为A（矩阵元素为0/1），则An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目

A^2[1][4],顶点1, 4为点A和D,则由顶点A到顶点D的长度为2的路径只有1条

2.2 邻接表法 顺序+链式存储

2.2.1 性能分析：

 无向图：边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)

 有向图：边结点的数量是|E|， 整体空间复杂度为 O(|V| + |E|)

2.2.2 特点 

• 更适合用于稀疏图；
• 若G为无向图，则顶点的度为该顶点边表的长度若G为有向图，则顶点的出度为该顶点边表的长度，计算入度需要遍历整个邻接表；
• 邻接表不唯一，边表结点的顺序根据算法和输入不同可能会不同。

2.2.3 代码实现

#define MAXVEX 100	//图中顶点数目的最大值
type char VertexType;	//顶点类型应由用户定义
typedef int EdgeType;	//边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{
	int adjvex;	//该弧所指向的顶点的下标或者位置
	EdgeType weight;	//权值，对于非网图可以不需要
	struct EdgeNode *next;	//指向下一个邻接点
}EdgeNode;
 
/*顶点表结点*/
typedef struct VertexNode{
	Vertex data;	//顶点域，存储顶点信息
	EdgeNode *firstedge	//边表头指针
}VertexNode, AdjList[MAXVEX];
 
/*邻接表*/
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//图中当前顶点数和边数
}

2.3 十字链表

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

2.3.1 问题引入 与解决

2.3.2 十字链表法性能分析

空间复杂度：O(|V|+|E|)

邻接表找顶点的入 边不方便，邻接矩阵空间复杂度 高 O(|V|2)

• 如何找到指定顶点的所有出边？——顺着绿色线路找
• 如何找到指定顶点的所有入边？——顺着橙色线路找

注意：十字链表只用于存储有向图

2.3.3 代码实现

#define MAX_VERTEX_NUM 20	//最大顶点数量
 
struct EBox{				//边结点
	int i,j; 				//该边依附的两个顶点的位置（一维数组下标）
	EBox *ilink,*jlink; 	//分别指向依附这两个顶点的下一条边
	InfoType info; 			//边的权值
};
struct VexBox{
	VertexType data;
	EBox *firstedge; 		//指向第一条依附该顶点的边
};
struct AMLGraph{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum,edgenum; 	//无向图的当前顶点数和边数
};

2.4 邻接多重表存储无向图

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

2.4.1 问题引入 与解决

邻接矩阵存储无向图、空间复杂度高 O(|V|2)，邻接表存储无向图每条边对应两份冗余信息， 删除顶点、删除边等操作 时间复杂度高

2.4.2 性能分析：

空间复杂度：O(|V|+|E|)

优点：删除边、删除节点等操 作很方便

注意：邻接多重表只适 用于存储无向图

2.4.3 四种存储方法比较：