数据结构基础之图

发表于： 2017-12-24 更新于： 2024-04-04 分类于：数据结构与算法

字数： 505 阅读：≈ 3分钟浏览：评论：

简介

概念:
- 由顶点的有穷非空集合和顶点之间边的集合组成, 通常表示为: G(V,E), 其中, G表示一个图, V是图G中顶点的集合, E是图G中边的集合
异同:
- 线性表中把数据元素叫做元素, 树中将数据元素叫结点, 在图中数据元素叫做顶点(Vertex)
- 线性表中可以没有数据元素,称为空表; 树中可以没有结点,叫做空树; 图中不允许没有顶点,若V是顶点的集合, 则集合V有穷且非空
- 线性表中, 相邻的数据元素具有线性关系; 树结构中, 相邻两层的结点具有层次关系; 图中, 任意两个顶点之间都可能有关系, 顶点之间的逻辑关系用边来表示, 边集可以是空

图的抽象数据类型

ADT 图(Graph)
Data
	顶点的有穷非空集合和边的集合
Operation
	CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G
	DestroyGraph(*G): 图G存在则销毁
	LocateVex(G, u): 若图G中存在顶点u, 则返回图中的位置
	GetVex(G, v): 返回图G中顶点v的值
	PutVex(G, v, value): 将图G中顶点v赋值value
	FirstAdjVex(G, *v): 返回顶点v的一个邻接顶点, 若顶点在G中无邻接顶点返回空
	NextAdjVex(G, v, *w): 返回顶点v相对于顶点w的下一个邻接顶点, 若w是v的最后一个邻接点, 则返回空
	InsertVex(*G): 在图G中增添新顶点v
	DeleteVex(*G, v): 删除图G中顶点v及相关的弧
	InsertArc(*G, v, w): 在图G中增填弧<v,w>, 若G是无向图, 还需要添加对称弧<w,v>
	DFSTraverse(G): 对图G中进行深度优先遍历, 在遍历过程对每个顶点调用
	HFSTraverse(G): 对图G中进行广度有限遍历, 在遍历过程对每个顶点调用
endADT

存储结构

邻接矩阵(Adjacency Matrix)

用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。设图G有n个顶点, 则邻接矩阵是一个n*n的方阵, 定义为 $$arc[i][j] = \begin{cases} 1, \quad 若(v_i,v_j)\in E或\left\langle v_i,v_j \right\rangle \in E\ 0, \quad 反之 \end{cases} $$
特性:
- 无向图的边数是一个对称矩阵
- 有向图中, 入度为列之和, 出度为行之和
优点:
- 可以快速查到一个顶点和另一顶点之间的关联关系
缺点:
- 占用了太多的空间

网图表示

定义:
- 设图G是网图, 有n个顶点, 则邻接矩阵是一个n*n的方阵, 定义为: $$ arc[i][j] = \begin{cases} W_{ij}, \quad 若(v_i,v_j)\in E或\left\langle v_i,v_j \right \rangle \in E\ 0, \quad 若i=j\ \infty, \quad 反之 \end{cases} $$
说明:
- $W_{ij}$表示$(v_i,v_j)$或$<v_i,v_j>$上的权值
- $\infty$表示一个计算机允许的、大于所有边上的权值的值，也就是一个不可能的极限值

邻接表(Adjacency List)

定义:
- 为了解决邻接矩阵占用空间的问题, 采用数组与链表相结合的存储方法称为邻接表
特性:
- 图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。

逆邻接表

有向图的逆邻接表: 对每个顶点vi都建立一个链接为vi为弧头的表
特性:
- 解决逆向查找的麻烦
- 与邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点

十字链表

将邻接表和逆邻接表结合起来
- 顶点表结构: data|firstin|firstout
  - firstin: 入边表头指针, 指向该顶点的入边表中第一个结点
  - firstout: 表示出边表头指针, 指向该顶点的出边表中的第一个结点
- 边表结点结构: tailvex|headvex|headlink|taillink, 如果是网, 还可以增加一个weight域来存储权值
  - tailvex: 弧起点在顶点表的下标
  - headvex: 弧终点在顶点表的下标
  - headlink: 入边表指针域, 指向终点相同的下一条边
  - taillink: 指向边表指针域, 指向起点相同的下一条边

邻接多重表

重新定义边表结构: ivex|ilink|jvex|jlink
- ivex和jvex是与某条边依附的两个顶点在顶点表中的下标
- ilink指向依附顶点ivex的下一条边
- jlink指向依附顶点jvex的下一条边

边集数组

由两个一维数组构成, 一个存储顶点的信息, 另一个存储边的信息。边数组的每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成

图的遍历(Traversing Graph)

从图中某一顶点出发访遍图中其余顶点, 且使每一个顶点仅被访问一次的过程

深度优先遍历(Depth_First_Search)

定义:
- 从图中某个顶点v出发, 访问此顶点, 然后从v的未访问邻接点出发深度优先遍历图, 直至图中所有和v有路径相通的顶点都被访问到, 若图中尚有顶点未被访问到, 则另选图中一个未曾被访问到的顶点作为起点, 重复上述过程, 直至图中所有顶点都被访问到为止
特征: 类似树的前序遍历
不同存储结构比较: 对于n个顶点e条边的图
- 邻接矩阵: O(n^2)
- 邻接表: O(n+e)

广度优先遍历(Breadth_First_Search)

定义:
- 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
特征: 类似树的层序遍历

异同

同: 时间复杂度一样
异:
- 对顶点的访问顺序不同
- 深度优先更适合目标比较明确, 以找到目标为主要目的的情况
- 广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

最小生成树(Minimum Cost Spanning Tree)

定义: 构造连通网的最小代价生成树

普里姆(Prim)算法

定义:
- 假设N = (P,{E})是连通网, TE是N上最小生成树中边的集合。算法从U = {u0}(u0属于V),TE={}开始。重复执行下述操作：在所有u属于U, v属于V-U的边(u,v)属于E中找一条代价最小的边(u0,v0)并入集合TE, 同时v0并入U, 直至U=V为止。此时TE中必有n-1条边, T=(V,{TE})为N的最小生成树。
时间复杂度: O(n^2)
证明: 反证法

克鲁斯卡尔(Kruskal)算法

定义:
- 假设N = (V,{E})是连通网, 则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}}, 图中每个顶点自成一个连通分量。在E中选择代价最小的边, 若该边依附的顶点落在T中不同的连通分量上, 则将此边加入到T中, 否则舍去此边而选择选择下一条代价最小的边。依次类推, 直至T中所有的顶点都在同一连通分量上为止。
时间复杂度：O(eloge)
证明: 归纳法

使用场景

普里姆算法对于稠密图, 即边数非常多的情况更好些
克鲁斯卡尔算法主要针对边来展开, 边数少时效率会非常高, 对于稀疏图有很大优势

最短路径

非网图: 由于边上没有权值, 最短路径指两顶点之间经过的边数最少的路径
网图: 两顶点之间经过的边上权值之和最少的路径, 称路径上第一个顶点是源点, 最后一个顶点是终点。

迪杰斯特拉(Dijkstra)算法

定义概述:
- 典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
时间复杂度: O(n^2)

弗洛伊德(Floyd)算法

定义概述：
- 解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
时间复杂度: O(n^3)
空间复杂度: O(n^2)

拓扑排序

无环: 图中没有回路

介绍

AOV网(Activity On Vertex NetWork):
- 在一个表示工程的有向图中, 用顶点表示活动, 用弧表示活动之间的优先关系, 这样的有向图为顶点表示活动的网。
拓扑序列：
- 设G=(V,E)是一个具有n个顶点的有向图, V中的顶点序列v1,v2,…,vn, 满足若从顶点vi到vj有一条路径, 则在顶点序列中顶点vi必须在vj之前。
拓扑排序：
- 对一个有向图构造拓扑序列的过程

拓扑排序算法

解决问题: 工程能否顺利的进行
基本思路：从AOV网中选择一个入度为0的顶点输出, 然后删去此顶点, 并删除以此顶点为尾的弧, 继续重复此步骤, 直到输出全部顶点或者AOV网中不存在入度为0的顶点为止
时间复杂度: O(n+e)

关键路径

解决问题: 工程完成需要的最短时间

介绍

AOE网:
- 在一个表示工程的带权有向图中, 用顶点表示事件, 用有向边表示活动, 用边上的权值表示活动的持续时间, 这种有向图的边表示活动的网。
路径长度：
- 路径上各个活动所持续的时间之和
关键路径：
- 从源点到汇点具有最大长度的路径
关键活动: 关键路径上的活动

算法描述

准备两个数组
- a：最早开始时间数组etv
- b：最迟开始时间数组。（针对顶点即事件而言）

步骤:

从源点V0出发，令etv[0]（源点）=0，按拓扑有序求其余各顶点的最早发生时间etv[i]（1 ≤ i ≤ n-1）。同时按照上一章拓扑排序的方法检测是否有环存在。
- 顶点Vk的最早发生时间etv[k]公式: $$ etv[k] = \begin{cases} 0, \quad 当 k = 0 时\ max{etv[i] + len<v_i,v_k>}, \quad 当k\neq0且<v_i,v_j>\in P[k] \end{cases} $$
- P[k]表示所有到达顶点Vk的弧的集合
- $len<v_i,v_k>为弧<v_i,v_k>上的权值$
从汇点Vn出发，令ltv[n-1] = etv[n-1]，按拓扑排序求各个其余各顶点的最迟发生时间ltv[i]（n-2 ≥ i ≥ 2）;
- 顶点Vk的最晚发生时间ltv[k]公式: $$ ltv[k] = \begin{cases} etv[k], \quad 当 k = n-1 时\ min{ltv[j] + len<v_k,v_j>}, \quad 当k \lt n-1且<v_k,v_j>\in S[k] \end{cases} $$
- S[k]表示所有从顶点Vk出发的弧的集合
- $len<v_k,v_j>为弧<v_k,v_j>上的权值$
- 其实是把拓扑序列倒过来进行
根据各顶点的etv和ltv数组的值，求出弧（活动）的最早开工时间和最迟开工时间，求每条弧的最早开工时间和最迟开工时间是否相等，若相等，则是关键活动。

注意：
- 1，2 完成点（事件）的最早和最迟。
- 3根据事件来计算活动最早和最迟，从而求的该弧（活动）是否为关键活动

参考

深度优先和广度优先遍历及其 Java 实现

Patrick's Blog

数据结构基础之图

简介

相关定义

图的顶点与边间关系

连通图

图的抽象数据类型

存储结构

邻接矩阵(Adjacency Matrix)

网图表示

邻接表(Adjacency List)

逆邻接表

十字链表

邻接多重表

边集数组

图的遍历(Traversing Graph)

深度优先遍历(Depth_First_Search)

广度优先遍历(Breadth_First_Search)

异同

最小生成树(Minimum Cost Spanning Tree)

普里姆(Prim)算法

克鲁斯卡尔(Kruskal)算法

使用场景

最短路径

迪杰斯特拉(Dijkstra)算法

弗洛伊德(Floyd)算法

拓扑排序

介绍

拓扑排序算法

关键路径

介绍

算法描述

步骤:

参考