MENU

抽象的“图”

• November 12, 2020 •

抽象的“图”

如果你问一位小学生,什么是树哇,他可能会指着大树说:“这就是树”;那什么又是图呢,“教室后面的黑板报上面就有图”

如果你问一位计算机专业的学生,“树是一种数据结构,这种结构的形状非常像一棵树,为了方便我们理解,我们将这种结构类比成树,子树——树枝,叶子结点——果实,路径——上树摘果子,所以我们通常称这种数据结构为树”

自然,图也是如此,一种数据结构,我们将所有的结点洒在一块平面上,他们相互散乱的连接,一个结点可有多个前驱结点和多个后继结点,就成了一张图


图的基本概念(能记就记,记不住就算了,用到的时候翻一下就阔以了,翻多了就记住了哈哈哈):

1.图分为无向图、有向图——>图上能看见箭头符号

2.完全图:途中任意两个顶点都可直接相互通达

3.邻接顶点:和自己共用一条边的顶点

4.顶点的度:我们期末考试就考了,度可以分成入度和出度,有向图:度等于出度与入度之和,出度就是指出去的箭头,入度是指回来的箭头;无向图:度等于出度或者等于入度

5.权,边的数据信息

6.路径长度:对于不带权的图,长度等于边的条数

7.带权图:路径所经过边的权值总和

8.子图,从图中扣一块下来就是子图

9.连通图和强连通图:从任意一个顶点出发,可以到达图中任何一个顶点,满足这一条件的图,若是无向图,称为连通图,若是有向图,称为强连通图

10.生成树:前提:连通图。一个连通图的最小连通子图就是该图的生成树,很可能考:有n个顶点的连通图的生成树有n个顶点和n-1条边

11.简单路径和回路:路径上没有重复的顶点,就叫简单路径,从一个顶点出发,最后又回到了该顶点,所经过的路径就是一条回路


复习了图的基本概念,咱们就来试试敲代码吧

Archives QR Code Tip
QR Code for this page
Tipping QR Code