数据结构与算法第八章 图

数据结构第八章 图

连通图、强连通图与连通分量、强连通分量

讨论强连通的前提是有向图

强连通图指的是图中各节点可互相到达

邻接矩阵（无向图对称，有向图不一定），如果是有权图，元素用权值表示，无边则置为无穷大。

画有向图的邻接表与逆邻接表

对每一个结点构建一个链表，将其出边连接的每一个结点存入，逆邻接表则相反（将入边连接的结点存入）

画有向图的邻接多重表

邻接多重表结构：对边结点的五个域：

mark（标记域） vertix1（始点） vertix2（终点） path1 path2

path1、path2是链接指针，path1指向与该边有同一始点的边；path2指向与该边有同一终点的边。

Kruskal算法的最优化证明：

（1）假设\(T\)是Kruskal算法的生成树，\(T^*\)是最小生成树

（2）假设\(e\)是在构造\(T\)时第一条不在\(T^*\)中的边，若整个过程不出现此情况，则就是最小生成树，下面证明第一种情况是不成立的。

（3）在\(T^*\)中加入\(e\)，一定会形成一条回路，此回路中至少有一条边\(e'\)不属于\(T\)

（4）在\(T^*\)视角中，一定有\(w(e')<w(e)\)（否则此回路保留\(e\)，删去\(e'\)得到边权和更小的生成树，矛盾）

（5）在\(T\)视角中，一定有\(w(e)<w(e')\)，矛盾

Prim算法

从连通网络中的某一顶点\(u_0\)出发, 选择与它关联的最小权值边 \((u_0, v)\), 将\(v\)加入到生成树顶点集合\(U\)中。

以后每一步从一个顶点在\(U\)中, 而另一个顶点不在\(U\)中的各条边中选择权值最小的边\((u', v')\), 把\(v'\)加入到\(U\)中。如此继续，直到网络中所有顶点都在\(U\)中为止。

prim算法适用于边稠密的网络。Kruskal算法适合于边稀疏的情形。

最短路径

Dijkstra算法（单源最短路径，不能出现负权）

使用堆优化，时间复杂度为：\(O((n+m)\log n)\)

将点分为2类，已经确定最短路径/未确定最短路径的点，分别记为白点、蓝点。

流程：

（1）初始化\(dis_{start}=0\)，其他节点的\(dis\)记为无穷大；

（2）找一个\(dis\)值最小的蓝点\(x\)，将其变为白点；

（3）遍历\(x\)的所有出边\((x,y,z)\)，若\(dis_y>dis_x+z\)，则令\(dis_y=dis_x+z\)

（4）重复（2）（3），直到所有点变为白点

当前时间复杂度为\(O(n^2)\)

正确性分析：核心是第（2）步所找的点\(x\)已经无法更新为更小的\(dis\)值，故变为白点。

设源点为\(s\)，当前更新点为\(x\)，记真实的\(\min dis_x=d',当前的dis_x=d\)，假设当前存在一条路径使得\(d'<d\)，则必然存在顶点\(p\)，\(W_{s\to p}+W_{p\to x}<d\)，而路径权值均非负，故应先更新\(dis_p\)，故更新\(x\)时，不存在满足上述条件的\(p\)，正确性成立。

注意：当存在负权边时，可以使\(\forall p,W_{s\to p}>d,W_{s\to p}+W_{p\to x}<d\)，导致\(x\)被错误地提前更新。

（2）步骤可以优化：仅考虑\(dis_x\neq +\infty\)的集合。在（3）中，若\(dis_y\)出现优化，将\(y\)加入\(dis\)小根堆中，开销为\(O(\log n)\)

参考代码，以LuoguP4779 单源最短路径为例 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int h[M],n,m,s,tot,vis[N];
long long dis[N];
struct priority
{
    int w,v;
    bool operator<(const priority &x)const
    {
        return x.w<w;
    }
};
std::priority_queue<priority> q;
struct edge{int v,w,next;}a[M];
void add(int x,int y,int z)
{
    a[++tot]=(edge){y,z,h[x]};
    h[x]=tot;
}
void dijkstra()
{
    for(int i=1;i<=n;i++) dis[i]=1e17;
    dis[s]=0;
    q.push((priority){0,s});
    while(!q.empty())
    {
        priority temp=q.top();q.pop();
        int x=temp.v,w=temp.w;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=h[x];i;i=a[i].next)
        {
            int v=a[i].v;
            if(dis[v]>dis[x]+a[i].w)
            {
                dis[v]=dis[x]+a[i].w;
                if(!vis[v])
                    q.push((priority){dis[v],v});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    return 0;
}
```

Floyd算法（所有顶点之间的最短路径）

时间复杂度为\(O(n^3)\)，记\(dp_{i,j}\)表示从顶点\(i\)出发，到达顶点\(j\)的最短路径

流程：

（1）初始化\(dp\)数组为正无穷，并改\(dp_{i,i}=0\)，对于边\((x,y,z)\)，改\(dp_{x,y}=z\)

（2）对\((i,j)\)，\(dp_{i,j}=\min\limits_{1\le k\le n}(dp_{i,j},dp_{i,k}+dp_{k,j})\)

Floyd算法的实现（关键部分）

\(dis_{i,j}\)是起点为i，终点为j的最短路径长度，\(path_{i,j}\)是相应路径上顶点j的前一顶点标号。 按如下方式求解\(i\to j\)的最短路径经过的各顶点，\(a_1=path_{i,j},a_2=path_{i,a_1},a_3=path_{i,a_2},\cdots,a_n=path_{i,a_{k}},其中a_n=i\)，所得最短路径为\(a_n\to a_{n-1}\to\cdots\to a_1\to j\) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        dis[i][j]=INF,path[i][j]=0;
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        a[i][j]=getweight(i,j);
        path[i][j]=i;
        if(i==j) a[i][j]=0;
    }
for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(dis[i][j]>dis[i][k]+dis[k][j])
            {
                dis[i][j]=dis[i][k]+dis[k][j];
                path[i][j]=path[k][j];
            }
        }

【相关题目】LuoguB3611 传递闭包

AOV网络：用顶点表示活动，有向边\((v_i,v_j)\)表示活动\(v_i\)必须先于\(v_j\)活动进行。如果出现有向回路，则出现错误。

拓扑排序：

（1）初始化：将入度为0的点存入队列

（2）依次取出队首，遍历其出边，并将出边所指的顶点的入度减1，若减为0，将此点加入队列。

（3）重复（2），直到队列为空

若存入队列中的元素数量和为总元素数，则此图是有向无环图，它的一个拓扑排序为前面流程的入队顶点序列，否则图中存在有向环。

算法时间复杂度为\(O(n+m)\)

参考代码，以LuoguB3644 拓扑排序为例 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
queue<int> q;
int din[N],n,tot,h[N];
struct edge{int v,next;}a[N];
void add(int x,int y)
{
    a[++tot]=(edge){y,h[x]};
    h[x]=tot;
}
int main()
{
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++)
    {
        while(scanf("%d",&x)&&x)
            add(i,x),din[x]++;
    }
    for(int i=1;i<=n;i++)
        if(!din[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        printf("%d ",x);
        for(int i=h[x];i;i=a[i].next)
        {
            din[a[i].v]--;
            if(!din[a[i].v]) q.push(a[i].v);
        }
    }
    return 0;
}

AOE网络：顶点表示事件、有向边表示活动、边上权值表示活动持续时间。

（考试重点）计算AOE网络中各结点的\(V_E,V_L\)，各边的\(A_E,A_L\)