图的全部知识点、考点梳理-数据结构

讲解了图的15条相关定义,图的表示方法、最小生成树、普里姆(Prim)算法、克鲁斯卡尔(Kruskal)算法、最短路径、迪杰斯特拉算法、弗洛伊德算法、拓扑排序、AOE 网(关键路径),邻接矩阵和邻接表的比较。

6 图

6.1 基本定义

  1. 图: 图(graph) 是由两个集合 V 和 E 组成。 V 是顶点的有穷非空集合, E 是 V 中顶点偶对(边)D的有穷集合
  2. 无向完全图:具有 n(n-1)/2 条边,则为无向完全图
  3. 有向完全图: n(n-1) 条边,则为有向完全图
  4. 度:顶点 V 相关联的边的数目
  5. 入度(有向):以顶点 V 为头的弧的数目
  6. 出度(有向):以顶点 V 为尾的弧的数目
  7. 路径和路径长度: 从顶点 V 到 顶点 S 的一系列边为路径,路径长度为边 / 弧的数目
  8. 回路或环:第一个顶点到最后一个顶点相同的路径称为回路或环
  9. 简单路径:序列中顶点不重复出现的路径称为简单路径
  10. 简单回路(简单环):除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路
  11. 连通:在无向图 G 中,从顶点 V 到顶点 S 有路径,则称 V 和 S 是连通的
  12. 连通图:如果图中任意两个顶点都连通,则称为连通图
  13. 连通分量:无向图中的极大连通子图
  14. 强连通分量:有向图中极大强连通子图称为强连通分量
  15. 强连通图:对每一对 Vi,Vj,从 Vi 到 Vj 和从 Vj 和 Vi 都存在路径,则G为强连通图

6.2 图的表示方法

6.2.1 邻接矩阵

邻接矩阵:是表示顶点之间相邻关系的矩阵,设 G(V, E) 是具有n个顶点的图,则 G 的邻接矩阵具有如下性质
A[i][j] = 1 存在边, 0 则不存在邻接矩阵是一个二维数组,通过 ij 代表两个顶点的边,所有二维数组对角线全为0,若在有向图中,行为出度,列为入度

6.2.2 邻接表

  1. 无向图结点
typedef struct node {
    int data,
    struct node * next;
}
  1. 有向图节点
typedef struct node {
    int data,
    // 出度
    struct node *next;
    // 入度
    struct node *prev;
}

6.3 最小生成树

6.3.1 普里姆(Prim)算法

选择一条权值最小的边,从权值最下边入度的结点相邻结点边中选最小边,直到完成

6.3.2 克鲁斯卡尔(Kruskal)算法

选择两个结点,其边权值最小。重复完成

6.3.3 最短路径

图的全部知识点、考点梳理-数据结构

6.3.3.1 迪杰斯特拉算法

求解过程

对于有向图,分为两组:已求出最短路径的重点集合,尚未求出最短路径终点集合

源点 终点 最短路径 路径长度
v0 v2 (v0, v2) 10
v0 v4 (v0, v4) 30
v0 v3 (v0, v4, v3) 50
v0 v5 (v0, v4, v3, v5) 60
v0 v1

根据算法,先求出源点及源点相邻节点的路径,并记录下来。
依次进行扩展,若扩展过程中,原有路径大于扩展路径,并更新。类似于计网的路由

6.3.3.2 弗洛伊德算法

将 Vi 到 Vj 的最短路径长度初始化,然后每次在两者之间加入顶点 V0,比较(Vi, Vj) 和 (Vi, V0, Vj) 的路径长度,
取其较短者作为 Vi 到 Vj 的中间顶点的最短路径(寻找相邻结点最短结点)

6.4 拓扑排序

在有向图中选一个无前驱的顶点且数除,从图中删除该顶点和所有以它为尾的弧,继续重复,直到不存在前驱顶点。

6.5 AOE 网(关键路径)

AOV 相对应的就是 AOE 网。即以边表示活动的网。AOE 是一个带权的有向无环图。顶点表示事件,弧表活动,权表活动持续时间。

 

图的全部知识点、考点梳理-数据结构

  1. 事件最早发生时间

进入事件 Vi 的每一个活动都结束,Vi 才可以发生。 Ve(0) = 0, Ve(i) = Max{Ve(k) + w_{k,i}}

  1. 事件最迟发生时间

事件 Vi 发生不得延误 Vi的每一后继事件的最迟发生时间。
Vi 的最迟发生时间不得迟于其后继事件 V_k 的最迟发生事件减去活动<V_iV_k>的持续时间
Vl(i) = Min{Vl(k) – w_{i,k}}

  1. 活动最早开始时间

只有事件 Vj 发生了,活动 ai 才能开始。所以活动 ai 的最早事件等于事件 Vj 的最早发生时间: e(i) Ve(j)

  1. 活动最晚开始时间

活动 ai 的开始时间需保证不延误事件 Vk 的最迟发生事件。所以活动 ai 的最晚开始时间 l(i) 等于时间 Vk 的最迟发生时间
Vl(k) 减去活动 ai 的持续时间 w_{j,k}: l(i) = Vl(k) – w-{j, k}

最早发生时间: ve(i)
ve(0) = 0
ve(1) = Max{ve(0) + w0,1} = 6
ve(2) = Max{ve(0) + w0,2} = 4
ve(3) = Max{ve(0) + w0,3} = 5
ve(4) = Max{ve(1) + w1,4, ve(2)+w2,4} =7
ve(5) = Max{ve(3) + w3,5} = 7
ve(6) = Max{ve(4) + w4,6} = 16
ve(7) = Max{ve(4) + w4,7, ve(5)+w5,7} = 14
ve(8) = Max{ve(6) + w6,8, ve(7)+w7,8} = 18
最迟发生时间vl(i)
vl(8) = ve(8) = 18
vl(7) = Min{vl(8) - w7,8} = 14
vl(6) = Min{vl(8) - w6,8} = 16
vl(5) = Min{vl(7) - w5,7} = 10
vl(4) = Min{vl(6) - w4,6, vl(7) - w4,7} = 7
vl(3) = Min{vl(5) - w3,5} = 8
vl(2) = Min{vl(4) - w2,4} = 6
vl(1) = Min{vl(4) - w1,4} = 6
vl(0) = Min{vl(1) - w0,1, vl(2) - w0,2, vl(3) - w0,3} = 0
活动最早时间 e(i)
e(a1) = ve(0) = 0
e(a2) = ve(0) = 0
e(a3) = ve(0) = 0;
e(a4) = ve(1) = 6;
e(a5) = ve(2) = 4;
e(a6) = ve(3) = 5;
e(a7) = ve(4) = 7;
e(a8) = ve(4) = 7;
e(a9) = ve(5) = 7;
e(a10) = ve(6) = 16;
e(a11) = ve(7) = 14;
活动最迟开始时间 l(i)
l(a11) = vl(8) - w7,8 = 14
l(a10) = vl(8) - w6,8 = 16
l(a9) = vl(7) - w5,7 = 10
l(a8) = vl(7) - w4,7 = 7
l(a7) = vl(6) - w4,6 = 7
l(a6) = vl(5) - w3,5 = 8
l(a5) = vl(4) - w2,4 = 6
l(a4) = vl(4) - w1,4 = 6
l(a3) = vl(3) - w0,3 = 3
l(a2) = vl(2) - w0,2 = 2
l(a1) = vl(1) - w0,1 = 0

邻接矩阵和邻接表的比较

项目 邻接矩阵 邻接矩阵 邻接表 邻接表
无向图 有向图 无向图 有向图
顶点表节点个数 n n n n
边节点个数 邻接矩阵堆成可压缩到 n^2 / 2 n^2 2e e
求某个顶点 v1 的度 扫描邻接矩阵中序号i对应的行 O(1) 求出度:扫描邻接矩阵的一行 O(n). 求入度:扫描矩阵的一列 扫描 vi 的边表,最坏O(n) 求出度:扫描vi的边表最坏O(n)。入度:按顶点表顺序扫描所有边表O(n+e)
求边的数目 扫描邻接矩阵O(n^2) 扫描邻接矩阵O(n^2) 按顶点表舒徐扫描所有边表,O(n+2e) 按顶点表顺序扫描所有边表O(n+e)
判定边 (vi, vj) 是否存在 直接检查邻接矩阵A[i][j]元素的值 直接检查邻接矩阵A[i][j]元素的值 扫描Vi的边表,最坏情况O(n) 扫描Vi的边表,最坏情况O(n)

 

125jz网原创文章。发布者:江山如画,转载请注明出处:http://www.125jz.com/8814.html

(0)
江山如画的头像江山如画管理团队
上一篇 2020年10月13日 下午8:44
下一篇 2020年10月16日 下午4:29

99%的人还看了以下文章

  • python 实战-逢7 过游戏的实现

    不知道你有没有玩过“逢 7 过”的游戏,游戏规则很简单: 几个人轮流报数,凡遇到 7 的倍数,或含 7 的数字就要跳过,否则就算失败。 今天我们就用 Python 来打印 1 到 100 之间,所有满足条件的数字。 知识点 Python 开发环境 int 类型 变量 运算符 while 循环 条件判断 💡提示: 开发中,我们经常要先构思框架,…

    2022年2月2日
    3.3K0
  • 第三课:第一个maven项目Hello Maven

    一、Maven的简单使用 1.1、Maven项目的目录约定 MavenProjectRoot(项目根目录)|—-src|     |—-main|     |         |—-java ——存放项目的.java文件|     |         |—-resources ——存放项目资源文件,如sprin…

    2023年1月27日 编程开发
    5960
  • object…object和object[]…object的区别

    object…object public int update(String sql, Object… params) throws SQLException { Connection conn = this.prepareConnection(); return this.update(conn, true, sql, params); }…

    2019年11月19日
    2.0K0
  • 单元测试工具JUnit介绍及使用,单元测试快速入门教程五

    JUnit是一个开放源代码的测试框架,用在编写和运行可重复的测试脚本之上,是用于Java语言编写的面向对象程序的单元测试工具。JUnit框架功能强大,目前已经成为Java单元测试的事实标准,基本上能满足日常的测试要求。 1.Junit主要特性 (1)可以将测试代码和产品代码分别开发,便于管理。 (2)针对某一个类的测试代码,以较少的改动便可以应用    另一…

    2018年4月18日 编程开发
    4.7K0
  • 人工智能基础测试

    1、 print(“Hi”) print(“3*6”) 程序输出结果:(5分) A、 Hi 18 B、 Hi 3*6 C、 Hi 3*6 D、 Hi 18 2、人工智能的概念最早是由哪一位科学家提出来的()(5分) A、 麦卡锡 B、 图灵 C、 冯·诺依曼 D、 马明斯基 3、下列关于人工智能的叙述不正确的有…

    2023年6月2日
    6540
  • 别再浪费时间了!分享一个学习Python的正确指南!

    Python是一门新手友好、功能强大、高效灵活的编程语言。 然而很多同学在学习过程中,并没有找到正确的方式,这样不仅浪费了大量的时间与精力,也对学习的兴趣有一定打击。 125网页设计整理了一些初学者学习的几大误区分享给大家,帮助同学们更好地学习Python。 急于求成 很多对学习Python有兴趣的同学们,可能在刚开始学习时没有找准学习方式。大家只是一味地买…

    2022年8月13日
    1.0K0

发表回复

登录后才能评论