第七章 图

什么是图

图的定义

图中的数据元素通常称为顶点，所有顶点构成顶点集，我们通常用V(Vetex)来表示。
元素间的关系用边来表示，通常用E(edge)来表示边集合。

根据图中的边是否有方向，图可分为：

  • 无向图
  • 有向图
    带权图-网

完全图: 有n个顶点,n(n-1)/2条边的无向图。
有向完全图: 有n个顶点，n(n-1)条边的有向图。

图的基本概念

顶点间的关系：

  • 邻接
  • 邻接点：若图中两个顶点之间存在边或弧，则称两个顶点互为邻接点。
  • 度：一个顶点的邻接点的个数。

入度：指以该顶点为弧头的弧的数目。
出度：指以该顶点为弧尾的弧的数目。

路径：无向图G中，从顶点vi到顶点vj的路径是一个顶点序列，起点为vi，终点为vj，可表示为一个这样的序列(vi,vi0,vi1,……,vim,vj)，其中任意两个相邻的顶点间必须存在邻接关系。如果图G是有向图，则路径也是有向的。
路径长度：该路径上边或弧的条数。

图的存储

顺序存储 - 邻接矩阵

链式存储 - 邻接表

若有向图有n个顶点，e条边，则它的邻接表需要n个头结点，e个表结点

对比

存储结构 存储方法 操作特性
邻接矩阵 一维数组（顶点）二维数组（邻接关系） 1.易于判定顶点是否邻接、查询某顶点的邻接点 2.插入、删除顶点复杂O(
邻接表 头结点（顶点）表结点（邻接关系） 1.易于：查询某顶点的邻接点；边或弧的插入、删除 2.判定顶点是否邻接：比邻接矩阵低效

图的遍历

DFS

1
2
3
4
5
6
7
8
9
10
11
Status DFS(Graph G, int v){
    // 从第v个顶点出发，DFS遍历图
    Visited[v] = true;
    Traverse(v);
    for(w = FirstAdjVex(G,v); w > 0; w = NextAdjVex(G, v, w)){
        // 对v尚未访问的邻接顶点w递归调用DFS
        if(!visited[w]){
            DFS(G, w);
        }
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status BFS(Graph G, int v){
    if(!visited[v]){
        EnQueue(Q, v);
        while(!EmptyQueue(Q)){
            visited[u] = true;
            Traverse(u);
            DeQueue(Q, u);
            for(w = FirstAdjVex(G, u); w != 0; u = NextAdjVex(G, u, w)){
                if(!visited[w]){
                    EnQueue(Q, w);
                }
            }
        }
    }
}

最小生成树

  • Prim
  • Kruskal

拓扑排序

最短路径

  • Dijsktra
  • Floyd