【自考】数据结构第五章图，期末不挂科指南，第9篇
图的基本概念
首先，你要明确图是什么样子的，就是下面这个样子的
图的定义与术语
有向图和无向图
直接对比图就可以看出来，有向图和无向图的区别了，这个没有什么难的。
有向图和无向图的表示法有略微的区别，注意看
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称为弧头或终点。
任何两点之间都有边的无向图称为无向完全图。
任何两点之间都有弧的有向图称为有向完全图。
权、带权图：图的边附带数值，这个数值叫权。每条边都带权的图称为带权图。
顶点的度、入度、出度：
- 无向图中顶点v的度是与该顶点相关联的边的数目，记为D(v)。
- 有向图中，把以顶点v为终点的弧的数目称为v的入度，记为ID(v)；把以顶点v为始点的弧的数目称为v的出度，记为OD(v)。有向图顶点v的度为入度和出度之和，即D（v） = ID（v）+ OD（v）。
简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。第一个顶点和最后一个顶点相同的路径称为回路。除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为简单回路或简单环。
下面还有一些需要了解的术语
连通、连通图、连通分量、极大连通子图、强连通、强连通图、强连通分量、生成树、生成森林
如果精力足够，都看看吧
图的存储结构
图的存储结构有很多中，例如 邻接矩阵、邻接表、十字链表和邻接多重表
邻接矩阵
矩阵中标记1，有边，标记0，没有边
注意：无向图的邻接矩阵是一个对称矩阵
带权图的邻接矩阵
邻接矩阵自考/期末考试真题
尝试着，画出无向图吧！
邻接表
邻接表是顺序存储与链式存储相结合的存储方法。
下图中，左侧是无向图，右侧是该无向图的邻接表，注意看，∧该符号，表示结束，没有连接的顶点了。
有向图及其类似，这个就不在做图扩充
图的遍历
图的遍历是指从图的某个顶点出发，系统地访问图的每个顶点，并且每个顶点只被访问一次。
遍历图的基本方法有两种：深度优先搜索和广度优先搜索。
连通图的深度优先搜索
深度优先，就是往下走，走不动了，返回上一级在走
连通图的广度优先搜索
顺着一个顶点，然后都遍历完。
图的应用
最小生成树的概念
概念：一个图的最小生成树是图所有生成树中权总和最小的生成树
构造最小生成树的Prim算法
每次都找权值最小的
看案例
构造最小生成树的克鲁斯卡尔算法 与 单源最短路径 这两种算法，自己看一下吧。
拓扑排序
AOV网
工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。
如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为AOV网。
- 拓扑排序
设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是图的弧的数目。
拓扑排序算法的基本步骤如下：
- 图中选择一个入度为0的顶点，输出该顶点
- 从图中删除该顶点及相关联的弧，调整被删弧的弧头结点的入度（入度减1）；
- 重复执行上述两个步骤，直到所有的入度为0
好好理解一下拓扑排序算法吧
自考/数据结构期末考试真题
画图说明步骤
更多图示： https://dwz.cn/r4lCXEuL
拓扑排序不唯一~