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

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

  • 动态网站开发技术asp、asp.net、php、jsp比较

    asp、asp.net、php、jsp技术简介 ASP 全称为Active Server Pages(中文译名为活动服务器页面),是微软公司推出的用于Web应用服务的一种编程技术.采用的脚本语言: VBScript 和JavaScript。 ASP.NET 微软公司很快公布了其宏伟的“Windows.NET”计划,发布了成为下一代网络服务框架的NGWS,同时…

    2018年3月15日
    2.7K0
  • python属于编译型还是解释型的语言?python是哪一种类型的编译语言

    Python先把代码编译成字节码,再对字节码解释执行。 java   编译型(请求次数多)+解释型(请求次数少) 解释性语言定义: 程序不需要编译,在运行程序的时候才翻译,每个语句都是执行的时候才翻译。这样解释性语言每执行一次就需要逐行翻译一次,效率比较低。 现代解释性语言通常把源程序编译成中间代码,然后用解释器把中间代码一条条翻译成目标机器代码,一条条执行…

    2023年2月26日
    3.1K0
  • Java课程设计报告-记事本源代码有流程图

    Java课程设计报告 题 目:简单记事本程序的设计年级专业:计算机科学与技术  软件工程学 号:学生姓名:指导老师: 目    录 摘要… 1 前言… 2 1需求分析… 2 1.1需求分析… 2 1.2功能设计… 3 2.概要设计… 3 2.1程序设计思路… 3 2.2程序运…

    2019年10月4日
    2.7K0
  • Vim编辑器常用命令大全

    编辑和保存文件 vim filename为编辑一个文件,若此文件不存在,则Vim会以filename为名创建这个文件。 启动Vim时自动处于命令模式,按I键可以进入插入模式,这个命令用于在当前光标所在处插入字符。 保存和退出 命令 操作 :w 保存文件 :w filename 另存为filename :q 退出Vim :q! 强制退出Vim,用于放弃保存修改…

    2022年9月22日
    1.4K0
  • pageEncoding和contentType编码作用和区别详解

    pageEncoding和contentType都用于定义字符编码,两者有什么区别?相信不少初学者都会有疑惑,今天中国网页设计给大家详细解读两者的区别,pageEncoding和contentType都在什么时候起作用。

    2022年12月1日
    1.1K0
  • input file获取文件路径时无法获取正确的路径

    页面有一个input file服务器控件,一个div,div是image标签的容器,当点击input file的值改变,我们往div里追加image标签;但当通过js的onchange事件动态获取input file 的路径的时候,发现console.log(path)打印出的路径是被浏览器屏蔽的, 例如:C:\fakepath\file.jpg 这是由于浏…

    2019年11月13日
    6.9K0

发表回复

登录后才能评论