数据结构——图

图

  • 定义：Graph=(V,E)
    – V：顶点(数据元素)的有穷非空集合
    – E：边的有穷集合

图的名词和术语

  • 顶点：图中的数据元素。
  • 边：若<v, w>E 必有<w, v>E, 则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边。
  • 弧：若<v, w>E 是有方向的,则称 <v, w>为顶点 v 和顶点 w 之间存在一条有向边，也称为弧。
  • 无向图：由顶点集和边集构成的图。每条边都是无方向的
  • 有向图：由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。、
  • 完全图
    – 顶点：n，边：e
    – 无向完全图：含有 e=n(n-1)/2 条边的无向图
    – 有向完全图：含有 e=n(n-1) 条弧的有向图

    在这里插入图片描述
  • 稀疏图：e<nlogn
  • 稠密图：e>nlogn
  • 权：某些图的边具有与它相关的数
  • 网：边/弧带权的图

    在这里插入图片描述
  • 邻接点：假若顶点v 和顶点w 之间存在一条边，
    则称顶点v 和w 互为邻接点
  • 顶点的度：与该顶点相关联的边的数目，记为TD(v)
  • 入度：以 v 为终点的有向边的条数, 记作 ID(v)
  • 出度：以 v 为始点的有向边的条数, 记作OD(v)度(TD)=出度(OD)+入度(ID)
  • 路径：接续的边构成的顶点序列。
  • 路径长度：路径上边或弧的数目/权值之和。
  • 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。
  • 简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。
    在这里插入图片描述
  • 连通图
    – 无向图
    – 图G中任意两个顶点之间都有路径相通
    – 连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。 
	>极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。

-  有向图
	- 强连通图：任意两个顶点之间都存在一条有向路径
	- 强连通分量：极大强连通子图

在这里插入图片描述
  • 极小连通子图： 该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。（n个顶点，n-1条边）
  • 生成树：包含无向图G 所有顶点的极小连通子图。
  • 生成森林：对非连通图，由各个连通分量的生成树的集合。
    在这里插入图片描述

图的存储结构

图的邻接矩阵表示

设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgen，定义为：

在这里插入图片描述

无向图的邻接矩阵表示

在这里插入图片描述
  • 无向图的邻接矩阵是对称的, 可压缩存储（上/下）三角。
  • 顶点i 的度＝第 i 行 (列) 中1 的个数；
  • 矩阵中1的个数的一半为图中边的数目
  • 很容易判断顶点Vi 和顶点Vj之间是否有边相连(看矩阵中i行j列值是否为1)
  • 顶点不变，在图中增加（删除）边：只需对二维数组对应分量赋值1（清0）完全图的邻接矩阵中，对角元素为0，其余1。

有向图的邻接矩阵表示

在这里插入图片描述

在有向图的邻接矩阵中，

第i行含义：以结点vi为尾的弧(即出度边）；

第i列含义：以结点vi为头的弧(即入度边）。

  • 有向图的邻接矩阵可能是不对称的。
  • 顶点的出度=第i行元素之和
  • 顶点的入度=第i列元素之和
  • 顶点的度=第i行元素之和+第i列元素之和
  • 很容易判断顶点Vi 和顶点Vj 是否有弧相连
  • 顶点不变，在图中增加（删除）边：只需对二维数组对应分量赋值1（清0）

网（即有权图）的邻接矩阵表示

在这里插入图片描述

邻接矩阵的存储表示

#define INFINITY 1000  // 定义一个无穷数
#define MAX_VERTEX_NUM  // 最大顶点数

// 图类型枚举定义{有向图，有向网，无向图，无向网}
typedef enum {DG, DN, UDG, UDN} GraphKind;

typedef struct ArcCell{// 边定义
	VRType adj;  // VRType是顶点关系类型。
		// 对无权图，用1或0表示相邻否；
		// 对带权图（网络），则为权值类型。
	InfoType* info;  // 该弧相关信息指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]

typedef struct { // 图的定义
	// 顶点信息
	VertexType vexs[MAX_VERTEX_NUM];  // 顶点向量
	AdjMatrix arcs;  // 邻接矩阵
	int vexnum, arcnum;  // 顶点数量和边的数量
	GraphKind kind;  // 图的种类标志
} MGraph;

采用邻接矩阵表示法构造无向网算法

/*---------------采用邻接矩阵建立无向网络---------------*/
// 算法思路
// 1. 输入总顶点数和总边数。
// 2. 依次输入点的信息存入顶点表中。
// 3. 初始化邻接矩阵，使每个权值初始化为极大值。
// 4. 构造邻接矩阵。 
void CreateUDN(MGraph &G){
	cin >> G.vexnum >> G.arcnum;  // 输入顶点数和边数
	for(int i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.vexs[i] = new char[10];
		cin >> G.vexs[i];  // 读入顶点信息
	}
	for(int i = 0; i < G.vexnum; i++)
		// 邻接矩阵初始化
		for(j = 0; j < G.vexnum; j++){
			G.arcs[i][j].adj = INFINITY;
			G.arcs[i][j].info = NULL;
		}
	for(k = 0; k < G.arcnum; k++){
		v1 = new char[10];
		v2 = new char[10];
		cin >> v1 >> v2 >> w;  // 读入e条边上的权
		i = LocateVex_MG(G, v1);  // 查找顶点v1在图中的位置
		j = LocateVex_MG(G, v2);
		G.arcs[i][j].adj = w;
		G.arcs[j][i].adj = w;
		delete v1;
		delete v2;
	}
}

int LocateVex_MG(MGraph G, VertexType x){
	// 查找顶点x在图中的位置
	for(int k = 0; strcmp(G.vexs[k], x); k++);
	return k;
}

邻接矩阵表示法的特点

  • 优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。
  • 缺点：n个顶点需要n*n个单元存储边;空间效率为O(n^2)。 对稀疏图而言尤其浪费空间。

图的邻接表表示

  • 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；
  • 一部分是单链表，用来存放边/弧的信息
  • 另一部分是数组，主要用来存放顶点本身的数据信息
    在这里插入图片描述

无向图的邻接表

  • 同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点）。
    在这里插入图片描述

    邻接表不唯一，因各个边结点的链入顺序是任意的

  • 空间效率为O(n+2e)，若是稀疏图(e<<n^2), 比邻接矩阵表示法O(n^2)省空间
  • 所有链表中边结点数目的一半为图中边数TD(Vi)=单链表中链接的结点个数

有向图的邻接表

在这里插入图片描述
  • 空间效率: O(n+e)
  • 出度：OD(Vi)＝单链出边表中链接的结点数
  • 入度：ID(Vi)＝邻接点域为Vi的弧个数
  • 度：TD(Vi) = OD( Vi ) + I D( Vi )

图的邻接表存储表示

typedef struct ArcNode{
	// 边结点定义
	int adjvex;  // 该弧所指向的顶点的位置
	struct ArcNode* nextarc;  // 指向下一条弧的指针
	InfoType* info;  // 该弧相关信息的指针
} ArcNode;

typedef struct VNode{
	// 顶点的结点定义
	// 表头结点
	VertexType data;  // 顶点信息
	ArcNode* firstarc;  // 指向第一条附属该顶点的弧
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{
	// 图结构定义
	AdjList vertices;  // 图的顶点结构数组
	int vexnum, arcnum;  // 顶点数和边数
	int kind;
} ALGraph;

采用邻接表表示法构造有向图

/*------------采用邻接表表示法构造有向图------------*/
void GreateDG_ALG(ALGraph &G){
	// 构造有向图
	cin >> G.vexnum >> G.arcnum;
	for(i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.vertices[i].data = new char[10];
		cin >> G.vertices[i].data;  // 读入顶点信息
		G.vertices[i].firstarc = NULL;
	}
	for(k = 0; k < G.arcnum; k++){
		// 建立边表
		v1 = new char[10]; 
		v2 = new char[10];
		cin >> v1 >> v2;
		i = LocateVex_ALG(G, v1);  // 弧尾
		j = LocateVex_ALG(G, v2);  // 弧头
		p = new ArcNode;
		p->adjvex = j;
		p->nextarc = G.vertices[i].firstarc;
		p->info = NULL;
		G.vertices[i].firstarc = p;  // 前插
	}
}

采用邻接表表示法构造无向图

/*------------采用邻接表表示法构造无向图------------*/
void CreateUDG(ALGraph &G){
	cin >> G.vexnum >> G.arcnum;  // 输入总顶点数，总边数
	for(i = 0; i < G.vexnum; i++){
		// 输入各点，构造表头结点表
		cin >> G.vertices[i].data;  // 输入顶点值
		G.vertices[i].firstarc = NULL;  // 初始化表头结点的指针域为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插入顶点vi的边表头部
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		p2 = new ArcNode;  // 生成另一个对称的新的边结点*p2
		p2->adjvex = i;
		// 将新结点*p2插入顶点vj的边表头部 
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}

邻接表表示法的特点

  • 优点：空间效率高，容易寻找顶点的邻接点undefined邻接矩阵与邻接表表示法的关系
  • 缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便
在这里插入图片描述
  • 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。undefined十字链表——用于有向图
  • 区别
    – 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
    – 邻接矩阵的空间复杂度为O(n*2), 而邻接表的空间复杂度为O(n+e)。
  • 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图
  • 结点表中的结点的表示
    在这里插入图片描述

    – data：结点的数据域，保存结点的数据值。
    – firstin：结点的指针域，给出自该结点出发的的第一条边的边结点的地址。
    – firstout：结点的指针场，给出进入该结点的第一条边的边结点的地址。

  • 边结点表中的结点的表示
    在这里插入图片描述
- info：边结点的数据域，保存边的权值等。
- tailvex：本条边的出发结点的地址。
- headvex：本条边的终止结点的地址。
- hlink：终止结点相同的边中的下一条边的地址。
- tlink：出发结点相同的边中的下一条边的地址。typedef struct ArcBox{
	// 弧结点结构表示
	int tailvex, headvex;
	InfoType* info;
	struct ArcBox* hlink,* tlink;
} ArcBox;

typedef struct VexNode{
	// 顶点的结构表示
	VertexType data;
	ArcBox* firstin,* firstout;
} VexNode;

typedef struct{
	// 有向图的十字链表
	VexNode xlist[MAX_VERTEX_NUM];  // 顶点结点
	int vexnum, arcnum;  // 有向图的当前顶点数和弧数
} OLGraph;

void CreatDG_OLG(OLGraph &G){
	// 构造有向图
	cin >> G.vexnum >> G.arcnum;  // 顶点数，弧数
	for(i = 0; i < G.vexnum; i++){
		// 建立顶点表
		G.xlist[i].data = new char[10];
		cin >> G.xlist[i].data;  // 读入顶点信息
		G.xlist[i].firstin = NULL;
		G.xlist[i].firstout = NULL;
	}
	for(k = 0; k < G.arcnum; k++){
		// 建立十字链表
		v1 = new char[10];
		v2 = new char[10];
		i = LocateVex_OLG(G, v1);
		j = LocateVex_OLG(G, v2);
		p = new ArcBox;
		p->info = NULL;
		p->headvex = j;  // 弧的终点
		p->tailvex = i;  // 弧的起点
		p->hlink = G.xlist[j].firstin;  // 前插
		p->tlink = G.xlist[i].firstout;
		G.xlist[j].firstin = G.xlist[i].firstout = p;
	}
}undefined无向图的邻接多重表存储表示

在图的链接存储(邻接表、逆邻接表、十字链表和邻接多重表)中，表头向量需要占用n个存储单元，所有边结点需要占用2e或e存储单元，所以最多需要（n+2e）个存储单元，稀疏图采用这种存储方式可节省存储空间。

图的遍历

  • 定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。undefined深度优先搜索（DFS —— Depth_First Search）基本思想：仿树的先序遍历过程。
  • 遍历实质：找每个顶点的邻接点的过程。
  • 图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。怎样避免重复访问 ？
  • 解决思路：设置辅助数组 visited n ，用来标记每个被访问过的顶点。
    – 初始状态为0
    – i 被访问，改 visited i为1，防止被多次访问
在这里插入图片描述

简单分析

  • 访问起始点v;
  • 若v的第1个邻接点没访问过，深度遍历此邻接点；
  • 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。

详细归纳

在这里插入图片描述
  • 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；
  • 再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2；
  • 然后再从 w2 出发，进行类似的访问，…
  • 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
  • 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。
    – 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
    – 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

图的深度优先搜索算法

连通图
int visited[MAX_VERTEX_NUM];  // 全局变量
void Visit(VertexType x){cout << x << " ";}

/*-----------图的深度优先搜索算法（连通图）-----------*/
void DFS(Graph G, int v){
	Visit(v); 
	visited[v] = true;
	// FirstAdjVex(G, v) 表示v的第一个邻接点
	// NextAdjVex(G, v, w) 表示v相对于w的下一个邻接点
	// w >= 0 表示邻接点存在
	for(w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if(!visited[w]) DFS(G, w);
}

非连通图
/*-----------图的深度优先搜索算法（非连通图）-----------*/
void DFSTraverse(Graph G){
	for(v = 0; v < G.vexnum; ++v) visited[v] = false;  // 访问标志数初始化
	for(v = 0; v < G.vexnum; ++v)
		if(!visited[v]) DFS(G, v);
}

遍历图的过程实质上是对每个顶点查找其邻接点的过程。

若给定图的存储结构,则从某一顶点出发的遍历结果应是唯一的。

邻接矩阵表示图的深度优先搜索遍历
在这里插入图片描述
/*-----------邻接矩阵表示图的深度优先搜索遍历-----------*/
void DFS_AM(AMGraph G, int v){
	// 图G为邻接矩阵类型
	cout << v;
	// 访问第v个结点
	visited[v] = true;
	for(w = 0; w < G.vexnum; w++){
		// 一次检查邻接矩阵v所在行
		if((G.arcs[v][w] != 0) && (!visited[w]))
			DFS(G, w);
		// w是v的邻接点，如果w未访问，则递归调用DFS
	}
}

邻接表表示图的深度优先搜索遍历
在这里插入图片描述
/*-----------邻接表表示图的深度优先搜索遍历-----------*/
void DFS_AL(ALGraph G, int v){
	// 图G为邻接表类型
	cout << v;
	visited[v] = true;  // 访问第v个顶点
	p = G.vertics[v].firstarc;  // p指向v的边链表的第一个边结点
	while(p != NULL){
		// 边结点非空 
		w = p->adjvex;  //表示w是v的邻接点
		if(!visited[w]) DFS(G, w);  // 如果w未访问，则递归调用DFS
			p = p->nextarc;  // p指向下一个边结点
		}
}

DFS算法效率分析
  • 用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n^2)。
  • 用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。稠密图适于在邻接矩阵上进行深度遍历；
    稀疏图适于在邻接表上进行深度遍历。

广度优先搜索（BFS － Breadth_First Search）

基本思想：仿树的层次遍历过程

在这里插入图片描述

简单分析

  • 在访问了起始点v之后，依次访问 v的邻接点；
  • 然后再依次访问这些顶点中未被访问过的邻接点；
  • 直到所有顶点都被访问过为止。

广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。

因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

算法思想

  • 从图中某个顶点v出发，访问v，并置visitedv的值为true，然后将v进队。
  • 只要队列不空，则重复下述处理
    – 队头顶点u出队
    – 依次检查u的所有邻接点w，如果visitedw的值为false，则访问w，并置visitedw的值为true，然后将w进队

图的广序优先搜索遍历算法

在这里插入图片描述
连通图
/*------------广度优先非递归遍历连通图G（连通图）------------*/
void BFS(Graph G, int v){
	cout << v;
	visited[v] = true;  // 访问第v个顶点
	InitQueue(Q);
	EnQueue(Q, v);
	while(!QueueEmpty(Q)){
		DeQueue(Q, u);
		for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) 
			if(!visited[w]){
				// w为u的尚未访问的邻接顶点
				cout << w;
				visited[w] = false;
				EnQueue(Q, w);  // w进队
			}
	}
}

非连通图
/*------------广度优先非递归遍历连通图G（非连通图）------------*/
void BFSTraverse(Graph G){
	for(v = 0; v < G.vexnum; ++v) visited[v] = false;  // 访问标志数初始化
	for(v = 0; v < G.vexnum; ++v)
		if(!visited[v]) BFS(G, v);
}

BFS算法效率分析

  • 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n^2)。
  • 用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

DFS与BFS算法效率比较

  • 空间复杂度相同，都是O(n)(借用了堆栈或队列）；
  • 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

小结：

遍历图的过程实质上都是通过边或弧找邻接点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。

邻接矩阵O(n2) 邻接表O(n+e)

正文完
2022-06-08