对图的基本理解——数据结构

2019-04-15 18:00发布

首先对于图内所需的基本术语进行理解

  1. 顶点
    可以理解为之前学的结点。可以理解为之前学的结点。
  2. VR
    两个顶点之间的关系,(比如a----b(无向图),这样说明a的尾部是b,也可以知道b的头是a)。
  3. 弧---->有向图 边----->无向图
    比如a---->b,可以这样理解a能检索到b,但b不能检索到a。这样的话----->这种的符号称为弧,即弧是单向的,是有向图特有的。
    a-----b这样的形式的话,表示a能检索到b,同样b也能检索到a,------这样的符号称为边,即边是双向的,是无向图所特有的。
  4. 稠密图,完全图,稀疏图
    完全图 假设有n个顶点,那么对于无向完全图而言,它有n(n-1)/2个边,
    对于有向完全图而言,它有n(n-1)个弧
    稀疏图 无向稀疏图的边小于nlogn的话,该图叫做稀疏图,反之稠密图。
  5. 邻接点
    如果边(v,v’)之间存在关系的话,那么顶点v,v’互为领接点,即v,v’相邻接,也可以说,边(v,v’)与顶点v,v’相关联。

  6. 对于 无向图而言,度就是,该顶点与多少个顶点相邻接。
    对于有向图而言,度包括出度和入度,出度就是由该顶点,向其他顶点发出的弧数,入度就是其他结点向该顶点发出的弧数。
  7. 权与网
    权是建立在弧或边的基础之上的,它可以表示从该顶点到邻接点所消耗的时间或距离等信息。这样的图称为赋权图
  8. 路径与回路
    路径就是顶点v到某一顶点的顶点序列,其中经过的弧或边的数目就称为路径。如果路径中第一个顶点和最后一个顶点相同的话就成为回路。
  9. 连通图
    在无向图中,若从某一顶点v到另一顶点v'有路径相通,则称vv'是连通的。如果任意两个顶点都是连通的,则称该无向图为连通图