数据的逻辑结构
集合: 元素间除同属一个集合外，无其他关系
线性结构: 一个对一个，如线性表、栈、队列
树形结构: 一个对多个，如树
图结构: 多个对多个，如图
图的定义和术语
G=(V,E)
V: 顶点的有穷非空集合
E: 边的有穷集合
ps: V全称vertex,E全称Edge
无向图: 每条边都是无方向的
有向图: 每条边都是有方向的
完全图: 任意两个点都有一条边相连
稀疏图: 有很少边或弧的图(e<nlogn)
稠密图: 有较多边或弧的图
网: 边/弧带权的图
邻接: 有边/弧相连的两个顶点之间的关系。
存在(vi,vj),则称vi和vj互为邻接点 ()表示边
存在<vi,vj>,则称vi邻接到vj，vj邻接于vi <>表示弧
关联(依附): 边/弧与顶点之间的关系
存在(vi,vj)/<vi,vj>，则称边/弧关联于vi和vj
顶点的度: 与该顶点相关联的边的个数，记为TD(v)
在有向图中，顶点的度等同于该顶点的入度和出度之和
顶点v的入度是以v为终点的有向边的条数，记作ID(v)
顶点v的出度是以v为始点的有向边的条数，记作OD(v)
图中个顶点的度
当有向图中仅一个顶点的入度为0，其余顶点的入度均为1，此时是何形状？
是树，而且是一棵有向树
路径: 接续的边构成的顶点序列
路径长度: 路径上边或弧的数目/权值之和
回路(环): 第一个顶点和最后一个顶点相同的路径
简单路径: 除路径起点和终点可以相同外，其余顶点均不相同的路径
简单回路:除路径起点和终点相同外，其余顶点均不相同的回路
连通图(强连通图)
在无(有)向图G=(V,{E})中，若对任一两个顶点v,u都存在从v到u的路径，则称G是连通图(强连通图)
权和网
图中边或弧锁具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费
带权的图称为网
子图
设有两个图G=(V,{E})、G1=(V1,{E1}),若V1包含于V，E1包含于E，则称G1是G的子图
连通分量
无向图G的极大连通子图称为G的连通分量
极大连通子图意思是: 该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再联通
有向图G的极大连通子图称为G的强联通分量
极大连通子图意思是: 该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强联通的
极小连通子图: 该子图是G的联通子图，在该子图中删除任意一条变，子图不再连通
生成树: 包含无向图G所有顶点的极小连通子图
生成森林: 对费连通图，由各个连通分量的生成树的构成的集合
图的类型定义
抽象数据类型定义
ADT Graph{
数据对象V: 具有想你那个桶特性的数据元素的集合，称为顶点集
数据关系R: R={VR}
VR={
}
基本操作
创建
查找
获取元素
插入
删除
比较重要的操作
GreateGraph(&G,V,VR)
构造图
DFSTraverse(G)
深度优先遍历
BFSTraverse(G)
广度优先遍历
图的存储结构
图的逻辑结构: 多对多
图没有顺序存储结构，但可以借助二维数组来表示元素间的关系 数组表示法(邻接矩阵)
表示法:
邻接矩阵(数组)表示法
邻接表(链式)表示法
邻接矩阵的存储表示: 用两个数组分别存储定点表和邻接矩阵
邻接矩阵表示法
无向图的邻接矩阵表示法
有向图的邻接矩阵表示法
网(有权图)的邻接矩阵表示法
邻接矩阵的存储形式
邻接矩阵的存储表示: 用两个数组分别存储顶点表和邻接矩阵
123456789typedef char VerTexType //设顶点的数据类型为字符型typedef int ArcType //假设边的权值类型为整型typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vernum,arcnum; //图的当前顶点数和边数}AMGraph
采用邻接矩阵表示法创建无向网
思想
1.输入总顶点数和总边数
2.依次输入点的信息存入顶点表中
3.初始化邻接矩阵，使每个权值初始化为极大值
4.构造邻接矩阵
邻接矩阵优点
直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有"邻接点"
方便计算任一顶点的度(从该点发出的边数为"出度"，指向该点的边数为"入度")
无向图: 对应行/列非0元素的个数
有向图: 对应行非0元素的个数是"出度"；对应列非0元素的个数是"入度"
缺点
不便于增加和删除顶点
浪费空间-存稀疏图有大量无效元素
浪费时间-统计稀疏图中一共有多少条边
邻接表表示法
邻接表
无向图
特点
邻接表不唯一
若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表节点。适宜存储稀疏图
无向图中顶点vi的度为第i个单链表中的结点数
有向图
特点
顶点vi的出度为第i个单链表中的结点个数
顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数
逆邻接表
顶点vi的入度为第i个单链表中的结点个数
顶点vi的出度为整个单链表中邻接点域值是i-1的结点个数
练习:已知某网的邻接表，请画出该网络
图的邻接表存储表示
1234567891011121314151617
typedef struct VNode{ VerTexType data; //顶点信息 ArcNode *firstarc; //指向第一条衣服该顶点的边的指针}VNode,AdjList[MVNum]; //AdjList表示邻接表类型typedef struct ArcNode{ //边结点 int adjvex; //该边所指向的顶点位置 struct ArcNode *nextarc; //指向下一条边的指针 OtherInfo info; //和边相关的信息}ArcNode; //图的结构定义typedef struct{ AdjList vertices; //vertices--vertex的复数 int vexnum,arcnum; //图的当前顶点数和弧数}ALGraph;
采用邻接表表示法创建无向网
1.输入总顶点数和总边数
2.建立顶点表
依次输入点的信息存入顶点表中
使每个表头结点的指针域初始化为NULL
3.创建邻接表
依次输入每条边依附的两个顶点
确定两个顶点的序号i和j，建立边结点
将此边结点分别插入到vi和vj对应的两个边链表中
邻接表特点
方便查找任一顶点的所有邻接点
节约稀疏图的空间
对无向图需要N个头结点+2E个弧节点
对有向图需要N个头结点+E个弧节点
方便计算任一顶点的度
对无向图容易
对有向图只能计算出度；需要构建逆邻接表(存指向自己的边)来方便计算入度
不方便检查任意一对顶点间是否存在边
邻接矩阵与邻接表表示法的关系
联系
邻接表中每个链表对应于邻接矩阵中的一行，链表中节点个数等于一行中非零元素的个数
区别
对任一确定的无向图，邻接矩阵是唯一的(行号与顶点编号一致)，但邻接表不唯一
邻接矩阵的空间复杂度为O(n^2),而邻接表的空间复杂度为O(n+e)
用途
邻接矩阵多用于稠密图，而邻接表多用于稀疏图
十字链表
十字链表法是有向图的另一种链式存储结构，是将有向图的邻接表和逆邻接表结合起来形成的一种链表
有向图中的每一条弧对应十字链表中的一个弧节点，同时有向图中的每个顶点在十字链表中对应有一个节点，叫做顶点结点
邻接多重表
图的遍历
从给出的连通图中某一顶点触发，沿着一些边访遍图中所有顶点，且使每个顶点仅被访问一次，就叫图的遍历，它是图的基本运算
遍历实质: 找每个顶点邻接点的过程
图的特点
图中可能存在回路，且图的任一顶点都可能与其他顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点
怎样避免重复访问？
解决思路:
设置辅助数组visited[n],用来标记每个被访问过的顶点
初始状态visited[i]为0
顶点i被访问，改visited[i]为1，防止多次访问
图常用的遍历方法:
深度优先搜索DFS
广度优先搜索BFS
深度优先遍历
思想
点亮迷宫中所有的灯
方法:
例
深度优先搜索遍历算法的实现
邻接矩阵表示的无向图深度遍历实现
DFS算法效率分析
用邻接矩阵来表示图，遍历图中每个顶点都要从头扫描该顶点所在的行，时间复杂度为O(n^2)
用邻接表来表示图，虽然有2e个表节点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)
结论:
稠密图适用于在邻接矩阵上进行深度遍历
稀疏图适于在邻接表上进行深度遍历
非连通图的遍历
刚刚是连通图的遍历，那么非连通图该如何遍历呢？
如果某个连通分量中全部已经遍历过还剩有没遍历过的顶点，那么就以该顶点开始继续DFS遍历
广度优先遍历
方法:
从图的某一顶点护法，首先访问该顶点所有邻接顶点，再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点
重复此过程，直至所有顶点均被访问为止
非连通图的BFS遍历
实现
邻接表表示的无向图广度遍历实现
BFS算法效率分析
如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检查矩阵中的整整一行(n个元素)，总的时间代价是O(n^2)
用邻接表来表示图，虽然有2e个表结点，但只需扫描e个顶点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)
DFS和BFS算法效率比较
空间复杂度相同，都是O(n)（借用了堆栈和队列）
时间复杂度值与存储结构相关(邻接矩阵或邻接表)有关，与搜索路径无关
图的应用
最小生成树
生成树: 包含无向图G所有顶点的极小连通子图
一个图的生成树不唯一
生成树特点:
1.生成树的顶点个数与图的顶点个数相同
2.生成树是图的极小连通子图，去掉一条边则非连通
3.一个有n个顶点的连通图的生成树有n-1条边
4.在生成树中加一条边必然形成回路
5.生成树中任意两个顶点间的路径是唯一的
6.含有n个顶点n-1条边的图不一定是生成树
无向图的生成树
深度优先生成树
广度优先生成树
设图G=(V,E)是连通图，当从图任一顶点触发遍历图G时，将边集E(G)分成两个集合T(G)和B(G),其中T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图G的极小连通子图，即G1是连通图G的生成树
最小生成树: 给定一个无向网，在该网的所有生成树种，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树
最小生成树的典型用途
在n个城市间建立通信网，使n个城市应铺n-1条路
但每个线路都有对应的经济成本，而n个城市最多有n(n-1)/2条线路，那么如何选择n-1条线路，使得花费最少
数学模型
顶点--表示城市，有n个；
边-表示线路，有N-1条
边的权值--表示线路的经济代价
连通图--表示n个城市间通信网
构造最小生成树(Minimum Spanning Tree)
构造最小生成树的算法很多，其中多数算法都利用了MST的性质。
MST性质： 设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若边(u,v)是一条具有最小权值的边，其中u包含于U，v包含于V-U，则比存在一棵包含边(u,v)的最小生成树
MST性质解释
在生成树的构造过程中，图中n个顶点分属两个集合
1.已落在生成树上的顶点集：U
2.尚未落在生成树上的顶点集：V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
ps:MST其实是一种贪心算法
构造最小生成树方法1：普里姆(Prim)算法
算法思想
ps:初始节点u0可以随机选择，每次选择邻接节点时不能构成回路
构造最小生成树方法2:克鲁斯卡尔(kruskal)算法
算法思想
ps:最小生成树不唯一
两种算法比较
ps: prim和kruskal算法都是利用了最小生成树的MST性质，也是贪心的体现
最短路径
典型应用
交通网络的问题--从甲地到乙地之间是否有公路连通？在多条通路的情况下，哪一条路最短？
交通网络用有向网来表示:
顶点--表示地点，
弧--表示两地点有路连通
弧上的权值--表示两地点之间的距离、交通费或途中所花费的时间等。
如何能够使一个地点到另一个地点的云舒时间最短或运费最省？这就是一个求两个地点间的最短路径问题
问题抽象: 在有向网那个中A点(源点)到达B点(终点)的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
> 最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边
第一类问题: 两点间最短路径
第二类问题: 某源点到其他各点最短路径
以上是两种常见的最短路径问题，有对应的以下算法:
1.单源最短路径--用Dijkstra（迪杰斯特拉）算法
2.所有顶点间的最短路径--用Floyd(佛洛依德)算法
迪杰斯特拉算法：
代码实现:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
/**最短路径:迪杰斯特拉实现 (本例中使用邻接矩阵表示图)思想: 同样是把所有顶点划分为两个结合，一个是已访问顶点，一个是未访问顶点，通过算法不断找出下一个最短路径顶点并加入到已访问顶点直至最后简单记忆需要四步initscanaddupdate*/const INF = 2<<31 - 1func dj(G AMGraph, vo int) ([]int, []int) { /** 初始化 visited存储已访问的顶点 D存储vo到i顶点的最短距离 P存储i位置的前继顶点位置 */ visited := make([]bool, G.NumVers) D := make([]int, G.NumVers) P := make([]int, G.NumVers) for i := 0; i < G.NumVers; i++ { D[i] = G.Arcs[vo][i] P[i] = -1 } visited[0] = true k := 0 for i := 1; i < G.NumVers; i++ { // 总共n个节点 还要找 n-1个节点，每次循环确定一个顶点，故需要n-1次循环 /** scan: 找出未访问顶点集合中，距离vo最近的顶点 */ min := INF for j := 0; j < G.NumVers; j++ { if !visited[j] && D[j] < min { k = j min = D[j] } } // add: 将上步找到的最小路径邻接顶点加入到已访问顶点集合中，记作临时节点 visited[k] = true // update://比较通过临时顶点访问其邻接顶点vi的距离与原vo访问vi的距离，如果减小了距离，则更新D[j2]的路径长度 for j2 := 0; j2 < G.NumVers; j2++ { if !visited[j2] && min+G.Arcs[k][j2] < D[j2] { D[j2] = min + G.Arcs[k][j2] P[j2] = k } } } return D, P}
时间复杂度: O(n^2)
佛洛依德算法:
对于所有顶点间的最短路径
方法1: 每次以一个顶点为源点，重复执行Dijkstra算法n次
方法2: 佛洛依德(Floyd)算法
算法思想
逐个顶点试探
从vi到vj的所有可能存在路径中
宣传u一条长度最短的路径
主要利用此属性: 如果v0->v1->v2是最短路径 那么v0->v1 v1->v2也一定是最短路径
v0是v1的前驱节点
12345678910
for k:=0;k<G.verNum;k++{ for i:=0;i<G.verNum;i++{ for j:=0;j<G.verNum;j++{ if D[i][k]+D[k][j]<D[i][j]{ D[i][j] = D[i][k]+D[k][j] P[i][j] = P[i][k] //这里不能直接使用P[i][j] = k,因为P[i][j]的含义是路径vi->...->vj路径的前驱节点,要存储的是整个路径的首顶点的下一个顶点 } } }}
> 对于P[i][j] = P[i][k]的解释
拓扑排序
有向无环图及其应用
有向无环图: 无环的有向图，简称DAG图(Directed Acycline Graph)
有向无环图常用来描述一个工程或系统的进行过程(通常把计划、施工、生产、程序流程等当做是一个工程)
一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成
AOV网:
用一个有向图表示一个工程各子工程及其相互制约关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Active On Vertex network)
用来解决拓扑排序问题
AOE网:
用一个有向网表示一个工程的各个工程及其互相制约关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网(Active On Edge network)
用来解决关键路径问题
AOV网的特点:
* 若从i到j有一条有向路径，则i是j的前驱；j是i的后续
* 若<i,j>是网中的有向边，则i是j的直接前驱；j是i的直接后继
* AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的
拓扑排序
在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列中，i一定排在j的前面，具有这种性质的线性序列成为拓扑有序序列，响应的拓扑有序排序的算法成为拓扑排序
例
拓扑排序的方法
在有向图中选中一个没有前驱的顶点且输出
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或大年图中不存在无前驱的顶点为止
检测AOV网中是否存在环的方法
对有向图过早顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环
一个AOV网的拓扑序列是不唯一的
关键路径(https://www.bilibili.com/video/av36909370)
某项目的任务是对A公司的办公室进行装修，如果10月1日前完成装修工程，项目应该何时开始？
准备一个家庭宴会，晚6点开始，最迟几点开始准备？压缩哪项活动时间可以使总时间减少？
把工程计划表示为边表示活动的网络，即AOE网，用顶点表示事件，弧表示活动，弧的权表示活动持续时间
事件表示在它之前的活动已经完成，在它之后活动可以开始
1.若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动
2.如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程完成时间，如a1、a4
3.处于所有的关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径编程不是关键路径。这时，必须重新寻找关键路径，如a1由6天变成3天，就会改变关键路径
顺着求最大（最早发生） 逆着求最小（最晚发生）
邻接矩阵法建立网的结构
邻接表法建立网的结构
无向图、有向图
深度优先遍历
广度优先遍历
最小生成树算法实现
无向网/有向网迪杰斯特拉算法最短路径实现
佛洛依德算法实现