《啊哈算法》的Java实现 |第八章：更多精彩算法

《啊哈算法》的Java现实 | 第一章：排序.
《啊哈算法》的Java现实 | 第二章：栈、队列、链表.
《啊哈算法》的Java现实 | 第三章：枚举！很暴力.
《啊哈算法》的java实现 | 第四章：万能的搜索.
《啊哈算法》的Java实现| 第五章：图.
《啊哈算法》的Java实现 | 第六章 ：最短路径及最短路径算法的对比分析.
《啊哈算法》的Java实现 | 第七章：神奇的树.
《啊哈算法》的Java实现 |第八章：更多精彩算法.

• 啊哈算法ch8
• • 图的最小生成树
  • 再谈最小生成树
  • • 改进算法
  • 重要城市-图的割点
  • 关键道路-用Tarjan算法求图的割边
  • 我要做月老-二分图最大匹配

package ch8;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class TUTest01 {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int m = scanner.nextInt();
    static int sum = 0;
    static int count =0;
    static int[] f = new int[n+1];
    static edge[] edges = new edge[m+1];
    public static void main(String[] args) {
      for (int i =1;i<=m;i++){
          int u = scanner.nextInt();
          int v = scanner.nextInt();
          int w = scanner.nextInt();
          edges[i] = new edge(u,v,w);
      }
      scanner.close();
      quicksort(1,m);
      for (int i =1;i<=n;i++){
          f[i]  =i;//初始化并查集
      }
      for (int i =1;i<=m;i++){
          if (merge(edges[i].u,edges[i].v)){//如果没有连通则选择这条边
              count++;
              sum = sum + edges[i].w;
          }
          if (count==n-1){
              break;
          }
      }
        System.out.println(sum);

    }
    public static void quicksort(int left,int right){
        if (left>right)return;
        int i = left;
        int j = right;
        while(i!=j){
            while(edges[j].w >= edges[left].w && i 
时间复杂度为O(MlogM)
 
再谈最小生成树 
package ch8;

import java.util.Scanner;

public class TUTest02 {
    static Scanner scanner = new Scanner(System.in);
    static int inf = 99999;
    static int count = 0, sum = 0;
    static int n = scanner.nextInt();
    static int m = scanner.nextInt();
    static int[][] e = new int[n+1][n+1];
    static int[] dis = new int[n+1];
    static int[] book = new int[n+1];

    public static void main(String[] args) {
        for (int i =1;i<=n;i++){
            for (int j =1;j<=n;j++){
                if (i==j) e[i][j] = 0;
                else e[i][j] = inf;
            }
        }
        for (int i = 1; i<=m; i++){
            int t1 = scanner.nextInt();
            int t2 = scanner.nextInt();
            int t3 = scanner.nextInt();
            e[t1][t2] = t3;
            e[t2][t1] = t3; //这里是无向图，两个方向的都要写
        }
        for (int i =1;i<=n;i++){
            dis[i] = e[1][i];//初始化dis数组，这里的生成树目前只有一号，所有要初始化一号顶点到各个顶点的距离
        }
        //初始化book，这里的book用来记录哪些点加入了生成树
        for (int i =1;i<=n;i++){
            book[i] = 0;
        }
        book[1] = 1;
        int j = 0;
        count ++;//用来记录生成树中的定点数，现在+1为1个
        while(count e[j][k])
                    dis[k] = e[j][k];
            }
        }

        System.out.println(sum);
    }
}
 
时间复杂度为O（N2）
 
改进算法 
package ch8;

import java.util.Scanner;

public class TUTest03  {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int m = scanner.nextInt();
    static int[] dis = new int[n+1];
    static int[] book = new int[n+1];
    static int[] h = new int[n+1];//用来保存堆
    static int[] pos  = new int[n+1];//用来保存每个顶点在堆中位置
    static int size;

    
    public static void swap(int x,int y){
        int t = h[x];
        h[x] = h[y];
        h[y] = t;

        //同步更新pos
        t = pos[h[x]];
        pos[h[x]] = pos[h[y]];
        pos[h[y]] = t;
    }

    
    public static void siftdown(int i){//传入下一个需要向下调整的结点
        int t,flag = 0;//flage用来标记是否需要继续向下调整
        while(i*2<=size && flag == 0){//首先i下面还需要有子结点，并且需要被调整
            if (dis[h[i]] > dis[h[i*2]]) t = i*2;
            else t = i;
            //右边的子结点
            if (i*2+1 <= size){
                if (dis[h[t]]>dis[h[i*2+1]]) t= i*2+1;
            }
            //如果发现最小结点编号不是自己的，说明子结点中有比父节点更小的
            if (t!=i){
                swap(t,i);//交换堆t和i位置的元素
                i = t;//更新i为刚与它交换子结点的的编号，继续执行
            }else flag = 1;
        }

    }

    
    public static void siftup(int i){
        int flag = 0;
        if (i == 1)return;//如果已经是堆的顶点就不需要调整了
        while(i!=1 && flag == 0){
            //判断是否比父节点小
            if (dis[h[i]] < dis[h[i/2]]) swap(i,i/2);//交换位置
            else flag=1;//表示以及不需要进行调整了
            i= i/2;//更新i的表换为父结点，便于下一次的调整
        }
    }

    
    public static int pop(){
        int t;
        t = h[1];//用一个临时变量来记录堆顶
        h[1] = h[size];//将堆最后一个值复制到堆顶
        pos[h[1]] = 1;
        size --;
        siftdown(1);//每次都把最后一个点赋值到顶点，然后向下调整，并且整个堆的大小-1，剔除掉顶部元素
        return t;

    }

    public static void main(String[] args) {
        int[] u = new int[2*m+1];
        int[] v = new int[2*m+1];
        int[] w = new int[2*m+1];
        int[] first = new int[n+1];
        int[] next = new int[2*m+1];
        int inf = 999999;
        int count = 0;
        int sum = 0;

        //输入边
        for (int i =1; i<=m;i++){
            u[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        scanner.close();
        //因为是无向图，所以需要将所有的边在反向存储一次
        for (int i =m+1; i<=m*2;i++){
            u[i] = v[i-m];
            v[i] = u[i-m];
            w[i] = w[i-m];
        }
        //开始使用邻接表存储边，初始化邻接表
        for (int i =1;i<=n;i++){
            first[i] = -1;//保存顶点为u[i]的第一条边 next保存编号为i的边的下一条边的编号
        }
        //存入值
        for (int i =1; i<= 2*m;i++){
            next[i] = first[u[i]];
            first[u[i]] = i;
        }
        for (int i =1;i<=n;i++){
            book[i] = 0;
        }

        //将1号顶点加入生成树
        book[1] = 1;
        count ++;
        //初始化dis数组
        dis[1] = 0;
        for (int i =2; i<=n;i++){
            dis[i] = inf;
        }
        int k = first[1];
        //初始化dis数组，更新为生成树中只有顶点1时，生成树到各个顶点的距离
        while(k!=-1){
            dis[v[k]] = w[k];
            k = next[k];
        }
        //初始化堆
        size = n;
        for (int i =1;i<=n;i++){
            h[i] = i;
            pos[i] = i;
        }
        for (int i = size/2; i>=1;i--)
            siftdown(i);//调整好整个数
        pop();//弹出栈顶元素，这个元素就是距离生成树最近的元素，这个栈顶元素为1号元素

        while(count < n){
            int j = pop();//弹出一个栈顶元素
            book[j] = 1;//标记 这个元素进入了生成树
            count ++;
            sum  =sum + dis[j];
            //扫描当前顶点j的所有边，进行松弛
            k = first[j];
            while(k != -1){
                if (book[v[k]] == 0&& dis[v[k]] > w[k]){
                    dis[v[k]] = w[k];//更新距离
                    siftup(pos[v[k]]);//进行向上调整
                    //pos[v[k]]存储的是顶点v[k]在堆中的位置
                }
                k = next[k];
            }
        }
        System.out.println(sum);
    }

}
 
时间复杂度为O(MlogN)
 
重要城市-图的割点 
package ch8;

import java.util.Scanner;

public class TUTest04 {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int m = scanner.nextInt();
    static int[][] e= new int[n+1][n+1];
    static int root;
    static int[] num = new int[n+1];
    static int[] low = new int[n+1];
    static int[] flag = new int[n+1];
    static int index;//index 用来进行时间戳的递增

    public static int min(int a, int b){
        return a< b ? a :b;
    }
    public static void dfs(int cur,int father){//当前顶点编号和父顶点编号
        int childnum = 0;//用来记录当前cur结点的子节点数
        index ++;
        num[cur] = index;//当前顶点的时间戳
        low[cur] = index;//当前结点能够访问到最早顶点的时间戳，刚开始就是自己
        for(int i =1; i<=n;i++){//枚举与当前顶点cur相连的顶点i
            if (e[cur][i] == 1){
                if (num[i] == 0) {//如果顶点i的时间戳为0，说明顶点还没有被访问过
                    childnum ++;//为子结点
                    dfs(i,cur);//继续往下深度优先遍历
                    //更新当前顶点cur最早能够访问到的顶点的时间戳
                    low[cur] = min(low[cur],low[i]);
                    //如果当前顶点不是根节点并且满足low[i]>=num[cur]，则当前顶点为割点
                    if (cur != root && low[i] >= num[cur]){
                        flag[cur] = 1;
                    }
                    //如果当前顶点时根节点，在生成书中根节点必须有两个儿子，那么这个根结点才是割点
                    if (cur == root && childnum == 2){
                        flag[cur] =1;
                    }

                }else if(i != father){
                    //否则如果顶点i被访问过，并且这个顶点不是当前顶点的father，说明此时的i为cur的祖先。因此
                    //需要更新当前结点cur能访问到的最早顶点的时间戳
                    low[cur] = min(low[cur],num[i]);
                }
            }
        }
    }

    public static void main(String[] args) {
        for (int i =1; i<=n;i++){
            for (int j=1; j<= n ;j++){
                e[i][j] = 0;
            }
        }
        for (int i =1; i<=m ;i++){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            e[x][y] = 1;
            e[y][x] = 1;
        }
        scanner.close();
        root =1;
        dfs(1,root);//从一号顶点进行dfs遍历

        for (int i =1;i<=n;i++){
            if (flag[i] == 1){
                System.out.println(i);
            }
        }
    }
}
 
时间复杂度为O（N2）
 
关键道路-用Tarjan算法求图的割边 
package ch8;

import java.util.Scanner;

public class TUTest05 {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int m = scanner.nextInt();
    static int[][] e= new int[n+1][n+1];
    static int root;
    static int[] num = new int[n+1];
    static int[] low = new int[n+1];
    static int[] flag = new int[n+1];
    static int index;//index 用来进行时间戳的递增

    public static int min(int a, int b){
        return a< b ? a :b;
    }
    public static void dfs(int cur,int father){//当前顶点编号和父顶点编号

        index ++;
        num[cur] = index;//当前顶点的时间戳
        low[cur] = index;//当前结点能够访问到最早顶点的时间戳，刚开始就是自己
        for(int i =1; i<=n;i++){//枚举与当前顶点cur相连的顶点i
            if (e[cur][i] == 1){
                if (num[i] == 0) {//如果顶点i的时间戳为0，说明顶点还没有被访问过
                    dfs(i,cur);//继续往下深度优先遍历
                    //更新当前顶点cur最早能够访问到的顶点的时间戳
                    low[cur] = min(low[cur],low[i]);
                    //如果当前顶点不是根节点并且满足low[i]>=num[cur]，则当前顶点为割边
                    if (low[i] > num[cur]){
                        System.out.println(cur + " - " + i);
                    }
                }else if(i != father){
                    //否则如果顶点i被访问过，并且这个顶点不是当前顶点的father，说明此时的i为cur的祖先。因此
                    //需要更新当前结点cur能访问到的最早顶点的时间戳
                    low[cur] = min(low[cur],num[i]);
                }
            }
        }
    }

    public static void main(String[] args) {
        for (int i =1; i<=n;i++){
            for (int j=1; j<= n ;j++){
                e[i][j] = 0;
            }
        }
        for (int i =1; i<=m ;i++){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            e[x][y] = 1;
            e[y][x] = 1;
        }
        scanner.close();
        root =1;
        dfs(1,root);//从一号顶点进行dfs遍历

        for (int i =1;i<=n;i++){
            if (flag[i] == 1){
                System.out.println(i);
            }
        }
    }
}
 
我要做月老-二分图最大匹配 
package ch8;

import java.util.Scanner;

public class TUTest06 {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int m = scanner.nextInt();
    static int[][] e = new int[n+1][n+1];
    static int[] book = new int[n+1];
    static int[] match = new int[n+1];
    public static boolean dfs(int u){
        for (int i =1;i<=n;i++){
            if (book[i] == 0 && e[u][i] == 1) {//u i 可以链接在一起
                book[i] = 1;
                if (match[i] == 0 || dfs(match[i])) { //i还没有配对或者找到了新的配对
                    //更新配对表
                    match[i] = u;
                    return true;//配对成功
                }
            }
        }
        return false;//全部遍历完都没有配对成功返回false
    }

    public static void main(String[] args) {
        int sum = 0;
        for (int i =1;i<=m;i++){
            int t1 = scanner.nextInt();
            int t2 = scanner.nextInt();
            e[t1][t2] = 1;
        }
        scanner.close();
        for (int i =1;i<=n;i++){
            for (int j =1; j<=n;j++){
                book[j] = 0;//清空上次搜索的标记
            }
            if (dfs(i)) sum++;//找到一条增广路，配对数+1
        }
        System.out.println(sum);
    }
}