数据结构与算法－图

图的定义

图G是由集合V和E组成，记成 G =（V，E）。其中：V为顶点集，不可为空；E为边集，可为空。边是顶点的有序对或无序对，它反映了两顶点之间的关系。

(1). 有向图：边是顶点的有序对的图。（图中每条边都用箭头指明了方向）

(2). 无向图：边是顶点的无序对的图。

图的基本术语

1. 顶点(Vertex)：图中的数据元素。

2. 弧：有向图中，顶点 Vi 到顶点 Vj 的边，记作<Vi,Vj>，Vj为弧头箭头端；Vi弧尾无箭头端。

3. 完全图

(1). 无向完全图：边数=n*(n-1)/2的无向图，其中n为顶点数。

(2). 有向完全图：边数=n*(n-1)的有向图，其中n为顶点数。

4. 权：与图中的边相关的数。

5. 子图：图G和G′，若有V(G′) 包含于 V(G) 和 E(G′) 包含于 E(G)，则称 G′ 为图 G 的子图。

6. 邻接：若 (Vi ,Vj ) 属于 E(G)，则称Vi和Vj互为邻接点。若弧<Vi ,Vj >属于E(G)，则称Vj是Vi的邻接点 。邻接代表的是顶点之间的关系。

7. 关联：若(Vi ,Vj ) 属于 E(G)，则称边(Vi ,Vj )关联于顶点Vi和Vj 。关联代表的是边与顶点间的关系。

8. 度

(1). 无向图D(Vi )：顶点Vi的度为与Vi相关联的边的个数。

(2). 有向图

①. 出度OD(Vi )：顶点Vi的出度为以Vi为尾的出边数；

②. 入度 ID(Vi )：顶点Vi的入度为以Vi为头的入边数；

③. 度D(Vi )：有向图的度=入度+出度，即 D(Vi ) = OD(Vi )+ID(Vi )；

图中边数与顶点的度的关系为：所有顶点度数之和的一半即为边数。

9. 路径

图中顶点Vp至Vq的路径是顶点序列 { Vp,Vi1,Vi2,…,Vin,Vq }，

且对无向图，边(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)属于VR(G)；

或对有向图，弧<Vp,Vi1>,<Vi1,Vi2>,<Vin,Vq>属于VR(G)。

10. 路径长度：路径上边或弧的数目。

11. 简单路径：除第一个和最后一个外，其余各顶点均不 相同的路径。

12. 回路：第一个和最后一个顶点相同的路径，也称环，回路中可以有多个圈。

13. 简单回路：第一个和最后一个顶点相同的简单路径，简单回路只能有一个圈。

14. 连通：无向图中，若从顶点Vi到Vj顶点有路径，则称Vi和Vj是连通的。

15. 连通图和连通分量

16. 生成树：含有该连通图的全部顶点的一个极小连通子图。 若连通图G的顶点个数为n，则G的生成树的边数为n-1。

G的子图G’边数大于n-1，则G’中一定有环。G的子图G’边数小于n-1，则G’中一定不连通。

17. 生成森林：在非连通图中，每个连通分量都可得到一个极小 连通子图，也就是生成树。这些生成树就组成了一个非连通图的生成森林。

图的基本运算

1. 建立图 GreateGraph(G,V,E)

2. 取顶点信息 GetVex(G,u)

3. 取边信息 Getarc(G,u,v)

4. 查询第一个邻接点 FirstVex(G,u)

5. 查询下一个邻接点 NextVex(G,u,v)

6. 插入顶点 InsertVex(G,v)

7. 删除顶点 DeleteVex(G,v)

8. 插入边 InsertArc(G,v,w)

9. 删除边 DeleteArc(G,v,w)

10. 遍历图 Travers(G,tag)