深度优先搜索dfs

深搜概述

深度优先搜索dfs：按照深度优先的方式进行搜索，"一条路走到黑"。

深度优先搜索和递归的区别：深度优先搜索是一种算法，注重的是思想，而递归是一种基于编程语言的实现方式

例题

1.排列数字

题目

代码

C++

#include<iostream>

using namespace std;

const int N = 10;

int n;
int path[N]; //记录方案
bool st[N];  //记录状态（这个数字是否被使用过）true表示用过

void dfs(int u){
    if(u == n){
        for (int i = 0;i < n;i++)
        {
            printf("%d ",path[i]);
            
        }
        printf("\n");
        return; //回溯
    }
     for(int i = 1;i <= n;i++){
            if(!st[i]){
                path[u] = i;  //没有被使用
                st[i] = true;
                dfs(u+1);//下一层
                //path[u] = 0;//恢复现场
                st[i] = false;
            }
        }    
}
int main()
{
    cin>>n;

    dfs(0);
    
    return 0;
}

2.枚举元组B3621

题目

代码

c++

#include<iostream>

using namespace std;

const int N = 10;
int n,k;
int path[N];
 
void dfs(int u) {
	if (u == n) {
		for (int i = 0; i < n; i++)
			cout << path[i] << " ";
		cout << endl;
		return;
	}
	for (int i = 1; i <= k; i++) {
		path[u] = i;
		dfs(u + 1);
	}
}
 
int main() {
	cin >> n >> k;
	dfs(0);
	return 0;
}

广（宽）度优先搜索BFS

队列queue

1、概述

队列（queue）：是一种运算受限制的线性表。其限制只允许从表的队首进行删除操作，而在表的队尾进行插入操作。特点：先进先出

队列的插入操作又叫入队，队列的删除操作又叫出队。

2、构造

#include "queue"
using namespace std;
int main() {
    queue<int> q;
    return 0;
}

3、使用

入队与出队 push()：入队
pop()：出队
获取队首元素 front()：获取队首元素
判空 empty()：判断是否为空
清空清空一个队列，需要手动清空。
while(!q.empty()) { q.pop(); }

广度优先搜索BFS

1、广度优先搜索BFS概述

广度优先搜索bfs：与深度优先搜索不同的是，广度优先搜索会先将与起始点距离较近的点搜索完毕，再继续搜索较远的点，而深搜却是沿着一个分支搜到最后。

bfs 从起点开始，优先搜索离起点最近的点，然后由这个最近的点扩展其他稍近的点，这样一层一层的扩展。

边权 = 1

2、广度优先搜索BFS步骤

BFS需要借助队列来实现

初始的时候把起始点放到队列中，并标记起点访问。
如果队列不为空，从队列中取出一个元素x，否则算法结束。
访问和x相连的所有点v，如果v没有被访问，把v入队，并标记已经访问
重复执行步骤2。

c++

void bfs(起始点) {
    将起始点放入队列中；
    标记起点访问；
    while(如果队列不为空) {
        访问队首元素x；
        删除队首元素；
        for(x的相邻点v) {
            if(v没被标记) {
                v加入队尾并标记；
            }
        }
    }
    队列为空，宽搜结束；
}

例题

1.走迷宫

题目

代码

c++

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII; //pair<int, int> 是 C++ 中的标准库类型，用于表示两个值的有序对。

const int N = 110;

int n, m;
int g[N][N], d[N][N];

int bfs()
{
    queue<PII> q;
    queue<pair<int,int>> q;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0, 0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n - 1][m - 1];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    cout << bfs() << endl;

    return 0;
}

2.八数码

题目

代码

c++

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int bfs(string start)
{
	string end = "12345678x";

	queue<string> q;
	unordered_map<string, int> d;

	q.push(start); //start 存 队列
	d[start] = 0; //起点到起点 = 0 初始化

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while(q.size())
    {
    	auto t = q.front();//存队首
    	q.pop();

    	int distance = d[t];//记录步数
    	if(t == end) return distance;

    	// 状态转移 // 一维变二维

    	int k = t.find('x');
    	int x = k /3;
    	int y = k %3;
    	for(int i = 0; i < 4; i++)
    	{
    		int  a  = x + dx[i],b = y + dy[i]; //记录 x 周围的
    		if(a >= 0 && a < 3 && b >= 0 && b < 3)
    		{
    			swap(t[k],t[a*3+b]);//交换 x 和 周围的数字  状态更新
    			if(!d.count(t))// 没有找到过的一个 //交换之后查哈希表，发现没有之前没有出现该字符串，就将“最少交换次数”更新；
    			{
    				d[t] = distance + 1;
    				q.push(t); //把新的状态加入队列 
    			}
    			swap(t[k],t[a*3+b]); //状态恢复
    		}
    	} 

    }
    return -1;
}

int main()
{
	string start;
	for(int i = 0 ;i < 9;i++)
	{
		char c;
		cin>>c;
		start +=c;
	}
	cout<<bfs(start)<<endl;
}

3.B3626跳跃机器人

题目

代码

c++

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1000000; 

bool book[N];
int n;

struct node {
    int x,step;
};

//不越界，并且这个点没有访问过
bool judge(int x) {
    return x >= 1 && x <= n && !book[x]; 
}

int bfs(int a) {
    queue<node> q;
    q.push({1,0});  
    book[0] = true;

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        int dx[] = {-1,1,t.x};

        for (int i = 0; i < 3; i++) {
            int tx = t.x + dx[i];

            if (judge(tx)) {
                book[tx] = true;
                q.push({tx, t.step + 1}); //步数更新+1

                if (tx == n) { //走到终点
                    return t.step + 1;
                }
            }
        }
    }

    return -1; // 没有找到路径
}

int main() {
    memset(book, false, sizeof(book));

    cin >> n;
    int result1 = bfs(n);

    cout << result1 << endl;

    return 0;
}

4.P1747 好奇怪的游戏

题目

代码

c++

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 20; 

bool book[N][N];//标记
int m, n, p, q;


//马不仅可以走日，也可以走田，所以一共有12个方向
int dx[] = {-1, -2, -2, -2, -2, -1, 1, 2, 2, 2, 2, 1};
int dy[] = {2, 2, 1, -1, -2, -2, -2, -2, -1, 1, 2, 2};

struct node {
    int x, y, step;
};

//不越界，并且这个点没有访问过
bool judge(int x, int y) {
    return x >= 1 && x <= N && y >= 1 && y <= N && !book[x][y]; 
}

int bfs(int a, int b) {
    queue<node> q;
    q.push({a, b, 0}); //开始的点（a,b）开始到开始的距离 
    book[a][b] = true;

    while (!q.empty()) {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 12; i++) { //找下一个点
            int tx = t.x + dx[i];
            int ty = t.y + dy[i]; 

            if (judge(tx, ty)) {
                book[tx][ty] = true;
                q.push({tx, ty, t.step + 1}); //步数更新+1

                if (tx == 1 && ty == 1) { //走到终点
                    return t.step + 1;
                }
            }
        }
    }

    return -1; // 没有找到路径
}

int main() {
    memset(book, false, sizeof(book));

    cin >> m >> n;
    int result1 = bfs(m, n);

    memset(book, false, sizeof(book));

    cin >> p >> q;
    int result2 = bfs(p, q);

    cout << result1 << endl;
    cout << result2 << endl;

    return 0;
}

树与图的深度优先遍历

例题

1.树的重心

题目

代码

c++

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N *2;

int h[N]; //h[] 表示节点索引 //head
int e[M]; //e[] 表示idx条边的结束节点是什么 节点的值
int ne[M]; //ne[] 表示idx条边的同起点的下一条边的idx 节点的next指针
int idx; //idx表示边的索引

bool st[N]; //标记是否遍历

int n,m;

int ans = N;

void add(int a,int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

//以u为根的子树中点的数量
int dfs(int u)
{
	st[u] = true; //标记已经被搜过
	int sum = 1;//当前子树的大小(节点数)
	int res = 0;// 删除该点，每一个连通块的最大值
    for (int i = h[u]; i != -1; i = ne[i]) //遍历u的所有初边
    {
        int j = e[i];
        if (!st[j])
        {
        	int s = dfs(j); //当前子树的大小
        	res = max(s,res);
        	sum +=s; //除了去掉的那个节点的，还剩下的节点数
        } 
    }
    res  = max(n-sum,res);	
    ans = min(ans,res);
    return sum;

}

int main()
{
	cin >> n;
  // 将链表的每个节点都重置为-1， 表示链表节点的终点
	memset(h,-1,sizeof h);
	for(int i = 0;i <n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b); 
		add(b,a); //无向边双向连通
	}
	dfs(1);//从节点1开始搜索（从哪个都行）
	cout<<ans<<endl;
}

树与图的广度优先遍历

例题

1.图中点的层次

题目

代码

c++

  #include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010, M = N *2;

int h[N]; //h[] 表示节点索引 //head
int e[M]; //e[] 表示idx条边的结束节点是什么 节点的值
int ne[M]; //ne[] 表示idx条边的同起点的下一条边的idx 节点的next指针
int idx; //idx表示边的索引

bool st[N]; //标记是否遍历

int n,m;
int d[N];

void add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int bfs()
{
	queue<int> q;
	st[1] = true; // 表示1号点已经被遍历过
	q.push(1);

	memset(d,-1,sizeof d);
	d[1] = 0;

	while (q.size()) {
    	int t = q.front();
    	q.pop();

    	for (int i = h[t]; i != -1; i = ne[i])
    	{
        	int j = e[i];
        	if (!st[j])
        	{
            	st[j] = true; // 表示点j已经被遍历过
            	d[j] = d[t] + 1; 
            	q.push(j);
        	}
    	}
	}	
	return d[n];	
}
int main()
{
	cin >> n >> m;
	memset(h,-1,sizeof h);
	for(int i = 0;i <m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b); 
	}

	cout<<bfs()<<endl;
}

拓扑排序

针对有向图，无向图没有拓扑序列
若一个由图中所有点构成的序列 A满足：对于图中的每条边 (x,y)，x 在 A中都出现在 y之前，则称 A是该图的一个拓扑序列。
每条边从前指向后
不是所有的图都有拓扑序列（有环的图）即有向无环图 - > 拓扑图

例题

1.有向图的拓扑序列

题目

代码

c++

#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];

void add(int a,int b) {
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

bool topsort()
{
	int hh  = 0,tt = -1;
	for(int i = 1;i<=n;i++)
	{
		if(!d[i])
		{
			q[ ++tt] = i; 
		}
	}
	while (hh <<tt)
	{
		int t = q[hh++];
		for(int i = h[t];i!=-1;i = ne[i])
		{
			int j = e[i];
			d[j] --;
			if (d[j] == 0)
			{
				q[++t]  = j;
			}
		}
	}
	return tt == n-1;
}

int main()
{
	cin>>n>>m;

	memset(h,-1,sizeof h);
	for(int i = 0;i < m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	if (topsort())
	{
		for(int i = 0;i<n;i++)
		{
			cout<<q[i]<<" ";
		}
	}
	else puts("-1");
	return 0;
}

模板

树与图的存储

树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(2) 邻接表：

c++

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

树与图的遍历

深度优先遍历

c++

int dfs(int u) {
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

宽度优先遍历

c++

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size()) {
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

拓扑排序

c++

bool topsort() {
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++tt] = i;

    while (hh <= tt) {
        int t = q[hh++];

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

最短路算法

朴素dijkstra算法

c++

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i++) {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化版dijkstra

c++

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue <PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Bellman-Ford算法

c++

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
} edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

spfa 算法（队列优化的Bellman-Ford算法）

c++

nt n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                // 如果队列中已存在j，则不需要将j重复插入
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

spfa判断图中是否存在负环

c++

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa() {
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }

    while (q.size()) {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

Floyd算法

c++

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd() {
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

最小生成树

朴素版prim算法

c++

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim() {
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

Kruskal算法

c++

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator<(const Edge &W) const {
        return w < W.w;
    }
} edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges, edges + m);

    for (int i = 1; i <= n; i++) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt++;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

二分图

染色法判别二分图

c++

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c) {
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (color[j] == -1) {
            if (!dfs(j, !c)) return false;
        } else if (color[j] == c) return false;
    }

    return true;
}

bool check() {
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i++)
        if (color[i] == -1)
            if (!dfs(i, 0)) {
                flag = false;
                break;
            }
    return flag;
}

匈牙利算法

c++

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            st[j] = true;
            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int main() {
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }
}

深度优先搜索dfs ​

深搜概述 ​

例题 ​

1.排列数字 ​

题目 ​

代码 ​

2.枚举元组B3621 ​

题目 ​

代码 ​

广（宽）度优先搜索BFS ​

队列queue ​

1、概述 ​

2、构造 ​

3、使用 ​

广度优先搜索BFS ​

1、广度优先搜索BFS概述 ​

2、广度优先搜索BFS步骤 ​

例题 ​

1.走迷宫 ​

题目 ​

代码 ​

2.八数码 ​

题目 ​

代码 ​

3.B3626跳跃机器人 ​

题目 ​

代码 ​

4.P1747 好奇怪的游戏 ​

​

题目 ​

代码 ​

树与图的深度优先遍历 ​

例题 ​

1.树的重心 ​

题目 ​

代码 ​

树与图的广度优先遍历 ​

例题 ​

1.图中点的层次 ​

题目 ​

代码 ​

拓扑排序 ​

例题 ​

1.有向图的拓扑序列 ​

题目 ​

代码 ​

模板 ​

树与图的存储 ​

树与图的遍历 ​

深度优先遍历 ​

宽度优先遍历 ​

拓扑排序 ​

最短路算法 ​

朴素dijkstra算法 ​

堆优化版dijkstra ​

Bellman-Ford算法 ​

spfa 算法（队列优化的Bellman-Ford算法） ​

spfa判断图中是否存在负环 ​

Floyd算法 ​

最小生成树 ​

朴素版prim算法 ​

Kruskal算法 ​

二分图 ​

染色法判别二分图 ​

匈牙利算法 ​

深度优先搜索dfs

深搜概述

例题

1.排列数字

题目

代码

2.枚举元组B3621

题目

代码

广（宽）度优先搜索BFS

队列queue

1、概述

2、构造

3、使用

广度优先搜索BFS

1、广度优先搜索BFS概述

2、广度优先搜索BFS步骤

例题

1.走迷宫

题目

代码

2.八数码

题目

代码

3.B3626跳跃机器人

题目

代码

4.P1747 好奇怪的游戏

题目

代码

树与图的深度优先遍历

例题

1.树的重心

题目

代码

树与图的广度优先遍历

例题

1.图中点的层次

题目

代码

拓扑排序

例题

1.有向图的拓扑序列

题目

代码

模板

树与图的存储

树与图的遍历

深度优先遍历

宽度优先遍历

拓扑排序

最短路算法

朴素dijkstra算法

堆优化版dijkstra

Bellman-Ford算法

spfa 算法（队列优化的Bellman-Ford算法）

spfa判断图中是否存在负环

Floyd算法

最小生成树

朴素版prim算法

Kruskal算法

二分图

染色法判别二分图

匈牙利算法