本文共 3459 字,大约阅读时间需要 11 分钟。
图
1.图简述
- 图由顶点(vertex)和边(edge)组成,通常表示为G=(V,E)
- G表示一个图,V是顶点集,E是边集;
- 顶点集V有穷且非空;
- 任意两个顶点之间都可以用边来表示它们之间的关系,边集E可以是空的;
2.应用举例
图结构的应用极其广泛:
3.图的一些相关概念
3.1 有向图
有向图的边是有明确方向的;
有向无环图:如果一个有向图,从任意顶点出发无法经过若干条边回到该顶点,那么它就是一个有向无环图。
3.2 出度和入度
出度 入度适用于有向图;
出度(out-degree):
- 如果一个顶点的出度为x,是指有x条边以该顶点为起点
入度(in-degree):
- 如果一个顶点的入度为x,是指有x条边以该顶点为终点
3.3 无向图
无向图的边是无方向的;
3.4 无向完全图
无向完全图的任意两个顶点之间都存在边;
n个顶点的无向完全图由n(n-1)/2条边;即(n-1) + (n-2) + (n-3) + … + 3 + 2 + 1
3.5 有向完全图
有向完全图的任意两个顶点之间都存在方向相反的两条边;
n个顶点的有向完全图有n(n-1)条边;
- 稠密图(Dense Graph):边数接近于或等于完全图;
- 稀疏图(Sparse Graph):边数远远少于完全图;
3.6 有权图
有权图的边可以拥有权值。
3.7 连通图
- 如果顶点x和y之间存在可相互抵达的路径(直接或间接的路径),则称x和y是连通的;
3.8 连通分量
- 连通分量:无向图的极大连通子图
- 连通图只有一个连通分量,即其本身;非连通的无向图有多个连通分量;
- 举例:下面的无向图有3个连通分量
3.9 强连通图
- 如果有向图G中任意两个顶点都是连通的,则称G为强连通图;
3.10 强联通分量
- 强连通分量:有向图的极大强连通子图
- 强连通图只有一个强连通分量,即其自身;非强梨连通的有向图有多个强连通分量;
4.图的实现
图有2种常见的实现方案:
- 邻接矩阵(Adjacency Matrix)
- 邻接表(Adjacency List)
4.1 邻接矩阵
邻接矩阵的存放方式:
4.2 邻接表
4.3 邻接表-有权图
5.图的遍历
从图中某一顶点出发访问图中其余顶点,且每一个顶点仅被访问一次;
图有2种常见的遍历方式(有向图、无向图都适用);
- 广度优先搜索(BFS),又称为宽度优先搜索、横向优先搜索
- 深度优先搜索(DFSS)
5.1 广度优先搜索(BFS)
之前所学的二叉树层序遍历就是一种广度优先搜索
5.2 深度优先搜索(DFS)
之前学的二叉树前序遍历就是一种深度优先搜索
6.AOV网(Activity On Vertex Network)
子工程之间可能存在一定的先后顺序,即某些子工程必须在其他的一些子工程完成后才能开始
- 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,子工程被称为活动(Activity)
- 标准的AOV网必须是一个有向五环图
6.1 拓扑排序
- 将AOV网中所有活动排成一个序列,使得每个活动的前驱活动都排在该活动的前面。
- 比如上图的拓扑排序结果是A B C D E F
拓扑排序的算法流程:
- 假设L是存放拓扑排序结果的列表
- 把所有入度为0的顶点放入L中,然后把这些顶点从图中去掉;
- 重复上述操作,直到找不到入度为0的顶点
- 如果此时L中的元素个数和顶点个数总数相同,说明拓扑排序完成
- 如果此时L中的元素个数小于顶点总数,说明原图中存在环,无法进行拓扑排序
6.2 AOV有关的题目
Leetcode 课程表I
7 生成树
7.1 生成树
生成树,也称为支撑树
- 连通图的极小连通子图,它含有图中全部的n个顶点,恰好只有n-1条边;
7.2 最小生成树
最小生成树:
- 也被称为最小权重树
- 是所有生成树中,总权值最小的那树
- 适用于有权的连通图(无向)
最小生成树在许多领域都有重要的作用,例如
- 要在n个城市之间铺设光缆,使它们都可以通信;
- 铺设光缆的费用很高,且各个城市之间因为距离不同等因素,铺设光缆的费用也不同;
- 那么如何使铺设光缆的总费用最低?
7.3 求最小生成树
求最小生成树的2个经典算法:
- Prim(普利姆算法)
- Kurskal(克鲁斯克尔算法)
求最短路径算法
- Dijkstra(迪杰斯特拉算法);
- Floyd(弗洛伊德算法)
- 最小生成树是用最小代价遍历整个图中所有顶点,所有的权值和最小;而最短路径只是保证出发点到终点的路径和最小,不一定要经过所有顶点。
- 最小生成树是一群点(所有点)的路径代价和最小,是一个n-1条边的数,最短路径是从一个点到另外一个点的最短路径;
7.3.1 Prim普利姆算法
从单一顶点开始,普利姆算法按照如下步骤逐步扩大树中所包含的顶点的数目,直到遍及连通图中的所有顶点
- 输入:一个加权连通图,其中顶点集合为V,边集合为E;
- 初始化:Vnew={x}, 其中x为集合V中的任一节点(起始点),Enew={};
- 重复以下操作,直到Vnew=V;
- 在集合E中选取权值最小的边(u,v),其中u为集合Vnew中的元素,而v不是;
- 将v加入集合Vnew中 ,将(u,v)加入集合Enew中
- 输出:使用集合Vnew和Enew来描述所得到的最小生成树;
7.3.2 Kruskal克鲁斯卡尔算法
Prim算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。同样的思路,也可以直接就以边来构建生成树也是很自然的想法,只不过 构建的时候要考虑是否会形成环路而已。
7.4 求A和B两点之间的最短路径
最短路径是指两顶点之间权值之和最小的路径(有向图、无向图均适用,不能有负权环)
求解最短路径的经典算法:
7.4.1 Dijkstra算法
Dijkstra属于单源最短路径算法,用于计算一个顶点到其它所有顶点的最短路径;
- 使用前提:不能有负权边;
- 时间复杂度:可优化至O(ElogV) E是边数量 V是节点数
Dijkstra-等价思考
Dijkstra的原理其实跟生活 中的一些自然现象完全一样:
- 把每一个顶点想象成一块小石头;
- 把每一条边想象成一条绳子,每一条绳子都连接着2块小石头,边的权值就是绳子的长度;
- 将小石头和绳子平放在一张桌子上
- 接下来想象一下,手拽着小石头A,慢慢地向上提起来,远离桌面
- B,D,C,E会依次离开桌面
- 最后绷直的绳子就是A到其他小石头的最短路径
Dijkstra算法步骤:
- 初始化时,S中只含有源节点;U为其他结点;计算S中的源节点到U中其他结点的路径;
- 之后从U中挑选一个距离最小的顶点k加入到S中;(该选定的距离就是v到k的最短路径长度);
- 以k为新考虑的中间点,更新源节点v到顶点u的距离,若短则更新
- 重复步骤,直到所有顶点都包含在S中了。
7.4.2 Floyd算法
Floyd属于多源最短路径算法,能够求出任意两个顶点之间的最短路径
- 支持负权边;
- 时间复杂度为O(V^3) 效率比执行V次Dijkstra算法要好(V表示顶点数量)
算法原理:
-
从任意顶点i到任意顶点j的最短路径不外乎两种可能
-
假设dist(i,j)为顶点i到顶点j的最短路径的距离
-
对于每一个顶点k,检查dist(i,k)+dist(k,j)<dist(i,j)是否成立
- 如果成立,证明i到k再到j的路径比i直接到j的路径短,设置dist(i,j)=dist(i,k)+dist(k,j)
- 当我们遍历完所有结点k,dist(i,j)中记录的便是i到j的最短路径的距离
-
时间复杂度为O(V^3) 效率比执行V次Dijkstra算法要好(V表示顶点数量)
算法原理:
-
从任意顶点i到任意顶点j的最短路径不外乎两种可能
-
假设dist(i,j)为顶点i到顶点j的最短路径的距离
-
对于每一个顶点k,检查dist(i,k)+dist(k,j)<dist(i,j)是否成立
- 如果成立,证明i到k再到j的路径比i直接到j的路径短,设置dist(i,j)=dist(i,k)+dist(k,j)
- 当我们遍历完所有结点k,dist(i,j)中记录的便是i到j的最短路径的距离
转载地址:http://jcwdf.baihongyu.com/