前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【自考】数据结构第五章图,期末不挂科指南,第9篇

【自考】数据结构第五章图,期末不挂科指南,第9篇

作者头像
梦想橡皮擦
发布2020-01-13 17:23:33
5200
发布2020-01-13 17:23:33
举报
文章被收录于专栏:Python3爬虫100例教程

图的基本概念

首先,你要明确图是什么样子的,就是下面这个样子的

数据结构自考
数据结构自考

图的定义与术语

有向图和无向图

直接对比图就可以看出来,有向图和无向图的区别了,这个没有什么难的。

数据结构自考 数据结构自考
数据结构自考 数据结构自考

有向图和无向图的表示法有略微的区别,注意看 G1有箭头,有向图,表示方法是 V={V~0~,V~1~,V~2~,V~3~} E = {<V~0~,V~1~>,<V~1~,V~2~>,<V~1~,V~0~>,<V~2~,V~0~>,<V~2~,V~3~>} G2无箭头,无向图,表示方法是 V={V~0~,V~1~,V~2~,V~3~} E = {(V~0~,V~1~),(V~1~,V~2~),(V~0~,V~2~),(V~2~,V~3~)}

弧、弧头、弧尾:有向图的边称为弧。无向图叫做边。有序偶对<v,w>表示有向图从v到w的一条弧,v称为弧尾或始点,w称为弧头或终点。

任何两点之间都有边的无向图称为无向完全图。 任何两点之间都有弧的有向图称为有向完全图。

权、带权图:图的边附带数值,这个数值叫权。每条边都带权的图称为带权图。

顶点的度、入度、出度:

  1. 无向图中顶点v的度是与该顶点相关联的边的数目,记为D(v)。
  2. 有向图中,把以顶点v为终点的弧的数目称为v的入度,记为ID(v);把以顶点v为始点的弧的数目称为v的出度,记为OD(v)。有向图顶点v的度为入度和出度之和,即D(v) = ID(v)+ OD(v)。

简单路径、回路、简单回路:序列中顶点不重复出现的路径称为简单路径。第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外,其余顶点不重复的回路,称为简单回路或简单环。

下面还有一些需要了解的术语

连通、连通图、连通分量、极大连通子图、强连通、强连通图、强连通分量、生成树、生成森林

如果精力足够,都看看吧

图的存储结构

图的存储结构有很多中,例如 邻接矩阵、邻接表、十字链表和邻接多重表

邻接矩阵

矩阵中标记1,有边,标记0,没有边

注意:无向图的邻接矩阵是一个对称矩阵

数据结构自考 数据结构自考 数据结构自考
数据结构自考 数据结构自考 数据结构自考

带权图的邻接矩阵

数据结构自考 数据结构自考 数据结构自考
数据结构自考 数据结构自考 数据结构自考

邻接矩阵自考/期末考试真题

数据结构自考
数据结构自考

尝试着,画出无向图吧!

邻接表

邻接表是顺序存储与链式存储相结合的存储方法。

下图中,左侧是无向图,右侧是该无向图的邻接表,注意看,该符号,表示结束,没有连接的顶点了。

数据结构自考
数据结构自考

有向图及其类似,这个就不在做图扩充

图的遍历

图的遍历是指从图的某个顶点出发,系统地访问图的每个顶点,并且每个顶点只被访问一次。 遍历图的基本方法有两种:深度优先搜索和广度优先搜索。

连通图的深度优先搜索

深度优先,就是往下走,走不动了,返回上一级在走

数据结构自考
数据结构自考

连通图的广度优先搜索

顺着一个顶点,然后都遍历完。

数据结构自考,自考
数据结构自考,自考

图的应用

最小生成树的概念

概念:一个图的最小生成树是图所有生成树中权总和最小的生成树

构造最小生成树的Prim算法

每次都找权值最小的

看案例

数据结构自考,自考
数据结构自考,自考

构造最小生成树的克鲁斯卡尔算法单源最短路径 这两种算法,自己看一下吧。

拓扑排序

  1. AOV网 工程或者某种流程可以分为若干个小的工程或阶段,这些小的工程或阶段就称为活动。 如果以图中的顶点来表示活动,有向边表示活动之间的优先关系,这种用顶点表示活动的有向图称为AOV网。
数据结构自考,自考
数据结构自考,自考
  1. 拓扑排序 设G=(V,E) 是一个具有n个顶点的有向图,V中顶点的序列v~1~,v~2~,...,v~n~称为一个拓扑序列,当且仅当该顶点序列满足下列条件:若在有向图G中,从顶点v~i~ ~ v~j~ 有一条路径,则在拓扑序列中顶点v~i~必须排在v~j~之前。找到一个有向图的一个拓扑序列的过程称为拓扑排序。完成拓扑排序的前提条件是AOV网中不允许出现回路。

拓扑排序算法的时间复杂度为O(n+e),n是图的顶点个数,e是图的弧的数目。

拓扑排序算法的基本步骤如下:

  1. 图中选择一个入度为0的顶点,输出该顶点
  2. 从图中删除该顶点及相关联的弧,调整被删弧的弧头结点的入度(入度减1);
  3. 重复执行上述两个步骤,直到所有的入度为0

好好理解一下拓扑排序算法吧

自考/数据结构期末考试真题

数据结构自考,自考 数据结构期末考试真题
数据结构自考,自考 数据结构期末考试真题

画图说明步骤 更多图示: https://dwz.cn/r4lCXEuL

数据结构期末考试真题
数据结构期末考试真题

拓扑排序不唯一~

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-01-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 图的基本概念
  • 图的存储结构
    • 邻接矩阵
      • 邻接矩阵自考/期末考试真题
      • 邻接表
      • 图的遍历
        • 连通图的深度优先搜索
          • 连通图的广度优先搜索
          • 图的应用
            • 最小生成树的概念
              • 拓扑排序
              • 自考/数据结构期末考试真题
              相关产品与服务
              对象存储
              对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档