图的最小生成树

川长思鸟来 2022-08-06 11:11 119阅读 0赞

import java.util.Stack;
    
    /*
     * 图的最小生成树
     */
    public class MSTDemo {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		char[] vertices = {'A', 'B', 'C', 'D', 'E'};
    		int[][] edges = {
    				{0, 1, 1, 1, 1},
    				{1, 0, 1, 1, 1},
    				{1, 1, 0, 1, 1},
    				{1, 1, 1, 0, 1},
    				{1, 1, 1, 1, 0}
    			};
    		
    		boolean[] isVisited = new boolean[vertices.length];
    		Stack<Integer> stack = new Stack<Integer>();
    		stack.push(0);
    		isVisited[0] = true;
    
    		while(!stack.isEmpty()) {
    			int par = stack.peek();
    			int v = getAdjUnvisitedVertex(par, edges, isVisited);
    			if(v == -1) {
    				stack.pop();
    			} else {
    				stack.push(v);
    				isVisited[v] = true;
    				System.out.print(vertices[par]);
    				System.out.print(vertices[v] + " ");
    			}
    		}
    		System.out.println();
    	}
    
    	public static int getAdjUnvisitedVertex(int cur, int[][] edges, boolean[] isVisited) {
    		// TODO Auto-generated method stub
    		for(int i = 0; i < edges[cur].length; i++) {
    			if(edges[cur][i]==1 && !isVisited[i]) {
    				return i;
    			}
    		}
    		return -1;
    	}
    
    }

输出结果：

AB BC CD DE

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关图的最小生成树算法

在上一篇文章中，我们看了一下图的遍历算法，主要是对图的深度优先遍历和图的广度优先遍历算法思想的介绍。接下来让我们来看一下图的最小声成树算法。首先，我们要知道，图的最小生成树

清疚/ 2022年09月28日 13:03/ 0 赞/ 134 阅读

相关图结构练习——最小生成树

图结构练习——最小生成树 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述有n个城市，其中有

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 06:11/ 0 赞/ 132 阅读

相关图的最小生成树

import java.util.Stack; / 图的最小生成树 / public class MSTDemo {

川长思鸟来/ 2022年08月06日 11:11/ 0 赞/ 120 阅读

相关图结构练习——最小生成树

Problem Description 有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，

末蓝、/ 2022年07月12日 09:51/ 0 赞/ 134 阅读

相关蓝桥-树-图最小生成树2

package com.jkxy.more; public class MTreeOPho2 { static int k,i,j,min,

喜欢ヅ旅行/ 2022年07月12日 04:37/ 0 赞/ 128 阅读

相关无向图最小生成树

N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。 Input 第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000

爱被打了一巴掌/ 2022年06月12日 06:42/ 0 赞/ 146 阅读

相关图结构练习——最小生成树

Think: 1知识点：最小生成树Kruskal算法 2反思：题意分析建议使用最小生成树Prim算法 3知识体系分析：Kruskal算法更适用于稀疏图，未加堆优化的

淩亂°似流年/ 2022年06月12日 03:19/ 0 赞/ 158 阅读

相关图论-最小生成树

给定一个无向图，如果它的某一个子图中任意俩个顶点都互相联通并且是一棵树，那么这棵树就是生成树。如果边上还有权值，边权和最小的称为最小生成树。算法1：Prim算法

深碍√TFBOYSˉ_/ 2022年05月28日 04:51/ 0 赞/ 137 阅读

相关数据结构—图—最小生成树

什么是最小生成树一个有 n 个结点的[连通图][Link 1]的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 \[1\]

悠悠/ 2022年04月12日 04:50/ 0 赞/ 434 阅读

相关图的应用——最小生成树

最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。最小生成树可以用Prim（普里姆）算法或kru

野性酷女/ 2021年11月16日 15:10/ 0 赞/ 249 阅读