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

讲解了图的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%的人还看了以下文章

  • java WEB编程技术上机练习一:

    jsp运行环境的搭建(jdk+TOMCAT)、编写JSP页面,配置虚拟目录并访问、熟悉MYECLIPSE的使用,包括项目的部署及运行。

    2018年8月29日
    4.9K1
  • Undefined variable: file python3不再支持file函数

    python处理文件时,使用file函数,提示错误:Undefined variable: file 反复查看语法,没有问题啊,最后查找到原因: python3不再支持file函数 替代方法:可以用open代替file 函数。

    2019年3月29日
    7.3K0
  • 手机上可以python编程吗,手机如何开发python

    想在手机上编写python代码? python语言应用很广泛,很多小伙伴想利用空闲时间学习Python,但是有时候身边没有电脑,今天就给大家分享两种手机编写运行python的方法,让你可以直接在自己的手机上做python开发学习。 一、直接在线编写运行(免安装) 手机通过浏览器打开 https://c.runoob.com/compile/9/ 推荐:★★★…

    2022年3月16日 编程开发
    4.7K0
  • Python 函数练习-生成指定长度的随机字符串(包含大小写字母,及数字)

    函数在 Python 中,可以通过 def 关键字定义函数,如下代码所示: import random import string def random_str(n): “”” 生成指定 n 长度的随机字符串 “”” s = string.ascii_letters + string.ascii_uppercase + string.digits retur…

    2022年2月3日
    1.7K0
  • Windows10+IIS+PHP7+MySQL5.7环境搭建

    IIS配置 本次搭建使用的系统是Windows7,Windows8,10与此类似。 开启IIS 开始–>控制面板–>程序和功能,点击左边栏的开启或关闭Windows功能,如图: 选择Internet信息服务并选择里面的CGI。打开浏览器,输入localhost或127.0.0.1,可以正常打开网页则说明开启成功。 新建站点…

    2021年8月14日 编程开发
    9580
  • 上机实战六 Servlet的开发 

      建议学时:6 2学时 一、编写Servlet,FirstServlet.java 通过URL访问该Servlet,显示这是我的第一个Servlet。 二、使用servlet实现求圆的面积,在r4.jsp页面提交表单,servlet负责接收用户请求、计算并显示圆的面积。 具体页面效果如下: 三、jsp+javabean+servlet实现求三角形的面积和周…

    2018年11月13日
    7.2K0

发表回复

登录后才能评论