图
图
WhYqZz图的定义
图G由顶点集V和边集E组成，记为G=(V,E),其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合。若V={$v_{1}$,$v_{2}$,…,$v_{n}$},则用|V|表述图G中顶点的个数，也称图G的阶，$E={(u,,v)|u\in V,v\in V }$,用|E|表示图G中边的条数
注意：线性表可以是空表，树可以是空树，但是图不可以是空，即V一定是非空集，但一个图的边集可以为空集
有向图、无向图
无向图
若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为$(v,w)$或$(w,v)$,因为$(v,w)$=$(w,v)$，其中v、w是顶点。可以说顶点v、w互为邻接点。边$(v,w)$依附于顶点w和v，或者说边$(v,w)$和顶点v、w相关联
$G_{2}=(V_{2},E_{2})$
$V_{2}$={$A,B,C,D,E$}
$E_{2}$={$(A,B),(B,D),(B,E),(C,D)(C,E),(D,E)$}
有向图
若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为$<v,w>$,其中v、w是顶点，v称为弧尾，w成为弧头，$<v,w>$称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。$<v,w>$≠$<w,v>$
$G_{1}=(V_{1},E_{1})$
$V$={$A,B,C,D,E$}
$E$={$<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>$}
简单图、多重图
简单图
- 不存在重复边
- 不存在顶点到自身的边
多重图
图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则图G为多重图
数据结构课程中只涉及简单图
顶点的度、入度、出度
- 对于无向图：
- 顶点v的度是指依附于顶点v的边的条数，记为TD(v)
- 在具有n个顶点，e个边的无向图中$\sum_{i=1}^{n}TD(v_{i})$=$2e$
- 即无向图所有顶点的度之和等于边的个数的2倍
- 对于有向图：
- 入度是以顶点v为终点的有向边的数目，记为ID(v)
- 出度是以顶点v为起点的有向边的数目，记为OD(v)
- 顶点的度等于其入度和出度的和，即TD(v)=ID(v)+OD(v)
- 在具有n个顶点，e个边的有向图中$\sum_{i=1}^{n}ID(v_{i})=\sum_{i=1}^{n}OD(v_{i})$=$e$
顶点-顶点关系的描述
- 路径——顶点$v_{p}$到顶点$v_{q}$之间的路径是指顶点序列，$v_{p},v_{i1},v_{i2},..,v_{im},v_{q}$(有向图的路径也是有向的，无向图之间也有可能不存在路径)
- 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
- 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径
- 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
- 路径长度：路径上边的数目
- 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若u和v根本不存在路径，则记该距离为无穷($\infty$)
- 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
- 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
连通图、强连通图
- 若无向图图G中任意两个顶点都是联通的，则称图G为联通图，否则称为非连通图
- 常见考点：
- 对于n个顶点的无向图G，若G是连通图，则最少有$n-1$条边
- 若G是非连通图，则最多可能有$C_{n-1}^{2}$条边
- 若有向图中任何一对顶点都是强连通的，则称此图为强连通图
- 常见考点：
- 对于n个顶点的有向图G，若G是强连通图，则最少有n条边(形成回路)
研究图的局部——子图
设有两个图G=(V,E),G’=(V’,E’),若V’是V的子集，且E’是E的子集，则称G’是G的子图
若有满足V(G’)=V(G)的子图G’，则称其为图G的生成子图
连通分量
无向图中的极大连通子图称为连通分量(子图必须连通，且包含尽可能多的顶点和边)
强连通分量
有向图中的极大强连通子图称为有向图的强连通分量
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图(边要尽可能少，但要保持连通)
若图中顶点数为n，则他的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会生成回路
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林
边的权、带权图/网
- 边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值被称为边的权值
- 带权图/网——边上带有权值的图被称为带权图，也称网
- 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
几种特殊的图
- 无向完全图——无向图中任意两个顶点之间都存在边
若无向图的顶点$|V|=n$,则$|E|\in[0,C_{n}^{2}]=[0,n(n-1)/2]$ - 有向完全图——有向图中任意两个顶点之间都存在方向相反的两个弧
若有向图的顶点$|V|=n$,则$|E|\in[0,2C_{n}^{2}]=[0,n(n-1)]$ - 稀疏图——边数很少的图称为稀疏图
- 稠密图——反之
没有绝对的界限，一般来说$|E|<|V|\log_{2}{|V|}$时，就可以将G视为稀疏图 - 树——不存在回路，且连通的无向图
n个顶点的树，必有n-1条边
常见考点：n个顶点的图，若$|E|>n-1$,则一定有回路 - 有向树——一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树
知识回顾与重要考点
图的存储
邻接矩阵法
1 |
|
结点数为n的图G=(V,E)的邻接矩阵A是n*n的，将G的顶点编号为$v_{1},v_{2},…,v_{n}$则
如何求顶点的度、入度、出度
- 无向图
第i个结点的度=第i行(或第i列)的非零元素个数 - 有向图
- 第i个结点的出度=第i行的非零元素个数
- 第i个结点的入度=第i列的非零元素个数
- 第i个结点的度=第i行、第i列的非零元素个数之和
邻接矩阵法存储带权图(网)
1 |
|
邻接矩阵法的性能分析
空间复杂度：$O(|V|^2)$——只和顶点数有关，和实际的边数无关
适合存储稠密图
无向图的邻接矩阵是对称矩阵，可以压缩存储(只存储上三角区/下三角区)
回顾特殊矩阵的压缩存储
邻接矩阵法的性质
设图G的邻接矩阵为A(矩阵元素为0/1)，则$A^n$的元素$A^n[i][j]$等于由顶点$i$到顶点$j$的长度为$n$的路径的数目
知识回顾与重要考点
- 如何计算指定顶点的度、入度、出度（分无向图、有向图来考虑）？时间复杂度如何？
- 如何找到与顶点相邻的边（入边、出边）？时间复杂度如何？
- 如何存储带权图？
- 空间复杂度——$O(|V|^2)$，适合存储稠密图
- 无向图的邻接矩阵为对称矩阵，如何压缩存储？
- 设图G的邻接矩阵为A（矩阵元素为0/1），则$A^n$的元素$A^n$[i][j]等于由顶点i到顶点j的长度为n的路径的数目
邻接表法(顺序+链式存储)
1 | //顶点 |
知识回顾与重要考点
| 邻接表 | 邻接矩阵 | |
|---|---|---|
| 空间复杂度 | 无向图$O(|V|+2|E|)$ 有向图$O(|V|+|E|)$ | $O(|V|^2)$ |
| 适合用于 | 存储稀疏图 | 存储稠密图 |
| 表示方式 | 不唯一 | 唯一 |
| 计算度/入度/出度/ | 计算有向图的度、入度不方便，其余很方便 | 必须遍历对应行和列 |
| 找相邻的边 | 找有向图的入边不方便，其余很方便 | 必须遍历对应行或列 |
十字链表法(存储有向图)
性能分析
空间复杂度：O(|V|+|E|)
如何找到指定顶点的所有出边——顺着绿色路线找
如何找到指定顶点的所有入边——顺着橙色路线找
注意：十字链表法只用于有向图
邻接多重表存储无向图
空间复杂度：O(|V|+|E|)
删除边、删除结点等操作方便
注意：邻接多重表只适用于存储无向图
知识回顾与重要考点
基本操作
- Adjacent(G,x,y):判断图G是否存在边<x, y>或(x, y)。
- Neighbors(G,x)：列出图G中与结点x邻接的边。
- InsertVertex(G,x)：在图G中插入顶点x。
- DeleteVertex(G,x):从图G中删除顶点x。
- AddEdge(G,x,y)：若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边。
- RemoveEdge(G,x,y)：若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边。
- FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
- NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
- Get_edge_value(G,x,y):获取图G中边(x, y)或<x, y>对应的权值。
- Set_edge_value(G,x,y,v):设置图G中边(x, y)或<x,y>对应的权值为v。
Adjacent(G,x,y)：判断是否存在边
- 邻接矩阵：直接看矩阵对应位置的值是否为1
- 邻接表：找目标结点所对应的编号，查看链表后边是否有所找结点
Neighbors(G,x)：列出相邻的边
- 邻接矩阵：
- 无向图：查看对应结点所在行和列
- 有向图：
- 出边：遍历所在行
- 入边：遍历所在列
- 邻接表：
- 无向图：查看对应结点的链表
- 有向图：
- 出边：查看对应结点的链表
- 入边：需要遍历整个邻接表
InsertVertex(G,x)：插入
- 邻接矩阵：
- 在保存顶点的数组后边空白的位置加入新结点的数据
- 邻接表：
- 在保存顶点的数组后边空白的位置加入新结点的数据，将链表指针设为NULL
DeleteVertex(G,x):删除
- 邻接矩阵：
- 无向图/有向图：将删除结点所在行列的数据全设为0，再在顶点的结构体中修改表示是否为空结点的bool变量
- 邻接表：
- 无向图：将目标结点以及所有相连的边结点删除，再遍历整个邻接表，删除指向删除结点的边的信息
- 有向图：
- 删出边：删除目标结点后边的链表
- 删入边：遍历整个邻接表
AddEdge(G,x,y)：增加边
- 邻接矩阵：将矩阵对应位置改为1
- 邻接表：在对应的两个结点的链表中插入新的边的信息
FirstNeighbor(G,x)：找到指定顶点的第一个邻接点
- 邻接矩阵：
- 无向图：找到顶点所对应一行的第一个1
- 有向图：
- 出边：扫描行
- 入边:扫描列
- 邻接表
- 无向图：找到边结点链表中的第一个结点
- 有向图：
- 出边：找到边结点链表中的第一个结点
- 入边：遍历整个邻接表
若无邻接点则返回-1
NextNeighbor(G,x,y)：找到邻接点的下一个邻接点
- 邻接矩阵
- 扫描目标顶点所在行，找到第二个1
- 邻接表
- 找到链表的第二个结点
Get_edge_value(G,x,y):获取权值/Set_edge_value(G,x,y,v):设置权值
与Adjacent(G,x,y)：判断是否存在边雷同，核心是找到边
