一个博客

随便写写

0%

图论

发表于 更新于

最近学了一些图的算法，因为我写的和网上的有一些区别，为了以后能够看懂，来记录一下我的写法注释。

链式前向星

链式前向星是比较高效且常用的存图方法，网上的写法都是用结构体来保存边的，但是我不喜欢写结构体，而且链式前向星只是用于保存，且保存之后不会再调整顺序，所以用平行数组保存。

1
2
int N[m],T[m],R[n];
//如果带权再加上W[m]

n和m分别为最大点数+1和最大边数+1。

R[i]表示以i为起点的一条边的序号，记为j，N[j]表示和j边相同起点的下一条边的序号，T[j]表示j边的终点，W[j]表示j边的权。

存图

假设要保存第i条边，起点、终点、权重分别用a,b,c表示。那么代码如下：

1
2
3
4
N[i]=R[a];
T[i]=b;
R[a]=i;
W[i]=c;

这样保存就像链表的前插法，后面插入的边会在前面，如果一些题目遍历图的时候对顺序有要求，那可以先对输入数据进行排序，然后再存图。

排序

假设每行数据的结构是“起点 终点 权重”，如果要进行排序，最好是写个结构体然后用结构体数组保存，然后自己写排序，或者重载比较运算符或者比较函数来用sort排序。但是这些都太麻烦了，所以我使用嵌套pair数组，pair自带重载比较运算符，以first以第一关键字，以second为第二关键字比较，可以省事很多。我这里用的是pair<pair<int,int>,int>，从左到右依次为“起点 终点 权重”。

如果要从较小的点到较大的点遍历，先插入的会在后面，所以按照降序排序，sort的第三个参数为greater()。

重边

链式前向星正常保存可以保存重边，但是有些情况需要去除重边，比如最长路或者最短路问题，这种时候只需要最长边或者最短边，如果每次保存边的时候都要遍历看边是否存在以及比较大小那耗时会非常恐怖。

我的处理方式是先对数据以权重为第一关键字进行排序，再用一个bool[n][n]或者bitset[n]数组来保存a到b的边是否已经保存了，第一个保存的一定是最大或最小的边，如果已经保存了就不需要再保存。

广度优先搜索

这里直接贴样例代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
int N[1001],T[1001],R[101],Q[101];
bool V[101];
//中间省略输入和存图
Q[0]=Q[1]=V[1]=1;
for(int j=1;Q[i];++i){
    //一些代码
    for(int j=R[i];j;j=N[j]){
        if(V[j])continue;
        V[j]=1;
        ++Q[0];
        Q[Q[0]]=j;
    }
}

深度优先搜索

深搜有两种写法，递归和栈，这里两种都写一下。
递归写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
int N[1001],T[1001],R[101];
bool V[101];
void F(int n){
    //一些代码
    for(int i=R[n];i;i=N[i]){
        if(V[i])continue;
        V[i]=1;
        F(i);
    }
}
//中间省略输入和存图
V[1]=1;
F(1);

栈写法，注意，这样遍历的顺序和保存的顺序是反的。

1
2
3
4
5
6
7
8
9
10
11
12
13
int N[1001],T[1001],R[101],S[101];
bool V[101];
//中间省略输入和存图
S[0]=S[1]=V[1]=1;
for(;S[0];——S[0]){
    //一些代码
    for(int i=R[S[0]];i;i=N[i]){
        if(V[i])continue;
        V[i]=1;
        S[S[0]]=i;
        ++S[0];
    }
}

拓扑排序

SPFA算法

SPFA算法可以用来求带权最长或者最短路，可以处理负权，但是听说很容易hack数据达到最坏情况。

Dijkstra算法

Dijkstra算法可以用来求无负环最短路，比SPFA算法稳定。对于负权和求最长路需要一些处理，详细参考这篇文章