whoway

# DFS/BFS和图论『模板』

  • 蓝桥杯A组、CSP第4题
- 02.最短路径
- 03.网络流
<font style="background:yellow">
<font style="background:pink">
<font style="background: MediumSpringGreen">
1
2
3
4
5

# 📑 目录

[TOC]

  • BFS的和树的层次遍历或者先序遍历结合理解

# 1.DFS模板⭐️

  • 最抽象并且易懂的模板在《算法笔记》的P352的DFS伪代码，统率了两种存储方式的解法。

# 1.1.邻接矩阵版（递归写法）

  • 1、节点数需要小于等于1000，因为这样开的二维数组int的1e6，几乎就差不多了，再开大就不OK，需要借助“邻接表”

  • 2、递归写法

#include<bits/stdc++.h>
using namespace std;

//邻接矩阵最大顶点数 
static const int maxn=1000+5;
static const int INF=0x3f3f3f;

//实际顶点数
int n;
//邻接矩阵存的图
int G[maxn][maxn];
//也可以是bool vis[maxn]={false},标记是否访问的标记数组
bool vis[maxn]={0};

//递归DFS 
void DFS(int current, int depth )
{
	vis[current]=true;
	//框架 ———对当前节点current进行的操作，在这进行
	
	//枚举从current出发能到达的顶点 
	for(int v=0; v<n; ++v)
	{
		if( false==vis[v] && INF!=G[current][v] )
		{
			DFS(v,depth+1);
		}
	}
}


//遍历图 
void DFSTrave()
{
	for(int current=0; current<n; ++current )
	{
		if( false==vis[current] )
		{
			DFS(current,1);//访问current和它所在连通块，1表示DFS的第1层 
		}
	}
} 


int main()
{
	//输入图，并且将无法到达的地方设置权值为INF
    DFSTrave();
    
	return 0;
}
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

# 1.2.邻接矩阵版（栈写法）

void dfs(int now)
{
	vis[now]=1;
	//Balabala1
	for (每一条now出发的边)
	if (!vis[e.to]) dfs(e.to);
	//Balabala2 
}
调用dfs(Start)

改成 

void dfs()
{
	stack[top=1]=Start;
	while(top)
	{
		int now=stack[top];
		if (!vis[now])
		{
			vis[now]=1;
			//Balabala1;
			for (每一条now出发的边)
			if (!vis[e.to]) stack[++top]=e.to;
		}
		else
		{
			//Balabala2;
			top--;
		}
	}
}

作者：陈诗翰
链接：https://www.zhihu.com/question/22985195/answer/29274088

陈诗翰 (作者) 回复赵奕2016-06-22
好像是的喔23
    
赵奕回复陈诗翰 (作者)2016-06-22
貌似把那个for循环倒过来跑一遍就可以了？

陈诗翰 (作者) 回复赵奕2016-06-22
对的
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

# 1.3.邻接表版（队列写法）

# 1.3.1.方法1—vector实现版

# 1.3.2.方法2—链表实现版

# 2.BFS模板⭐️

# 3.图论模板

# 3.1.最小生成树

# 3.1.1.prim算法(⭐️贪心)

#include<cstdio>
#include<cstring>
 
#define M 210
#define INF 0x3f3f3f3f
 
int map[M][M],low[M],visit[M];   //low[i]是一个点到下一个点的最短距离
int prim(int n)
{
    int pos,result = 0,i,j,min;
    memset(visit,0,sizeof(visit));
    visit[1] = 1,pos = 1;
 
    for(i = 1;i <= n; i++)
        if(i != pos)
            low[i] = map[pos][i];
 
    for(i = 1;i < n; i++){
        min = INF;
        for(j = 1;j <= n; j++)
            if(visit[j] == 0 && min > low[j]){
                min = low[j];
                pos = j;
            }
 
        result += min;
        visit[pos] = 1;
        for(j = 1;j <= n; j++)
            if(visit[j] == 0 && low[j] > map[pos][j])
                low[j] = map[pos][j];
    }
    return result;
}
int main()
{
    int n,p;
    while(scanf("%d",&n) != EOF){
        int i,j;
        for(i = 1;i <= n; i++)
            for(j = 1;j <= n; j++){
                scanf("%d",&p);
                map[i][j] = p;
            }
        printf("%d\n",prim(n));
    }
    return 0;
}
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

# 3.1.2.Kruskal算法(⭐️贪心)

  • 存边开始的，边贪心

  • 代码来源：https://www.cnblogs.com/sench/p/7967511.html

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

struct Edge
{
    int a, b, dist;

    Edge() {}
    Edge(int a, int b, int d) :a(a), b(b), dist(d) {}
};

bool cmp(Edge e1, Edge e2)
{
    return e1.dist < e2.dist;
}

const int N = 100 + 10;
vector<Edge> v;
int p[N];
int map[N][N];
int n;

int find_root(int x)
{
    if (p[x] == -1)
        return x;
    else return find_root(p[x]);
}

void kruskal()
{
    memset(p, -1, sizeof(p));
    sort(v.begin(), v.end(), cmp);    //将边按边长从短到长排序
    int ans = 0;
    for (int i = 0; i < v.size(); i++)
    {
        int ra = find_root(v[i].a);
        int rb = find_root(v[i].b);
        if (ra != rb)
        {
            ans += v[i].dist;
            p[ra] = rb;
        }
    }
    printf("%d\n", ans);
}

int main()
{
    //freopen("poj1258.txt", "r", stdin);
    while (scanf("%d", &n) == 1)
    {
        v.clear();    //注意初始化
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i < j) v.push_back(Edge(i, j, map[i][j]));
        kruskal();
    }
    return 0;
}
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
58
59
60
61
62
63
64
65
66
67

# 3.2.拓扑排序

队列/其实stack也行+减治法

# 3.2.1.方法1，没借助「入度」数组优化—低配版

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

        //构造领接表
        bool table[ numCourses ][ numCourses ];
        memset( table, 0, sizeof( table) );
        for( auto vec : prerequisites )
        {
            table[ vec[1] ][ vec[0] ]= true;
        }

        //标记数组，标记是否访问了
        bool visit[ numCourses ];
        memset( visit, 0, sizeof( visit) );

        //开始拓扑排序
        queue<int> help;    //辅助数据结构——队列

        for(int i=0; i<numCourses; ++i)
        {
            bool tag=true;
            for(int row=0; row<numCourses; ++row )
            {
                if( true==table[row][i] )
                {
                    tag=false;
                    break;
                }
            }

            if( true==tag )
            {
                help.push( i );
                break;
            }
        }

        while( !help.empty() )
        {
            int begin=help.front();
            help.pop();
            visit[begin]=true;

            //清除有效边
            for(int col=0; col<numCourses; ++col )
            {
                table[begin][col]=false;
            }

            
            //寻找下一批的，可以被选中的人
            for(int i=0; i<numCourses; ++i)
            {
                if( false==visit[i] )
                {
                    bool tag=true;
                    for(int row=0; row<numCourses; ++row )
                    {
                        if( true==table[row][i] )
                        {
                            tag=false;
                            break;
                        }
                    }

                    if( true==tag )
                    {
                        help.push( i );
                        break;
                    }
                }
            }

        }

        for( int i=0; i<numCourses; ++i)
        {
            if( false==visit[i] )
            {
                return false;
            }
        }

        return true;
    }
};
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

# 3.2.2.方法2.使用「入度」数组优化—标准版

# 3.3.Warshall算法(⭐️dp)

  • 动态规划

# 插曲—最短路径分类

图的最短路径问题有若干变化形式

  • 1.从单个点到某1个点的最短路径
  • 2.从单个点出发到「全部点」的最短路径分别是（Dijstr算法解决）
  • 3.完全最短路径问题：找到「每个顶点」到「其他所有顶点」之间的距离（Floyd算法）

# 3.3.Floyd算法(⭐️dp)

  • 动态规划

    • 计算完全最短路径

    • input：图的权重矩阵

    • output：距离矩阵

# 3.4.Dijkstra(⭐️贪心)

  • 路径贪心

# 3.5.Bellman-Ford算法

# 3.6.SPFA算法（Shortest Path Faster Algorithm）

# 3.6.1.SLF优化(Small Label First)

  • 优化思路：将原队列改成双端队列，对要加入队列的点 p，如果 dist[p] 小于队头元素 u 的 dist[u]，将其插入到队头，否则插入到队尾。

# 3.6.2.LLL优化 (Large Label Last)

  • 优化思路：对每个要出队的队头元素 u，比较 dist[u] 和队列中点的 dist 的平均值，如果 dist[u] 更大，将其弹出放到队尾，然后取队首元素进行相同操作，直到队头元素的 dist 小于等于平均值

# 4.二分图&网络流

基本知识点：

假设大家已经会了：
    建图：邻接表&链式前向星
    判图连通：并查集
    图的遍历：DFS、BFS

最短路：
    SPFA—可以处理有关负权边的图，可以找负环，Bellman-Ford算法的队列优化
    Dijkastra算法——堆优化
1
2
3
4
5
6
7
8