图论算法

作者: 漫游之光 | 来源:发表于2018-09-13 09:59 被阅读0次

图论算法
图论算法
图论——A*算法
图论算法
[算法] 图论
图论算法
[图论算法]Prim算法
图论：Dijkstra算法
图论(1)-tarjan算法求强联通分量，割点，桥
Union-Find算法详解

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为 $G(V, E)$ ，V是图G中顶点的集合，E是图G中边的集合。图分为无向图和有向图，根据图的边长，又分为带权图与不带权图。

图常用的表示方法有两种，邻接矩阵和邻接表。如果一个图有n个顶点，那么使用邻接矩阵表示为一个n*n的二维数组，数组中 $[i,j]$ 表示从顶点 $i$ 到顶点 $j$ 的边的相关信息。邻接表则表示为n个线性表，第 $i$ 个线性表里的内容代表了和顶点 $i$ 相连的边的信息。

深度优先搜索

在图中进行深搜，一般可以用递归函数实现。如果要判断从某个点V出发能否走到终点，程序框架如下（一开始V是新点）：

bool Dfs(V) {
    if(V是终点) {
        return true;
    }
    if(V是旧点) {
        return false; 
    }
    将V标记为旧点; 
    对和V相邻的每一个结点U{
        if(Dfs(U) == true){
            return true;
        }
    } 
    return false;
}

如果要记录从起点到终点的路径，则需要一个数组path来记录一路走过的每一个结点，还需要一个变量depth来记录当前的深度（从出发起走到当前结点的步数）。深度可以不作为全局变量而写成Dfs()的参数。假设结点的类型是Node，则程序的框架如下：

Node path[MAX_LEN]
int depth;

bool Dfs(V) {
    if(V是终点) {
        path[depth] = V;
        return true;
    }
    if(V是旧点) {
        return false; 
    }
    path[depth] = V;
    depth++; 
    将V标记为旧点; 
    对和V相邻的每一个结点U{
        if(Dfs(U) == true){
            return true;
        }
    } 
    //如果需要从这里返回false，证明了从这个点到不了终点
    //要删除这个点 
    depth--; 
    return false;
}

int main(){
    将所有点都标记为新点；
    depth = 0;
    if(Dfs(起点)){
        for(int i = 0;i <= depth;depth++){
            cout<<path[i]<<endl;
        }
    } 
    return 0;
}

把图中的所有结点都走一遍，这叫做遍历一个图。可以用深度优先搜索的方法遍历一个图，遍历图的代码框架如下：

Dfs(V){
    if(V是旧点){
        return;
    }
    将V标记为旧点;
    对和V相邻的每一个点U{
        Dfs(U); 
    } 
}

int main(){
    将所有的点都标记为新点;
    while(在图中能找到新点k){
        Dfs(k);
    } 
    return 0;
}

广度优先搜索

广搜的目标是，一旦找到一条查从起点到目标节点的路径，这条路径，这条路径就一定是最优的。使用广搜时需要把节点分层。起点是0层，从起点最少要走n步，且走n步就一定能到达的节点就是第n层。广搜就是按层次从低到高依次扩展结点，拓展出来的结点要用队列存。

把初始结点（起点）S0放入Open表中，Open表是一个队列。
如果Open表为空，则问题无解，失败退出。
把Open表头部结点v取出放入Closed表。
考察结点v是否为目标结点（终点）。若是，则得到问题的解，转到步骤7。
若结点n不可扩展，则转到步骤2。
扩展结点v，将其不在Closed表和Open表中的相邻结点放入Open表的尾部，并在刚扩展出来的结点中存储直线该结点的父节点的指针以及该结点的层次，然后转到步骤2。
广搜成功结束。根据终点v中存放的层次信息，就可知道从S0走到v的最佳路径有几步。根据父节点的指针信息一步步倒着查，就能找到S0到v的路径。

判断有向图中是否有环路

这里可以使用深度优先搜索，也可以使用广度优先搜索。使用深度优先搜索，算法如下：在深度优先搜索时，如果正在搜索的某一个顶点（还没有退出该顶点的深度优先搜索），又回到了该顶点，即证明该图有环。这里其实和深度优先搜索基本一致，需要修改的主要地方是，记录是否遍历过该顶点的遍历需要有三种情况，未遍历，已经遍历过了和正在遍历。

使用广度优先搜索解决这个问题，需要修改的地方稍微多一点。在广度优先搜索时，先将入度为0（指向该顶点的顶点数为0）的顶点加入到队列中。在队列中取出一个顶点时，它指向的所有顶点的入度减一，如此时指向顶点的入度为0，则添加至队列。当广度优先搜索完成时，如果所有顶点的入度都为0，则图无环，否则，图有环。

旅行商问题（动态规划解法）

一个售货员必须访问n个城市，恰好访问每个城市一次，并最终回到出发城市。售货员从城市i到城市j的旅行费用是一个整数，旅行所需的全部费用是他旅行经过的的各边费用之和，而售货员希望使整个旅行费用最低。

下面给出的这个解法是一个动态规划的解法，这个解法只适用于数据量比较小的情况。其实以前我根本就没有看这个问题，直到看到字节跳动的笔试在考这个问题，我才发现原来这种解法并不难，如果看过，在笔试的时候，应该能写出来，但如果没看过，估计只能用暴力枚举了（能过50%），所以，还是要多多积累。

int getMinPath(vector<vector<int>> &graph){
    const int MAX = 0x0fffffff;
    int n = graph.size();
    int stateNum = 1 << n;
    // dp[i][j]中的i是一个二进制形式的数，表示经过城市的集合，如0111表示经过了城市0,1,2
    // dp[i][j]表示经过了i中的城市，并且以j结尾的路径长度
    vector<vector<int> > dp(stateNum,vector<int>(n,MAX));
    dp[1][0] = 0; //从城市0出发，所以经过城市0，以城市0结尾的路径为0
    //从城市0出发，更新和其他城市的距离
    for(int i=1;i<stateNum;i++){
        for(int j=0;j<n;j++){
            if(dp[i][j] != MAX){ //如果已经访问过
                for(int k=0;k<n;k++){
                    if( (i & (1 << k) ) == 0){ 
                        //没有访问过k，且从这里到k的距离小于原来的距离，则更新
                        dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j] + graph[j][k]);
                    }
                }
            }
        }
    }
    int res = MAX;
    for(int i=1;i<n;i++){
        res = min(res,dp[stateNum-1][i] + graph[i][0]);
    }
    return res;
}