三、软设笔记【数据结构】-图、图的遍历、拓扑排序

电玩女神 2022-01-06 13:47 77阅读 0赞

一、图  
图G是由两个集合V和E构成的二元组，记作G+(V，E)，其中V是图中顶点的非空有限集合，E是图中边的有限集合。  
\*有向图：图G中的每条边都是有方向的，顶点间的关系用<vi，vj>表示；  
\*无向图：图G中的每条边都是无方向的；顶点间的关系用<vi，vj>表示；  
\*完全图：图G任意两个顶点都有一条边相连接；  
\*有向完全图：n个顶点的有向图有n(n-1)条边。  
\*无向完全图：n个顶点的无向图有n(n-1)/2条边。  
  
  
1.度：顶点v的度是与它相关联的边的条数，记作TD(v)。  
\*入度：是以v为终点的有向边的条数，记作ID(v)；  
\*出度：是以v为始点的有向边的条数，记作OD(v)。  
在有向图中，顶点的度等于该顶点的入度与出度之和。  
  
2.带权图：  
即边上带权的图，其中权是指每条边标上的具有某种含义的数值（即与边相关的数）。  
  
3.连通图  
在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。如果图中的任意一对顶点都是连通的，则称此图是连通图。无向图G=(V,E)是连通的，那么边的数目大于等于顶点的数目减一  
  
强连通图：在有向图中，若对于每一对顶点vi和vj，都存在一条从vi到vj到vj到vi的路径，则称此图是强连通图。  
  
4.生成树(最小生成树)  
是一个极小的连通子图，它含有图中全部n个顶点，但只有n-1条边。  
\*如果在生成树上添加1条边，必定构成一个环。  
\*若图中有n个顶点，却少于n-1条边，必为非连通图。  
  
1.邻接矩阵  
对于一个具有n个结点的图，可以使用n\*n的矩阵（二维数组）来表示它们间的邻接关系。  
2.邻接表  
邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存储相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。  
  
三、图的遍历  
1.深度优先搜索（DFS）  
\*访问起始点v；  
\*若v的第一个邻接点没有访问过，深度遍历此邻接点；  
\*若当前邻接点已访问过，再找v的第二个邻接点重新遍历。  
2.广度优先搜索（BFS）  
\*在访问了起始点v之后，依次访问v的邻接点；  
\*然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；  
\*直到所有顶点都被访问过为止。  
  
四、拓扑排序  
AOV网是一种有向无环图，顶点表示一项工作，有向边表示前一项工作完成后才能开始后一项工作。AOV网中的顶点之间隐含着某种顺序，求解这个顺序序列的操作称为拓扑排序。对AOV网进行拓扑排序的基本思想是：  
（1）从AOV网中选择一个没有前驱的顶点输出它；  
（2）从AOV网中删去改顶点，且删去所有以该顶点为尾的弧；  
（3）重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。

转载于:https://www.cnblogs.com/changemax/p/10015120.html