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考研计算机数据结构:图”相关内容,希望对大家有帮助。祝大家考上理想的院校!

.xqy_container .xqy_core .xqy_core_main .xqy_core_text{height:auto !important;}

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

未经允许不得转载:考研培训网 » 2022考研计算机数据结构:图

赞 (0) 打赏

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏