2023计算机考研初试在即，在最后阶段建议各位同学将知识点再系统复习一遍，以免有所遗漏！2022计算机考研数据结构第五单元知识点包含图、图的存储结构、图的遍历等内容。高顿考研为大家整理了2022计算机考研数据结构第五单元知识点的详细内容，供大家参考复习！
图
图是一种非线性结构。在图中，每个结点可以有任意个前驱、任意个后继。
相关术语：
顶点：图中的结点常称为顶点。
边：结点的偶对。
有向图：若代表一条边的偶对是有序的，则称其为有向图。用〈u,v〉表示有向边。
无向图：若代表一条边的偶对是无序的，则称其为无向图。用(u,v)表示无向边。
完全图：一个图有最多的边数，无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边。
简单路径：一条路径上的所有顶点，除起始顶点和终止顶点可以相同外，其余顶点各不相同。
回路：是一条简单路径，其起始顶点和终止顶点相同。
连通图：无向图中，若两个顶点u和v之间存在一条从u到v的路径，则称u和v是连通的。若图中任意一对顶点都是连通的。
强连通图：有向图中，若任意一对顶点u和v间存在一条从u到v的路径和一条从v到u的路径。
连通分量：无向图的极大连通子图。
强连通分量：有向图的极大强连通子图。
度：在无向图中，与某个顶点相关联的边的数目。
入度：在有向图中，以某个顶点为头(始点)的边的数目。
出度：在有向图中，以某个顶点为尾(终点)的边的数目。
有向图的根：恰有一个顶点入度为0，其余顶点入度为1，该顶点称为有向图的根。
网：带权值的图。
相关运算：
Exist(u,v)：如果图中存在边，则函数返回true，否则返回false。
Insert(u,v,w)：向图中添加权为w的边，若插入成功，则函数返回Success;若图中已存在边，则函数返回Duplicate;其它情况函数返回Failure。
Remove(u,v)：从图中删除边，若图中不存在边，则函数返回NotPresent;若图中存在边，则从图中删除此边，函数返回Success;其它情况函数返回Failure。
Vertices()：函数返回图中顶点数目。
图的存储结构
(1)邻接矩阵
a<u><u>=0：主对角线元素都是0;
a<u>[v]=w：
若E，则w=1，或w=w(i,j)(带权图);
若E，则w=noEdge，其中，noEdge=0(不带权图);noEdge=INF(带权图)。
(2)邻接表
在邻接表中，为图的每个顶点u建立了一个单链表，链表中的每个结点代表一条边，称为边结点。这样，顶点u的单链表记录了邻接自u的全部顶点。每个单链表相当于邻接矩阵的一行。
图的遍历
(1)深度优先遍历
a.访问顶点v，并对v做已访问标记;
b.依次从v的未访问的邻接点出发，对图作深度优先搜索。
图中所有顶点，以及在遍历时经过的边(即从已访问的顶点到达未访问顶点的边)构成的子图，称为图的深度优先搜索生成树(或生成森林)。
(2)广度优先遍历
a.访问顶点v，并对v做已访问标记;
b.依次访问v的各个未访问过的邻接点;
c.再依次访问分别于这些邻接点相邻接且未访问过的顶点。
图中所有顶点以及在遍历时经过的边(即从已访问的顶点到达未访问顶点的边)构成的子图称为图的广度优先搜索生成树(或生成森林)。
算法见书P166
拓扑排序
拓扑排序：将有向图中的顶点排成一个拓扑序列的过程。
拓扑序列：有向图中的一个顶点序列，对图中任意两个顶点i和j，若i是j的前驱结点，则在线性序列中i先于j。
AOV网：以顶点表示活动，有向边表示活动之间的领先关系的有向图。
注意：拓扑序列不是唯一的!
可以用拓扑排序的方法来测试有向图是否存在回路，若经过拓扑排序后所有顶点都已列出，则不存在回路。
排序步骤：
a.任选一个入度为零的顶点，并输出之;
b.从图中删除该顶点及其所有出边;
c.重复步骤1、2，直到所有顶点都已输出，或者直到剩下的图中再也没有入度为零的顶点为止，后者表示图中包含有向回路。
最小代价生成树
无向连通图的生成树是一个极小连通子图，它包括图中全部顶点，并且有尽可能少的边。
无向连通网络的最小代价生成树是所有生成树中边的权值之和最小的。
(1)普里姆算法：
首先，从n个顶点中任选一个顶点v加入到原来为空的生成树中;然后，重复执行下列操作：从一个顶点在生成树中，而另一个顶点不在生成树中的那些边中，选取一条权值最小的边，并将这条边以及它所关联的目前还不在生成树中的那个顶点加入到生成树中。当生成树中的顶点数达到n时，整个构造过程结束。
(2)克鲁斯卡尔算法
单源最短路径
边的权值之和最小的路径称为最短路径，并称v(x)为这条最短路径的源点，v(i)为终点。
迪杰斯特拉算法：
按最短路径长度值由小到大的次序，逐步求得每一条最短路径。
关键路径
关键路径：在无回路的有向网络中，假设只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点)，则从源点到汇点之间的最长的路径称为关键路径。
AOE网：以顶点代表事件，有向边表示活动，有向边上的权表示一向活动所需的时间。注意AOV网和AOE网的区别
关键活动：对整个工程的最短完成时间有影响的活动。
求关键路径的算法：(见书P174)
a.计算每个事件可能的最早发生时间
b.计算每个事件允许的最迟发生时间
c.输出关键活动

展开全文