太原理工大學2021軟體學院資料結構課程設計第二題(構造可以使n個城市連接的最小生成樹)核心代碼(2021.6.6)

宣告：這里只是給出核心代碼

核心代碼指程式的計算部分，不是完整程式

題目背景：P3366 【模板】最小生成樹 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

題目

題目描述

如題，給出一個無向圖，求出最小生成樹，如果該圖不連通，則輸出 orz，

輸入格式

第一行包含兩個整數 N,M，表示該圖共有 N 個結點和 M 條無向邊，

接下來 M 行每行包含三個整數xi,yi,zi，表示有一條長度為zi的無向邊連接結點 xi,yi.

輸出格式

如果該圖連通，則輸出一個整數表示最小生成樹的各邊的長度之和，如果該圖不連通則輸出 orz，

輸入輸出樣例

**輸入 **

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

輸出 #1

7

最小生成樹背景知識

1.最小生成樹的代價指最小生成樹各邊長度之和

Kruscal演算法代碼

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @see 圖論 Kruscal https://www.luogu.com.cn/problem/P3366 https://www.acwing.com/solution/content/30279/
 */
public class Main {

    static class Edge {
        int a, b, w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    static final int N = 100010;
    static int n, m;
    static int[] p;
    static Edge[] edges;

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    static String next() throws Exception {
        in.nextToken();
        return in.sval;
    }

    /**
     * 并查集find模板
     * @param x 當前連通塊的點
     * @return
     */
    static int find(int x) {
        if (p[x]!=x){
            p[x] = find(p[x]);
        }
        return p[x];
    }

    static int kruskal() {
        Arrays.sort(edges, Comparator.comparingInt(a -> a.w));
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        int res = 0, count = 0;
        for (int i = 0; i < m; i++) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                res += w;
                count++;
            }
        }
        //判斷是否連通
        return count < n - 1 ? -1 : res;

    }

    public static void main(String[] args) throws Exception {
        n = nextInt();
        m = nextInt();
        edges = new Edge[m];
        p = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            edges[i] = new Edge(a, b, c);

        }
        int ans = kruskal();
        if (ans==-1){
            System.out.println("orz");
        }else {
            System.out.println(ans);
        }

    }


}

Prim演算法代碼

package Acwing858Prim演算法求最小生成樹;

import java.io.*;
import java.util.Arrays;

/**
 * @see 圖論 最小生成樹 Prim https://www.acwing.com/solution/content/38312/ https://www.luogu.com.cn/problem/P3366
 */
public class PrimClass {
    static final int INF = 9999;
    static int[][] ad;
    static int[] dist;
    static int n, m;
    static boolean[] st;

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    static int prim() {
        Arrays.fill(dist, INF);
        int res = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            if (i > 0 && dist[t] == INF) {
                return INF;
            }
            if (i > 0) {
                res += dist[t];
            }
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], ad[t][j]);
            }
            st[t] = true;

        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        n = nextInt();
        m = nextInt();
        dist = new int[n+1];
        ad = new int[n+1][n+1];
        st = new boolean[n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    ad[i][j] = 0;
                } else {
                    ad[i][j] = INF;
                }
            }
        }

        while (m-- > 0) {
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            ad[a][b] = Math.min(ad[a][b], c);
//-------------無向圖-----------------------------
            ad[b][a]= ad[a][b];
//-----------------------------------------------
        }
        int ans = prim();
        if (ans == INF) {
            System.out.println("orz");
        } else {
            System.out.println(ans);
        }


    }


}

再次強調，以上只是核心代碼，同學們要根據核心代碼，自己撰寫完整的程式

完整程式應該是這樣

刷題不迷路，歡迎關注博主的git題集，這里有最詳細的分類，最經典的例題和最全面的注釋

感興趣的同學可以賞個star嗎：演算法刷題集git地址 題目原始碼地址