图论与图搜索

关于图论的知识很早就想给自己做一个整理，关于图的知识，应该是算法与数据结构里面最有意思的一部分了，也是我个人很喜欢的一块。之前一直觉得自己水平不够，写得不好。前几天参加数学建模的竞赛，拿到的题目的本质就是一道图搜索的题目。于是，比赛的时候恶补了一波，赛后又总结了一下。于是，把自己总结的贴在这里，做一个记录。

图的本质，描述的是一堆点与点的关系，这个点可以是道路结点，也可以是人，也可以是其他实体。

下面是我想写的：

1. 递归
2. 深度遍历和广度遍历
3. 全排列和组合问题
4. 八皇后问题
5. A-star 算法

---

1. 递归和回溯

对于递归，如果这个问题，可以被调用自身并且在每一次调用的过程里面问题的规模还在不断的减少，那么这个递归的方法可以来解决这个问题。

举个典型的例子，二分查找，代码如下：

int binarySearch(int * arr ,int begin ,int end,int key){
    //递归的减枝条件
    //pass
    
    
    //递归结束条件
    if (begin >end  ){
        return -1
    }

    //找到解的情况
    if(key==arr[(end-begin)/2+begin]){
         return (end-begin)/2+begin;
    }

    //进入下一波递归
    if(key <arr[(end-begin)/2+begin] ){
         binarySearch(arr,begin,mid-1,key);
    }
    else{
        binarySearch(arr,mid+1,end,key);
    }
}

写一个递归的代码，我的理解是从四点入手，

1. 递归结束的条件是什么
2. 进入下一层递归的条件是什么
3. 找到解的情况
4. 为了减少搜索的规模，可以考虑减枝。减枝有两种，一种是合法性的减枝，一种是能够减少搜索规模的减枝

下面写一个其他的，组合问题。

LeetCode78:Subsets 
For example, 
If nums = [1,2,3], a solution is:
[ 
[3], 
[1], 
[2], 
[1,2,3], 
[1,3], 
[2,3], 
[1,2], 
[] 
]

思路：
对于一个元素，有两种选择，一种是把这个元素加入到当前的集合然后处理后面的元素，另一个是不把这个元素加入到当前结合然后处理后面的元素。

完全满足递归的思想：

1. 可以调用自身
2. 问题的规模在变小

so，代码如下：

#include <iostream>
#include <vector>
using namespace std;

void print_res(vector<vector<char>> &ans, vector<int> &path,vector<char> vc){
    //以print的方式输出
    for (int i=0;i<path.size();i++){
        if(path[i]==1){
            cout<<vc[i]<<"  ";
        }
    }
    cout<<endl;

    //将结果pushbach到ans里面
    vector<char> row;
    for (int i=0;i<path.size();i++){
        if(path[i]==1){
             row.push_back(vc[i]);
        }
    }
    ans.push_back(row);
}

void dfs(vector<vector<char>> &ans ,vector<int> path,int index ,vector<char> &vc ){
    //减枝
    if (index >vc.size()){
        return ;  //剪枝 表示结束，需要return
    }
    //找到结果
    if(index==vc.size()){
        print_res(ans,path,vc);
        return;  //找到结果，也意味着这一层的搜索结束，然后return
    }
    //进入下一层的递归，进入递归之后，创建两个机器人干活，一个机器人取当前元素加入集合干活，另外一个机器人不取当前元素加入集合，然后干活
    //取  创建一个机器人，进入递归干活
    path[index]=1;
    dfs(ans,path,index+1,vc);
    // 对于进入递归之后，从递归出来，一定要记的清楚上一次递归的状态，这个非常非常的重要!!!! 
    path[index]=0;
    //不取 
    dfs(ans,path,index+1,vc);
}

vector<vector<char>>  subset(vector<char> & vc){
    vector<vector <char>> ans;
    vector<int> path(vc.size(),-1);
    int index=0;

    //进入递归
    //取当前元素，进入递归
    path[index]=1;
    dfs(ans,path,index+1,vc);

    //对于进入递归之后，从递归出来，一定要记的清楚上一次递归的状态，这个非常非常的重要!!!! 
    path[index]=0;
    //不取当前元素，进入递归
    dfs(ans,path,index+1,vc);
    return ans;
}

int main(){
    vector<char> vc;
    vc.push_back('a');
    vc.push_back('b');
    vc.push_back('c');
    vc.push_back('d');
    vector<vector <char>> ans=subset(vc);
    return 0;
}

image.png

深度优先遍历和广度优先遍历

深度优先遍历和广度优先遍历的算法本身并不是很难，很多书已经写的很好了。但是，深度优先的实现可以解决很多除了图遍历之外，还很适合解决很多搜索类的问题。而dfs的本质，也是一种递归。

看看八皇后问题

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

这个问题，在搜索所有的状态空间，时间复杂度是O(N^N)。搜索过程，如下：

草图.png

#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>  

using namespace std;

//记录一下结果的个数
int times=0;

void print_res(vector<int> path ){
    times++;
    for (auto it =path.begin();it!=path.end();it++){
        cout<<*it<<"  ";
    }
    cout<<endl;
}

bool isHang(vector<int> path){
    set<int> path_set;

    for (auto it =path.begin();it!=path.end();it++){
        path_set.insert(*it);
    }

    if(path_set.size()==path.size()){
        return true;
    }
    else{
        return false;
    }
}

bool isXiexian(vector<int> path){
    for(int i=0;i<path.size()-1;i++){
        for(int j=i+1;j<path.size();j++){
            if(abs(path[i]-path[j])==abs(i-j) ){
                return false;
            }
        }
    }
    return true;
}

void dfs(int index,int n,vector<int> path){

    //找到结果 
    if(index==n){
        //判断结果的合法性

        if(isHang(path) && isXiexian(path)){
            print_res(path);
        }
        return ;
    }


    //进入下一层递归
    for(int i=0;i<n;i++){
        path[index]=i;
        dfs(index+1,n,path);
        path[index]=-1;
    }
}

void n_queen(int n){
    vector<int> path(n,-1);
    int index=0;
    for(int i=0;i<n;i++){
        path[index]=i;
        dfs(index+1,n,path);

        //清除上一次进入递归的状态
        path[index]=-1;
    }
}

int main(){
    const int n=8;
    n_queen(n);
    cout<<endl;
    cout<<"times : "<<times<<endl;
    return 0;
}

A-star 算法

to-do