【资料结构】图的基本定义

一个图形具有两个集合的基本组成:G(V,E)

V:表示顶点的集合

  V(G1)={1,2,3,4}

E:表示边的集合

  E(G1)={(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(2,3)}

无向图与有向图

无向图:图的边不具有方向性

  (V0,V1)=(V1,V0)

有向图:图的边具有方向性

  <V0,V1>!=<V1,V0>

<u,v>表示u-->v

      u是边的尾巴      v是边的头

图的限制

完全图

一个图形有最大的边数量

设顶点数为n    无向图:n(n-1)    有向图:n(n-1)/2

邻近与附接

子图

属于图的子集合为子图

路径相关

路径:从顶点到顶点所经过的边

长度:路径上的边数目

除了第一个点和最后一个点，其余经过顶点不重複为简单路径，当第一个点和最后一个点相同时可称为迴圈。

强连结组件

强连结:在有向图中，点u连向v，点v连向u

强连结组:具有强连结的最大子图

分支度

该顶点附接的边数量
有向图: