图论入门

图论的存储

我们采用一种类似邻接表的形式进行存储，一个数组进行输入和存储原始数据，另一个可以开一个可变长的vector用于保存我们这个点可以通向哪个点。

int fa[1100];
vector<int> a[1100];

树的遍历（DFS，BFS）

很基本直接平推即可，由于不存在环的问题，所以很简单。

题目描述

给定一棵大小为n，根为1的树，求出其dfs序、bfs序。

请将所有出点按照编号从小到大排序后进行遍历。

解释：dfs为深度优先搜索，bfs为宽度优先搜索。输入格式个整数n，表示点的个数。（1≤n≤50)

接下来一行n-1个整数，第i个数字fa表示点i的父亲。

（1＜fa≤n)输出格式第一行输出dfs序，第二行输出bfs序。

样例输入1

4

112

样例输出1

1243

1234

样例输入2

5

1224

样例输出2

12345

12345

#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int fa[1100];
vector<int> a[1100];
void dfs(int x){
    cout<<x<<' ';
    for(auto &y : a[x])dfs(y);
}

void bfs(int x) {
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int t = q.front();
        cout<<t<<' ';
        q.pop();
        for (auto &y : a[t]) {
            q.push(y);
        }
    }
}
int main(){
    int n;
    cin>>n;
    // 读入father数组
    for(int i = 2;i <= n;i++)cin>>fa[i];
    // 读入每个节点的子节点，并将其存入对应的数组中
    for(int i = 2;i<=n;i++) a[fa[i]].push_back(i);
    // 对每个节点的子节点进行排序
    for(int i = 1;i<=n;i++) sort(a[i].begin(),a[i].end());
    dfs(1);
    cout<< endl;
    bfs(1);
    return 0;
}

图的遍历

图中可能存在环的问题所以我们会采用一个visted数据记录我们走过的位置。

DFS解法(与之前树的DFS思路相同，只是在那个基础上加了一个visited数组)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
bitset<N> visted;
vector<int> a[N];//记得别开的太小哦
//这个地方的写法多种多样。
void dfs(int x){
    visted[x] = true;
    for(auto &y : a[x]){
        if (visted[y])continue;
        dfs(y);
    }
}

int main(){
    cout.tie(0),cin.tie(0),ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= m; i++){
        int c,b;
        cin>>c>>b;
        if(c!=b)
        a[c].push_back(b);
    }
    dfs(1);
    //减少时间复杂度，我们可以直接采用桶排的思想。
    for (int i = 1; i <= n; ++i) {
        if(visted[i]){
            cout<<i<<" ";
        }
    }
    return 0;
}

BFS解法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
bitset<N> visted;
vector<int> a[N];
void bfs(int x){
    queue<int> q;
    q.push(x);
    while (!q.empty()){
        int t = q.front();
        if(visted[t])return;
        visted[t] = true;
        q.pop();
        for (auto &y : a[t]) {
            bfs(y);
        }
    }
}

int main(){
    cout.tie(0),cin.tie(0),ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= m; i++){
        int c,b;
        cin>>c>>b;
        if(c!=b)
        a[c].push_back(b);
    }
    bfs(1);
    for (int i = 1; i <= n; ++i) {
        if(visted[i]){
            cout<<i<<" ";
        }
    }
    return 0;
}

全排列

全排列本身就是一种树状结构可以解决的问题。我们解决算法问题归根结底就是将我们的思路清晰的写发给计算机。

我们只要一路搜索找到a4我们就会意识到我们应该返回了，所以这个地方我们要使用的应该是dfs，而因为还需要返回，所以我们还要使用一下回溯的思想，同时我们如果不进行剪枝操作的话，这的时间复杂度在n的n次方，大概到10就会超时，所以我们要进行剪枝操作。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
bitset<N> visted;
//vector<int> a[N];
int a[N];
int n;
void dfs(int depth){
    //如果深度等于n+1，则输出排列,相当于我们上面图中说的终止条件
    if(depth == n+1){
        for (int i = 1; i <= n; ++i) {
            if(i == n)cout<<a[i]<<'\n';
            else cout<<a[i]<<' ';
            //return;
        }
    }
    //遍历1到n，如果已经访问过，则跳过
    for(int i =1;i<=n;i++){
        //利用这个条件进行剪枝操作
        if(visted[i])continue;
        //标记为已访问
        visted[i] = true;
        //将当前数字放到排列的当前位置
        a[depth] = i;
        //递归调用
        dfs(depth+1);
        //恢复现场
        //回溯，即撤销刚才的访问标记
        //标记为未访问
        visted[i] = false;
        //将当前位置的数字置为0
        a[depth] = 0;

    }
}

int main(){
    cout.tie(0),cin.tie(0),ios::sync_with_stdio(false);
    cin>>n;
    dfs(1);
}

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

const int N=1e3+10;
int a[N][N],n,m;

int d[N][N];

bool vis[N][N];

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

int mn=10000;

bool inarr(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=m;
}

void dfs(int x,int y)
{
    if(x==n&&y==m)
    {
        mn=min(mn,d[x][y]);
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(inarr(nx,ny)&&!vis[nx][ny]&&!a[nx][ny])
        {
            d[nx][ny]=d[x][y]+1;
            vis[nx][ny]=true;
            dfs(nx,ny);
            vis[nx][ny]=false;
        }
    }
}

void bfs()
{
    queue <pair<int,int> > qu;
    qu.push({1,1});
    vis[1][1]=true;
    while(qu.size()){
        int x=qu.front().first;int y=qu.front().second;
        qu.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(inarr(nx,ny)&&!vis[nx][ny]&&!a[nx][ny]){
                d[nx][ny]=d[x][y]+1;
                vis[nx][ny]=true;
                qu.push({nx,ny});
            }
        }
    }

}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    bfs();
    if(d[n][m])
        cout<<d[n][m];
    else
        cout<<-1;
}