数据结构第六章图

2023-03-08

字数统计: 4k | 阅读时长≈ 14 分钟

系列链接
第一章概述	第二章线性表	第三章栈与队列	第四章串
第五章树与二叉树	第六章图	第七章查找	第八章排序

🔥基本概念

图G记为G=(V,E)
顶点集V：所有顶点（结点）的集合，用|V|表示顶点个数
边集E：所有边的集合，用|E|表示图G中边的条数
图的顶点集不能是空的，但是边集可以是空的，边两头一定都有顶点
无向图和有向图：E是无向边（边）的集合，(v,w)=(w,v)，则G是无向图；E是有向边（弧）的集合，弧记为<v,w>，v是弧尾，w是弧头，<v,w>!=<w,v>，则G是有向图
简单图和多重图：不存在重复边和顶点到自身的边的图是简单图，反之则为多重图。它们都分为有向和无向，我们主要讨论简单图。
度：

无向图：顶点v的度是依附于该点的边数TD(v)
有向图：入度是以顶点v为终点（指向v）的有向边数ID(v)，出度是以v为起点的有向边数OD(v)，度是出度入度之和TD=ID+OD

顶点之间关系：

路径：两点之间的线路的顶点序列，有向图要求考虑方向一致性
回路（环）：第一个顶点即最后一个顶点的路径
简单路径：不重复经过结点的路径
简单回路：头尾相同的简单路径
路径长度：路径上的边数
点到点的距离；u到v的最短路径若存在即为距离，不存在则为无穷

连通图：任意两点都连通（有路径）的无向图，则为连通图
强连通图：任意两点都强连通（有路径）的有向图，则为强连通图
子图：图的一部分（注意前提得是图）
连通分量：无向图的极大连通子图称为连通分量，极大连通子图是必须连通且包含尽可能多的顶点和边的子图（尽可能多连）
强连通分量：有向图的极大强连通子图称为强连通分量，极大强连通子图是必须强连通且包含尽可能多的顶点和边的子图
生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能少），不唯一
生成森林：将图的连通分量分别生成生成树
边的权：给边赋予的权值
带权图：边带有权的图是带权图，也称为网
带权路径长度：带权图中，一条路径上所有边的权值之和
其他图：

无向完全图：任何两点都存在边的无向图
有向完全图：任何两点都存在方向相反的两条弧的有向图
树：不存在回路且连通的无向图，即上一章的树，树属于图
森林：和树同理
有向树：一个顶点入度为0，其余顶点入度均为1的有向图

🔥图的存储结构

邻接矩阵法

矩阵的0和1代表两点之间的边存在与否
无向图的邻接矩阵是对称矩阵，可以进行压缩存储

#define MaxVertexNum 100      //顶点数目最大值
typedef struct{
  char Vex[MaxVertexNum];     //顶点表
  int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵，即边表，可以用char和bool减小空间
  int vexnum,arcnum;      //图的当前顶点树和边数/弧树
} MGraph;

无向图的顶点的度等于该点所在行或列的非零元素个数；有向图顶点出度是行非零元素个数，入度是列非零元素个数，度是两者之和。
对于带权图，只要把矩阵的0,1改成权值
邻接矩阵空间复杂度很高，适合用于存放边很密的图（空间利用率大），
Aⁿ[i][j]等于i到j顶点的长度为n的路径的数目，以此可以得到矩阵Aⁿ，如下：

邻接表法（顺序+链式）

邻接表法

如上图，^代表空，求顶点度只需要查找对应的链表即可
每个顶点链表的边顺序不唯一
邻接表找入边很不方便，需要遍历整个邻接表。删除边也很不方便，需要删两份数据

十字链表法

十字链表存有向图

如图，对于有向图，从一个顶点出发顺着橙色寻找可以找到所有指向它的弧，顺着绿色寻找可以找到所有指出的弧
十字链表找出入边都方便，但只能存有向图

邻接多重表

邻接多重表存无向图

类似十字链表，不会有冗余数据，删除方便
邻接多重表只能存无向图

比较

存储方式

🔥图的基本操作

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

🔥图的遍历

广度优先遍历（BFS）

BFS的思路和树的广度优先遍历一样，借助辅助队列进行

bool visited[MAX_VERTEX_NUM];   //访问标记数组，已经访问过的点设为true
void BFS(Graph G,int v){    //从顶点v出发广度优先遍历G
  visit(v);       //访问操作
  visited[v]=true;    //标记已访问点
  Enqueue(Q,v);       //顶点v入队Q
  while(!isEmpty(Q)){   //一直遍历直到队列为空
    DeQueue(Q,v);     //顶点v出列
    for(w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w))   //所有v的邻接点
      if(!visited[w]){    //访问未被访问过的邻接点
        visit(w);
        visited[w]=true;
        EnQueue[Q,w];
      }
  }
}
void BFSTraverse(Graph G){    //对G进行广度优先遍历
  for(i=0;i<G.vexnum;++i)
    visited[i]=false;     //访问标记数组的初始化
  InitQueue(Q);         //初始化辅助队列Q
  for(i=0;i<G.vexnum;++i)   //从0号顶点开始遍历
    if(!visited[i])     //对每个连通分量调用一次BFS
      BFS(G,i);       //对未被访问过的点进行BFS
}

BFSTraverse函数的存在保证非连通图也能遍历完全
广度优先生成树：根据上述的BFS操作，我们可以根据遍历的先后获取一个树，这是因为一次遍历过程中，每个顶点是通过哪个点遍历到是唯一的，这恰恰是树的结构。邻接表遍历过程不唯一，生成树也就不唯一
广度优先生成森林：非连通图可以多个广度优先生成树，构成森林就是广度优先生成森林。
有向图从不同点遍历，需要的次数可能不一样

深度优先遍历（DFS）

一条路走到底再回头，类似树的先根遍历，利用递归实现

bool visited[MAX_VERTEX_NUM];     //访问标记数组
void DFS(Graph G,int v){
  visit(v);
  visited[v]=true;        //已访问标记
  for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
    if(!visited[w]){      //w为u尚未访问的邻接顶点
      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);
}

和BFS一样，使用DFSTraverse防止非连通图遍历不全的问题
深度优先生成树：根据深度优先遍历获得的序列得到生成树，同广度优先生成树
深度优先生成森林：类似广度优先生成森林

🔥最小生成树

又名最小代价树，生成树中边权值之和最小的即为最小生成树。研究对象是带权连通的无向图

Prim（普里姆）算法

从某个顶点开始构建生成树，每次仅将代价（边的权值）最小的新顶点纳入生成树，直到所有顶点都纳入为止
同一顶点Prim算法可以得到不同的生成树
时间复杂度与顶点数相关，适用于边密的图

Kruskal（克鲁斯卡尔）算法

在所有边中每次选择一条权值最小的边，使这条边两头连通（已连通的就不选），直到所有结点连通
时间复杂度与边数相关，适合边稀疏的图

🔥最短路径

分为单源最短路径（特定一个点分别到多点）和各顶点间最短路径（任何两点之间）
单源最短路径方法：BFS算法（用于无权图），Dijkstra算法（带权、无权图）
各顶点间最短路径：Floyd算法（带权、无权图）

BFS算法

思路上就是修改BFS遍历算法，visit的具体操作是修改最短路径（d）和前驱结点（path）

void BFS_MIN_Distance(Graph G,int u){
  //d[i]表示u到i结点的最短路径
  for(i=0;i<G.vexnum;++i){
    d[i]=inf;       //初始化路径无穷大
    path[i]=-1;     //最短路径从哪个顶点来的（前驱结点）
  }
  d[u]=0;
  visited[u]=true;
  EnQueue(Q,u);
  while(!isEmpty(Q)){
    DeQueue(Q,u);
    for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
      if(!visited[w]){      //未访问过的邻接结点
        d[w]=d[u]+1;      //到这个点的路径等于到前驱结点路径+1
        path[w]=u;        //最短路径从u到w
        visited[w]=true;
        EnQueue(Q,w);     //w入队
      }
  }
}

BFS算法最短路径

如上图，要知道2如何到8最短，只要顺着表格中path从8按前驱结点依次找回到2，其间经过的结点也是路径上的结点，8的d也就是最短路径长度，最短路径就是2->6->7->8
对应广度优先生成树，我们可以看到每个结点所在的层数也能反映其最短路径：

Dijkstra算法

Dijkstra算法思路

如上图，以有向图为例，思路上是对于未确定最短路径的点不断更新其路径，需要n-1轮处理。思路和Prim算法的思路类似
得到如上结果，就可以顺着表格找寻点1到任何一点的最短路径及其长度
Dijkstra算法不适用有负权值的边的图

Floyd算法

利用动态规划思想，分阶段求解

对于n个顶点的图G，求任意一对顶点Vi->Vj之间的最短路径可分为如下几个阶段:
初始：不允许在其他顶点中转，最短路径是？
0：若允许在Vo中转，最短路径是？
1：若允许在Vo、V1中转，最短路径是？
2：若允许在Vo、V1、V2中转，最短路径是？
…
n-1：若允许在Vo、V1、V2. …..Vn-1中转，最短路径是?

Floyd算法

如此得到2个矩阵，可以通过左边这个矩阵查找最短距离，右边这个矩阵查找中转点，如果不止一个中转点，需要考虑端点到中转点的最短路径，就是多查找表格几次，直到路径是存在的。
代码上核心逻辑如下：

for(int k=0;k<n;k++){     //考虑Vk作为中转点
  for(int i=0;i<n;i++){   //遍历整个矩阵，i为行号，j为列号
    for(int j=0;j<n;j++){
      if(A[i][j]>A[i][k]+A[k][j]){  //考虑Vk作为中转点会不会缩短路径
        A[i][j]=A[i][k]+A[k][j];    //更新最短路径
        path[i][j]=k;         //中转点
      }
    }
  }
}