图

技术探索
🗨️字数统计=1.8k字 ⏳阅读时长≈6分钟

一、相关名词解释

1. 完全图

  • 无向图中任意两个顶点之间都存在边，称为无向完全图。 n个顶点，n(n-1)/2 条边
  • 有向图中任意两个顶点之间都存在相反的两条弧，称为有向完全图。 n个顶点, n(n-1）条边

2. 连通图/强连通图

  • 无向图 中顶点v到顶点w有路径存在，称v和w连通。若任意两个顶点都连通，连通图
    若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图
    若一个图有n个顶点，并且边数大于n-1，则此图必有回路
  • 有向图 中顶点 v 到顶点 w 和顶点 w 到顶点 v 之间都有路径，称 v 和w 强连通 。若任意两个顶点都连通，强连通图

3. 连通分量/极大连通子图

  • 无向图中极大连通子图称为连通分量；
  • 有向图中极大连通子图称为强连通分量；

极小连通子图指该连通子图既保持图的连通且包含的边数最少；

4. 生成树 (对于连通图而言）

连通图的生成树是 包含全部顶点的一个极小连通子图（即包含全部顶点且边数最少）

若砍去生成树的一条边，则会变成非连通图

若加上一条边，则会形成一个回路

5. 顶点的入度和出度

  • 无向图 的的全部顶点的度之和等于边数的2倍
  • 有向图 的全部顶点的入度之和与出度之和相等，且与边数相等

6. 简单路径

序列中的顶点和路径不重复出现的路径。

7. 回路

路径中第一个顶点和最后一个顶点相同的路径


二、图的存储

1. 邻接矩阵法：（稠密图）

图的顺序存储结构

一维数组存储顶点集，二维数组存储边集

无向图的邻接矩阵第i行（列）非零元素的个数表示该顶点的度

有向图的邻接矩阵第i行（列）非零元素的个数表示该顶点的出度（入度）

无向图的邻接矩阵是对称的

2. 邻接表法：（稀疏图）

图的链式存储结构

一个单链表表示该顶点的边表；

各个单链表的头指针和顶点采用顺序存储连接起来表示顶点表

邻接表可以方便的找出一顶点的所有邻边，但确定两结点之间是否有边效率低下

在有向图中，求一个给定结点的出度只需计算邻接表中结点的个数，但求入度需要遍历全部顶点的邻接表

假设有n个顶点，e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为：O(n+e)

首先删除下标为v的顶点表结点的单链表，边数最多n-1，时间复杂度O(n)；

再扫描所有边表结点，删除所有的顶点v的入边，时间复杂度O(e)；

3. 十字链表

有向图的另一种链式存储结构。

4. 邻接多重表

无向图的链式存储结构。


三、图的遍历

1. 广度优先遍历BFS（类似于层次遍历）

基本思想 ：利用 队列 实现。

  • 首先访问起始顶点 V 并将其入队
  • V出队，并遍历V的所有邻接点 w1，w2，….，wn并依次入队
  • w1出队，并遍历 w1 的全部邻接点(不包括已经被访问的点)
  • w2出队，并遍历w2的全部邻接点(不包括已经被访问的点)
  • ……. 以此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    void BFS(Graph G, int v){
        visit(v); //访问初始结点
        visited[v] = TRUE; //初始结点置已访问标识
        EnQueue(Q,v); //顶点v入队
        while(!isEmpty(Q)){
            DeQueue(Q,v); //顶点v出队
            for(w = FirstNeighbor(G,v); w>=0; w = NextNeighbor(G,v,w)){ //循环遍历v所有邻接点
                if(!visited[w]){
                    visit(w); //访问顶点w
                    visited[w] = TRUE;
                    EnQueue(Q, w);
                }
            }
        } //while
    }
    void BFSTraverse(Graph G){
        for(i = 0; i<G.vexnum; i++)
            visited[i] = FALSE;
        InitQueue(Q); //初始化队列
        for(i = 0; i<G.vexnum;i++) //防止一次遍历无法遍历到全部结点（非连通图）
            if(!visited[i]) //若未被访问
                BFS(G,i);
}

2. 深度优先遍历DFS（类似于先序遍历）

基本思想：利用 递归/栈 实现。当不能继续向下访问时，依次回退到最近的被访问结点

  • 首先访问顶点V，并将其标记为已访问
  • 然后访问与顶点V的其中一个未被访问的邻接点W，并将其标记为已访问
  • 再访问W的其中一个未被访问的邻接点，并将其标记为已访问
  • 依次类推….. 当一个顶点所有的邻接顶点都被访问过时，则依次退回最近被访问过的顶点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    void DFS(Graph G, int v){
        visit(v);
        visited[v] = TRUE;
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
            if(!visited[v])
                DFS(G,w); //递归
        }
    }
    void DFSTraverse(Graph G, int v){
        for(int i = 0 ; i<G.vexnum; i++)
            visited[v] = FALSE;
        for(int i = 0; i<G.vexnum; i++)
            if(!visited[v])
                DFS(G,i);
}
}

四、图的应用

1. 最小生成树

① Prim算法

每次选取相对最小的边并且互相连通。需保证无环

② kruskal算法

每次选取最小的边，无须保证此过程是否连通。需保证无环

2. 最短路径

① Dijkstra算法

该算法可以求得某一顶点到其余各顶点的最短路径。

算法思想：

  • 设有两个顶点集合 S 和 T，其中集合 S 中存放的是图中已找到最短路径的顶点，集合 T 中存放 的是图中的剩余顶点。

  • 初始状态时，集合 S 中只包含源点 V0，然后不断从集合 T 中选取到顶点 V0 路径最短的顶点 Vu 并加入集合 S 中，之后的路径可通过该结点

  • 集合 S 每加入一个新的顶点 Vu，都要修改 V0 到集合 T 中各个顶点的最短路径的长度值。

  • 不断重 复这个过程，直至集合T中的顶点全部并入到 S 中为止。

② Floyd算法

每次都试图在路径上添加新的中间结点

3. 拓扑排序

什么图可以进行拓扑排序？

有向无环图

基本思想 ：每次去除一个入度为0的结点和该与顶结点相连的边

若图中存在一条A——>B的路径，则在拓扑排序中表示B事件在A事件的后面

4. 关键路径

具有最大路径长度的路径称为关键路径

只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快所有关键路径上的关键活动才能缩短工期

关于关键路径的求解问题可参考本篇博文：木子阳555 -【数据结构-图】关键路径解法

分享到