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()：函数返回图中顶点数目。

　　第五单元 第六单元 第七单元

　　以上是小编为大家整理分享的“2022考研计算机数据结构：图”相关内容，希望对大家有帮助。祝大家考上理想的院校!

2022考研计算机数据结构：图