图的基本算法集合(最短路径与最小生成树)

1.最短路径算法(DFS 弗洛伊德迪杰斯特拉 Bellman-Ford)

1.1DFS 两点最短路径

其实不只是深度优先搜索，广度优先搜索也可以解决此类问题，这里拿DFS作为介绍，在解决最短路径的问题上，DFS和BFS是差不太多的
思路：从起始节点开始访问所有的与起始节点相邻的边，然后继续搜索直到达到我们想要的cur节点同时维护一个最短路径变量得到答案。

import java.util.Scanner;

public class Map {
    static int n,m,min,finalN;//分别是节点数量 边的数量 以及过程中维护的最小值 以及我们要找的点
    static int inf=99999999;//人为拟定的最大值，我们可以把它看作无穷大 即两个节点之间没有通路
    static int[][] edge=new int[100][100];//邻接矩阵存图数组
    static int[] mark=new int[100];//标记数组
    public static void dfs(int cur,int pathLength){
          if(min<pathLength) return;//终止条件1 当前路径的长度已经超过了维护的最小值
        //终止条件2 当前节点已经来到了我们要找的最终节点
          if(cur==finalN){
              if(min>pathLength) min=pathLength;//维护最小值并return
              return;
          }
          else{
              for(int i=1;i<=n;i++)//dfs for循环部分 遍历所有的可能
              {
                  //如果存在通路并且没有走过并且不是走当前节点
                  if(edge[cur][i]!=inf && edge[cur][i]!=0 &&mark[i]==0){
                      mark[i]=1;
                      dfs(i,pathLength+edge[cur][i]);
                      mark[i]=0;//dfs回溯过程
                  }
              }
          }
          return;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        finalN=sc.nextInt();
        //邻接矩阵初始化过程 我们让每两个节点之间的距离都等于inf 然后让每个节点走到自己的路径为0
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                edge[i][j]=inf;
            }
            edge[i][i]=0;
        }
        int a,b;
        //存入我们要输入的边
        while(m--!=0)
        {
            a=sc.nextInt();
            b=sc.nextInt();
            edge[a][b]=sc.nextInt();
        }
        min=inf;
        mark[1]=1;
        dfs(1,0);
        System.out.println(min);
    }
}

我们要查阅哪两个点只需要控制dfs的起始条件和finalN的值就可以了，但是细心的小伙伴可能会发现，我们循环退出的条件是当前的路径大于了维护的最小路径值，所以我们不进行下一次的for循环，但是想一想，如果我们的图中存在负值的边，那么当前的路径值进行循环以后就可能比最短路径小了，所以说我们进行dfs加入这个终止条件的时候我们就没办法维护负权值的边了，所以我们如果有负权值的边，就不应该让循环因为这个终止，我们只加入终止条件2即可，这里不考虑最终节点邻接的边还有负权值的情况，想一想如果我们可以通过终点走一个负值的边然后再回到终点，如果距离可以被缩小，那么路径值的总和就可以一直被缩小了也就没有研究的价值了。

1.2弗洛伊德算法多源最短路径

佛洛依德算法是在我看来解决最短路径的最暴力的算法，但他可以解决多源的最短路径即任意两点之间的最短路径都可以得到，代码也非常的简单。
思路：首先我们只允许经过节点1进行中转求出各个节点的最短路程，然后我们允许经过节点1和2进行中转重复求最短路径，一直到允许经过所有节点进行中转的时候，我们维护出的最短路径就是严格最短的路径了，我们可以通过弗洛伊德算法解决带有负值边的部分图如果是负值单向边是可以的如果是负值回路则解决不了换句话说负权值环路不存在最小值的
这里只附核心代码其它构造图的过程与第一个是一样的

    public static void Floyd(){
        //第一重循环代表了以哪个点作为中转 由于我们每维护完一轮最外层的循环就相当于是以一个点作为中转
        //所以我们可以使用for循环来模拟以点1为中转，以点1，2为中转....这样的过程
        //通俗点说就是 第一轮维护完了相当于是各个点经过点1以后得到的最短路径并且保留了下来 当我们再维护以点2为中转
        //那是不是就相当于每个点以1，2为中转的最小值了呢？对吧
        for(int k = 1; k <= n; k++){
        //后面两重循环就相当于是遍历矩阵
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                //更新值的操作
                    if(edge[i][k] < inf && edge[k][j] < inf && edge[i][j] > edge[i][k] + edge[k][j])
                        edge[i][j] = edge[i][k] + edge[k][j];
                }
            }
        }
    }

1.3迪杰斯特拉算法单源最短路径

如果说弗洛伊德是一种规划的思想，那么迪杰斯特拉就是一种贪心算法
需要注意的是迪杰斯特拉由于是一种贪心算法，所以有些情况无法进行计算，它解决不了解决不了解决不了带有负权边的图！具体原因下面再做说明

思路：我们从一个节点开始每次找到距离这个节点最近的一条边，我们认为这条边不需要维护了就是最短的值，然后我们标记这个点表示已经使用过，然后再以这个点为中转点更新其它路径的值，然后再拿一条最短的边，重复上述操作，想一想如果边都是正值的话是不是很完美的可以求出以起始点为起点到其它所有点的最短路径的值，但是如果有边是负值呢？
比如我们当前节点1到节点3的值是-2 节点1到节点2的值是-1 节点2到节点3的值是-2 我们从节点1出发的时候显然不会先走-1值的边再更新得到1-3的值为-3 而是直接选择1-3为-2的边再进行下一步操作所以说解决不了带有负值的问题

      public static int[] Dijkstra(int start){
        //start为起始点
        //dis即最后需要的单源最短路径数组
        int[] dis=new int[n+1];
        //初始化dis数组
        for(int i=1;i<=n;i++) dis[i]=edge[start][i];
        //标记起点已经走过
        mark[start]=1;
        //维护每次取到的最短边对应的另一个点
        int u=-1;
        //维护最短边 并且记录最小节点
        for(int i=1;i<=n-1;i++) {
            min = inf;
            for (int j = 1; j <= n; j++) {
                if (mark[j] == 0 && dis[j] < min) {
                    min = dis[j];
                    u = j;
                }
            }
            mark[u]=1;
            //以最小点再进行一轮松弛操作
            for (int k = 1; k <= n; k++) {
                if (edge[u][k] < inf && mark[k] == 0) {
                    if (dis[k] > dis[u] + edge[u][k])
                        dis[k] = dis[u] + edge[u][k];
                }
            }
        }
       return dis;
    }

1.4Bellman-Floyd 解决带有负权边的问题

Bellman-Floyd算法我看来它很像是BFS的思想
思路：我们把图存入到三个数组中这里我们设置为s[] e[] w[]
分别是起点终点权值然后每次检索所有的边进行松弛操作进行n-1轮松弛以后就可以得到我们想要的单源最短路径而这种算法就不会出现迪杰斯特拉会出现的带负权边计算错误的问题大家看思路可能会不太理解我会在代码中在做陈述

    public static int[] Bellman_Floyd(int start){
        int[] dis=new int[n+1];
        for(int i=1;i<=n;i++) dis[i]=inf;
        //初始化让自己可以走到自己
        dis[start]=0;
        //想一想如果有从起始点可以走到的边 那么第一次循环的时候由于dis[start]=0了 那么我们就可以得到从起始点走一步可以到其它点的最短路径
        //如果继续循环 我们走一步能到的距离已经更新了 那么通过第二次循环就可以得到走两步的点 我就是这么理解的 大家也可以自己模拟模拟
        for(int j=1;j<=n-1;j++)
        {
            for(int i=1;i<=m;i++)
            {
                if(dis[e[i]]>dis[s[i]]+w[i])
                    dis[e[i]]=dis[s[i]]+w[i];
            }
        }
        return dis;
    }

另外这种算法还可以知道有没有负权回路假设我们走了n步了再走一步如果还有点的距离可以被更新的话那么就存在负权回路了但是我们说有负权回路那么研究最小值也变得没了意义实际问题中负权值几乎很少出现
另外 Bellman-Floyd算法是最多进行n-1次松弛操作假设松弛操作没有意义了，有些节点已经到达了最小值就不需要再继续进行松弛，我们可以设计一个队列，每次只对最小值发生变化的节点再进行松弛操作就可以简化时间这个叫做Bellman-Floyd算法的队列优化大家有兴趣可以查阅资料

2.最小生成树

当然最小生成树也可以使用搜索的方法来遍历所有的路径进行计算但那样很费时间于是我们介绍下面两种最小生成树常用算法

2.1克鲁斯卡尔算法

思路：首先我们将所有边以权值排序接着一条一条选择如果当前选择的边不会使我们的最小生成树构成回路则加入这条边持续选择直到n-1条边为止
我们如何知道加入的新边不会构成回路呢？
我们要知道不会构成回路，就需要知道这条边的两个节点是不是已经用过了
如果两个节点都用过了的话，那么我们再加入新边就会导致最小生成树生成失败，于是我们这里需要用到一种数据结构叫做并查集，即维护所有节点的根源，我们一开始让所有节点的根源是自己，如果加入一条边就让边的end节点归顺于start节点如果两个节点的并查集的值是一样的说明两个节点此时已经连通了

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
//定义一个类存边
class edge{
    int u;
    int v;
    int w;

    @Override
    public String toString() {
        return "edge{" +
                "u=" + u +
                ", v=" + v +
                ", w=" + w +
                '}';
    }
}
public class Kruskal {
    static edge[] e=new edge[100];
    static int n,m;
    //并查集数组
    static int[] f=new int[100];
    static int sum=0,count=0;
    //并查集得到祖先的方法
    public static int getf(int v)
    {
        if(f[v]==v)
            return v;
        else
            f[v]=getf(f[v]);
        return f[v];
    }
    //查找祖先并决定是否可以加入边的方法
    public static int merge(int v,int u)
    {
        int t1;
        int t2;
        t1=getf(v);
        t2=getf(u);
        //如果不一样 就让end节点归顺于start 返回1代表可行
        if(t1!=t2)
        {
            f[t2]=t1;
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=1;i<=m;i++)
        {
            e[i]=new edge();//自定义类型数组初始化
            //存边
            e[i].u=sc.nextInt();
            e[i].v=sc.nextInt();
            e[i].w=sc.nextInt();
        }
        //重写接口排序 以w即权值为对象 对[1,m]下标排序
        Arrays.sort(e,1,m+1, new Comparator<edge>() {
            @Override
            public int compare(edge o1, edge o2) {
                return o1.w-o2.w;
            }
        });
       // System.out.println(Arrays.toString(e));
        for(int i=1;i<=n;i++) f[i]=i;
        //核心部分
        for(int i=1;i<=m;i++)
        {
            if(merge(e[i].u,e[i].v)==1)
            {
                count++;
                sum=sum+e[i].w;
            }
            //n-1个节点则退出
            if(count==n-1) break;
        }
        System.out.println(sum);

    }
}

2.2Prim算法

思路：以一个节点为起始节点每一次加入距离最短的节点再更新与其它节点的距离，然后再加入一个距离最短的节点直到加入n个节点为止想一想这是不是与迪杰斯特拉的算法思维很像呢
迪杰斯特拉也是这样维护但是最后维护的是一个数组即单源最短路径如果我们对这个过程稍加修改就可以得到最小生成树

    public static int Prim(int start){
        int sum=0;//要维护的权值和 
        int count = 0;
        //start为起始点
        //dis单源最短路径数组
        int[] dis=new int[n+1];
        //初始化dis数组
        for(int i=1;i<=n;i++) dis[i]=edge[start][i];
        //标记起点已经走过
        mark[start]=1;
        //维护每次取到的最短边对应的另一个点
        int u=-1;
        //维护最短边 并且记录最小节点
        count++;
        //n个节点就可以不用继续循环了
        while(count<n) {
            min = inf;
            for (int j = 1; j <= n; j++) {
                if (mark[j] == 0 && dis[j] < min) {
                    min = dis[j];
                    u = j;
                }
            }
            mark[u]=1;count++;sum+=dis[u];
            //System.out.println(dis[u]);
            //以最小点再进行一轮松弛操作
            //不同于迪杰斯特拉的是，我们的最小生成树
            //每次要加的只有进行松弛操作的两点间的距离
            //而不是起始点到终点的距离，所以dis数组
            //**维护的是点到当前已经生成的树的距离**
            //所以更新操作也对应着有所改变
            for (int k = 1; k <= n; k++) {
                if (edge[u][k] < inf && mark[k] == 0) {
                    if (dis[k] >  edge[u][k])
                        dis[k] =  edge[u][k];
                }
            }
        }
        return sum;
    }