相关定义

图、顶点、邻接关系(边)

图 graph 是由顶点的有穷非空集合和顶点之间边的集合组成, 通常表示为: G ( V , E ) G(V,E) G(V,E) 其中,G表示一个图,V是图G中 顶点 vertex 的集合,E是图G中 的集合。

  • 线性结构中,元素仅有线性关系,每个元素只有一个直接前驱和直接后继,逻辑关系为“前驱-后继”;
  • 树形结构中,数据元素(结点)之间有着明显的层次关系,每层上的元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关。逻辑关系为“parent-child”;
  • 图形结构中,数据元素(顶点)之间具有任意关系,图中任意两个数据元素之间都可能相关,逻辑关系称为 邻接 adjacent

有向图、无向图、网

  • 无向边 undirected:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶对 ( V i , V j ) (V_i,V_j) (Vi,Vj) 来表示,则左侧无向图表示为: G = ( V 1 , E 1 ) G= (V_1,E_1) G=(V1,E1),其中顶点的集合 V 1 = { A B C D } V_1=\{A,B,C,D\} V1={ABCD}; 边的集合 E 1 = { ( A , B ) , ( B , C ) , ( C , D ) , ( D , A ) , ( A , C ) } E_1=\{(A,B) ,(B,C),(C,D), (D,A) , (A,C)\} E1={(A,B),(B,C),(C,D),(D,A),(A,C)}

  • 有向边 directed:若从顶点 V i V_i Vi V j V_j Vj的边有方向,则称这条边为有向边,也称为 , 用有序偶 < V i , V j > <V_i,V_j> <Vi,Vj> 来表示, V i V_i Vi称为弧尾, V j V_j Vj称为弧头,即 V i V_i Vi指向 V j V_j Vj。 如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。 右侧有向图表示为: G = ( V 2 , E 2 ) G= (V_2, E_2) G=(V2,E2),其中顶点集合 V 2 = { A , B , C , D } V_2=\{A,B,C,D\} V2={A,B,C,D}; 弧集合 E 2 = { < A , D > , < B , A > , < C , A > , < B , C > } E2=\{<A,D>, <B,A>, <C,A>, <B,C>\} E2={<A,D>,<B,A>,<C,A>,<B,C>}

  • 有权图:每条边上带有 权weight 的图,也分有向和无向。

  • 完全无向图:该无向图中任意两个顶点之间都存在边,n个顶点共含有 C n 2 = n × ( n 1 ) 2 C_n^2 = \frac{n×(n-1)}{2} Cn2=2n×(n1)条边;

  • 完全有向图:该有向图中任意两个顶点之间都存在方向相反的两条弧,n个顶点共含有 2 × C n 2 = n × ( n 1 ) 2×C_n^2 =n×(n-1) 2×Cn2=n×(n1)条边;


图的抽象数据类型



图的存储结构

邻接矩阵

邻接表

邻接矩阵和邻接表的比较

以无向图 G ( V , E ) G(V, E) G(V,E)为例,含有n个顶点e条边:

  • 空间复杂度:邻接矩阵 O ( n 2 ) O(n^2) O(n2),邻接表 O ( n + e ) O(n+e) O(n+e)
  • 访问邻接点的平均时间复杂度:邻接矩阵 O ( n ) O(n) O(n),邻接表 O ( e / n ) O(e/n) O(e/n)
  • 唯一性:顶点编号确定后,邻接矩阵是唯一的,邻接表不是,取决于创建图时的输入次序和顶点在边表的插入算法。

图的遍历方式

从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历。


深度优先搜索 DFS
从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v 有路径相通的顶点都被访问到。

广度优先搜索 BFS

广度优先遍历就类似于树的层序遍历。


图的代码实现


图的应用

最小生成树:用最短的路径连接所有顶点

求解两点之间的最短路径

拓扑排序