图论

                              图论


 

基本概念

图是由顶点的有穷非空集合以及顶点的边的集合组成,通常表示为G(V,E); V是顶点的集合、E是边的集合;

基本术语

  1. 无向边:若顶点Vi和Vj之间的边没有方向,称这条边为无向边(Edge),用(Vi,Vj)来表示。
  2. 无向图(Undirected graphs):图中任意两个顶点的边都是无向边。
  3. 有向边:若从顶点Vi到Vj的边有方向,称这条边为有向边,也称为弧(Arc),用 <Vi, Vj> 来表示,其中Vi称为弧尾(Tail),Vj称为弧头(Head)。
  4. 有向图(Directed graphs):图中任意两个顶点的边都是有向边。
  5. 简单图:不存在自环(顶点到其自身的边)和重边(完全相同的边)的图
  6. 无向完全图:无向图中,任意两个顶点之间都存在边。
  7. 有向完全图:有向图中,任意两个顶点之间都存在方向相反的两条弧。
  8. 稀疏图;有很少条边或弧的图称为稀疏图,反之称为稠密图。
  9. (Weight):表示从图中一个顶点到另一个顶点的距离或耗费。
  10. :带有权重的图
  11. 度:与特定顶点相连接的边数;
  12. 出度、入度:有向图中的概念,出度表示以此顶点为起点的边的数目,入度表示以此顶点为终点的边的数目;
  13. :第一个顶点和最后一个顶点相同的路径;
  14. 简单环:除去第一个顶点和最后一个顶点后没有重复顶点的环;
  15. 连通图:任意两个顶点都相互连通的图;
  16. 极大连通子图:包含尽可能多的顶点(必须是连通的),即找不到另外一个顶点,使得此顶点能够连接到此极大连通子图的任意一个顶点;
  17. 连通分量:极大连通子图的数量;
  18. 强连通图:此为有向图的概念,表示任意两个顶点a,b,使得a能够连接到b,b也能连接到a 的图;
  19. 生成树:n个顶点,n-1条边,并且保证n个顶点相互连通(不存在环);
  20. 最小生成树:此生成树的边的权重之和是所有生成树中最小的;
  21. AOV网(Activity On Vertex Network ):在有向图中若以顶点表示活动,有向边表示活动之间的先后关系
  22. AOE网(Activity On Edge Network):在带权有向图中若以顶点表示事件,有向边表示活动,边上的权值表示该活动持续的时间

有向图与无向图

1.无向图(undirected graph)

       如果一个图结构中,所有的边都没有方向性,那么这种图便称为无向图。典型的无向图,如图二所示。由于无向图中的边没有方向性,这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边,可以表示为(V2, V6),也可以表示为(V6,V2)。

  图论

                        图二  无向图

      对于图二无向图,对应的顶点集合和边集合如下:

       V(G)= {V1,V2,V3,V4,V5,V6}

       E(G)= {(V1,V2),(V1,V3),(V2,V6),(V2,V5),(V2,V4),(V4,V3),(V3,V5),(V5,V6)}

 

    2.有向图(directed graph)

      一个图结构中,边是有方向性的,那么这种图就称为有向图,如图三所示。由于图的边有方向性,我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边,例如<V2,V6>表示从顶点V2到顶点V6,而<V6,V2>表示顶点V6到顶点V2。

     图论

                    图三  有向图

 

      对于图三有向图,对应的顶点集合和边集合如下:

       V(G)= {V1,V2,V3,V4,V5,V6}

       E(G)= {<V2,V1>,<V3,V1>,<V4,V3>,<V4,V2>,<V3,V5>,<V5,V3>,<V2,V5>,<V6,V5>,<V2,V6>,<V6,V2>}

  

      注意:

          无向图也可以理解成一个特殊的有向图,就是边互相指向对方节点,A指向B,B又指向A。

邻接链表与邻接矩阵
图最常见的表示形式为邻接链表和邻接矩阵。邻接链接在表示稀疏图时非常紧凑而成为了通常的选择,相比之下,如果在稀疏图表示时使用邻接矩阵,会浪费很多内存空间,遍历的时候也会增加开销。但是,这不是绝对的。如果图是稠密图,邻接链表的优势就不明显了,那么就可以选择更加方便的邻接矩阵。

还有,顶点之间有多种关系的时候,也不适合使用矩阵。因为表示的时候,矩阵中的每一个元素都会被当作一个表。

上一篇:阿里云 FaaS 架构设计与创新实践


下一篇:Photoshop制作星空爆炸效果