图

基本概念

定义

• 图G由顶点集V和边集E组成，记为G=(V,E)
• V(G)表示图G中顶点的有限非空集
• E(G)表示图G中顶点之间的关系集合
• 线性表可以是空表，树可以是空树，但图不可以是空

无向图

• 若E是无向边的有限集合时，则图G为无向图
• 边时顶点的无序对，记为(v,w)或(w,v).其中v,w是顶点。由于(v,w)=(w,v)，所以可以说顶点w和顶点v互为邻接
• 边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v,w相关联

有向图

• 若E时有向边的有限集合时，则图G为有向图
• 弧时顶点的有序对，记为<v,w>,其中v，w是顶点，v称为弧尾，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v
• 注意，<v,w> != <w,v>

简单图

• 不存在重复边
• 不存在顶点到自身的边

多重图

• 图G中某两个节点之间的边数多余一条又允许顶点通过一条边和自己关联，则G为多重图

顶点的度、入度和出度

无向图

• 顶点v的度时指依附于该顶点的边的条数，记为TD(v)
• 在具有n个顶点，e条边的无向图中，无向图的全部顶点的度等于边数的两倍

有向图

• 入度是以顶点v为终点的有向边的数目，记为ID(v)
• 出度时以顶点v为起点的有向边的数目，记为OD(v)
• 顶点v的度等于其入度和出度之和，即 $TD(v) = ID(v) + OD(v) $

顶点-顶点的关系描述

• 路径：顶点vp到顶点vq之间的一条路径是指顶点序列
• 回路：第一个顶点和最后一个顶点相同的路径称为回路或环
• 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径
• 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
• 路径长度：路径上边的数目
• 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若不存在路径，则记该距离为无穷
• 无向图中：若从顶点v到顶点w有路径存在，则称v和w时连通的
• 有向图中：若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点时强连通的

连通图和强连通图

• 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图
• 对于无向图，若图G是连通的，则最少有 $n-1$ 条边；非连通的，最多可能有 $ C_{n-1}^{2}$ 条边
• 如果任意一对顶点都是强连通的，则称为强连通图
• 对于有向图，如果是强连通图，则最少有n条边(形成回路)

子图

• 设有两个图 G = (V,E)和G’=(V’,E’)，若V’是V的子集且E’是E的子集，则G’是G的子图
• 若有满足V(G’) = V(G)的子图G’，则称其为G的生成子图
• 注意：并非任意挑选几个点，几条边都能构成子图

连通分量

• 无向图中的极大连通子图称为连通分量
• 子图必须连通，且饱含尽可能多的顶点和边

强连通分量

• 有向图中的极大强连通子图称为有向图的强连通分量
• 子图必须强连通，同时保留尽可能多的边

生成树

• 连通图的生成树是包含图中全部顶点的一个极小连通子图
• 边尽可能少，但要保持连通
• 若图中顶点数为n，则它的生成树含有n-1条边
• 对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

生成森林

• 在非连通图中，连通分量的生成树构成了非连通图的生成森林

边的权、带权图/网

• 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
• 带权图/网：边上带有权值的图称为带权图，也称为网
• 带权路径长度：当图时带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

几种特殊形态的图

• 无向完全图：无向图中任意两个顶点之间都存在边
• 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
• 稀疏图：边数很少的图
• 稠密图：边数很多的图
• 树：不存在回路，且连通的无向图
• 有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图
• n个顶点的树，必有n-1条边；n个顶点的图，若|E| > n - 1,则一定有回路

邻接矩阵法

定义

• 节点数为n的图G=(V,E)的邻接矩阵A是 $n*n$，将G的顶点编号为 $v_1,v_2,\dots,v_n$,则 如果不是E(G)中的边时，A[i][j] = 0， 否则A[i][j] = 1

无向图

• 第i个节点的度=第i行(或第i列)的非零元素个数

有向图

• 第i个节点的出度=第i行的非零元素个数
• 第i个节点的入度=第i列的非零元素个数
• 第i个节点的度=第i行，第i列的非零元素个数之和

邻接表法

• 邻接矩阵使用数组实现顺序存储，不适合稀疏矩阵

定义

• 每个节点保存孩子链表头指针
• 边节点的数量是2|E|，整体空间复杂度是O(|V|+2|E|)
• 只要确定了顶点编号，图的邻接矩阵表示方法唯一，图的邻接表表示方法不唯一

十字链表、邻接多重表

• 十字链表存储有向图
• 邻接多重表存储无向图

十字链表

• 空间复杂度O(|V|+|E|)
• 顺着绿色线路可以找到顶点的所有出边
• 顺着橙色线路可以找到顶点的所有入边

邻接多重表

• 邻接表每条边对应两份冗余信息，删除顶点，删除边等操作时间复杂度高
• 邻接矩阵空间复杂度高

• 空间复杂度O(|V|+|E|)
• 删除边，删除顶点操作方便

图基本操作

• Adjacent(G,x,y) 判断图是否存在边<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的第一个邻接点，不存在则返回-1
• NextNeighbor(G,x,y) 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个临界点号
• GetEdgeValue(G,x,y) 获取图G中边(x,y)或<x,y>对应的权值
• SetEdgeValue(G,x,y,v) 设置图G中边(x,y)或<x,y>对应的权值为v

只针对邻接矩阵和邻接表

广度优先搜索(BFS)

• 类似于树的层序遍历
• 每个节点，先把邻接节点遍历完之后，再进入下一层遍历
• 树不存在回路，搜索相邻节点时，不可能搜到已经访问过的节点
• 图搜索时，可能搜到之前访问过的顶点

代码实现

• 找到与一个顶点邻接的所有顶点
• 标记哪些顶点呗访问过
• 需要一个辅助队列

// 广度优先遍历
// 从顶点v出发，广度优先遍历图G
void BFS(Graph G, int v) {
    // 访问初始顶点v
    visit(v);
    // 对v做已访问标记
    visited[v] = TRUE;
    // 顶点v入队列Q
    Enqueue(Q, v);
    
    while (!isEmpty(Q)) {
        // 顶点v出队列
        DeQueue(Q, v);
        // 检测v所有邻接点
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            // w为v的尚未访问的邻接顶点
            if (!visited[w]) {
                // 访问顶点w
                visit(w);
                // 对w做已访问标记
                visited[w] = TRUE;
                // 顶点w入队列
                EnQueue(Q, w);
            } // if
        } // while
    }
}

• 同一个图的邻接矩阵表示方法唯一，因此广度优先搜索序列唯一
• 同一个图的邻接表表示方法不唯一，因此广度优先搜索序列不唯一

算法存在的问题及解决方案

• 如果是非连通图，则无法遍历完所有节点

• 空间复杂度：最坏情况，O(|V|)
• 邻接矩阵时间复杂度:O($|V|^2$)
• 邻接表时间复杂度:O(|V|+|E|)

图的深度优先遍历(DFS)

• 类似于树的前/中/后序遍历
• 尽可能往深处走，遍历完一个分支后，再回到上一个节点遍历其他分支
• 深度优先用递归实现，广度优先用队列实现

存在的问题和解决方案

• 如果时非连通图，则无法遍历完所有节点

• 空间复杂度：最坏情况O(|V|),最好情况O(1)
• 邻接矩阵时间复杂度: O($|V|^2$)
• 邻接表时间复杂度：O(|V|+|E|)

最小生成树

生成树

• 连通图的生成树是包含图中全部顶点的一个极小连通子图
• 若图中顶点数为n，则它的生成树含有n-1条边
• 对于生成树而言，若砍去它的一条边，会变成非连通图，若加上一条边会形成一个回路

最小生成树

• 对于一个带权连通无向图，生成树不同，每棵树的权也可能不同
• 设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则称T为G的最小生成树
• 最小生成树可能有多个，但边的权值之和总是唯一最小的
• 最小生成树的边数 = 顶点数 - 1
• 砍掉一条则不连通，增加一条边则会出现回路
• 如果一个连通图本身就是一棵树，则其最小生成树就是它本省
• 只有连通图才有生成树，非连通图只有生成森林

Prim算法(普里姆)

思想

• 从某一个顶点开始构建生成树
• 每次讲代价最小的新顶点纳入生成树，直到所有的顶点都纳入为止
• 时间复杂度O($|V|^2|$), 适用于边稠密图

数据结构

实现步骤

• 从V0开始，总共需要n-1轮处理
• 循环遍历所有节点，找到lowCost最低的且还没有加入树的顶点
• 再次循环遍历，更新还没加入的各个顶点的lowCost值
• 重复上面的步骤，直到所有节点都加入树，生成的树为最小生成树

Kruskal算法(克鲁斯卡尔)

算法思想

• 每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)
• 直到所有节点都连通
• 时间复杂度O($|E|\log_2|E|$)

数据结构

• 让各条边按照权值顺序排序

实现步骤

• 共执行e轮，每轮判断两个顶点是否属于同一集合
• 检查第e条边的两个顶点是否连通(是否属于同一集合)
• 若不连通，则连起来
• 若连通，则不操作
• 重复上面步骤直到所有边都被遍历过

最短路径问题-BFS算法

• 无权图可以视为一种特殊的带权图，只是每条边的权值都为1
• BFS一般只适用于无权图的最短路径问题

代码实现

• d数组表示u到各个节点的最短路径
• path数组表示该节点回到u节点的最短前驱节点
• 由此生成的生成树同时也反映了起点到任意节点的距离

最短路径-Dijkstra算法

• BFS无法计算带权路径长度
• Dijkstra不适用于带负权值的带权图

算法思想

• 初始：从V0开始，初始化三个数组信息
• 循环遍历所有节点，找到还没有确定最短路径切dist最小的顶点Vi，令final[i] = true
• 检查所有邻接自Vi的顶点，如果final的值为false，则更新dist和path值
• 重复上述步骤，直到所有节点的final都标记为true

实现思路

• final[0]=true;dist[0]=0,path[0]=-1;
• 遍历所有顶点，找到还没确定最短路径且dist最小的顶点Vi，令final[i]=true
• 检查所有邻接自Vi的顶点，如果final[j] == false && dist[i] + arcsi < dist[j]，则令dist[j]=dist[i]+arcsi; path[j]=i
• 注：arcsi表示从Vi到Vj的弧的权值

时间复杂度为O(n2)即O(|V|2)

最短路径-Floyd算法

算法思想

• 求出每一对顶点之间的最短路径
• 使用动态规划思想

思考方法如下

• 初始：不允许在其他顶点中转，最短路径是？
• 0: 允许在V0中转，最短路径是？
• …
• n-1: 允许在V0,V1,V2,..,Vn-1中转，最短路径是？

实现步骤

代码实现

// ... 准备工作，根据图的信息初始化矩阵 A 和 path，入上图
for(int k = 0; k < n; k++) {
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++){
           if(A[i][j] > A[i][k] + A[k][j]) {
               A[i][j] = A[i][k] + A[k][j];
               path[i][j] = k;
           }
       }
   }
}

tips:

• Floyd算法可用于负权图
• 不能解决带有负权回路的图，这种图可能没有最短路径

有向无环图的描述表达式

定义

• 若一个有向图中不存在环，则称为有向无环图

解题方法

• 把各个操作数不重复排成一排
• 标出各个运算符的生效顺序(先后顺序有点出入无所谓)
• 按顺序加入运算符，注意分层
• 从底向上层逐层检查同层的运算符是否可以合体

拓扑排序

• 每个顶点只出现一次
• 顶点在A的序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径
• 有向无环图

或者

• 拓扑排序是对有向无环图顶点的一种排序
• 它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面

实现

• 从AOV网中，选择一个没有前驱的顶点并输出
• 从网中删除该顶点和所有以它为起点的有向边
• 重复前面的步骤直到当前AOV网为空或当前网中不存在无前驱的顶点为止

代码实现

逆拓扑排序

• 从AOV网中选择一个没有后继的顶点并输出
• 从网中删除该顶点和所有以它为终点的有向边
• 重复上面的步骤直到AOV网为空