无向图的深度java代码_Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

不念不忘少年蓝@ 2022-11-10 10:33 51阅读 0赞

所谓有权图，就是图中的每一条边上都会有相应的一个或一组值。通常情况下，这个值只是一个数字

如：在交通运输网中，边上的权值可能表示的是路程，也可能表示的是运输费用(显然二者都是数字)。不过，边上的权值也有可能是其它东西，比如说是一个字符串，甚至是一个更加复杂的数据包，里面集合了更多的数据

克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。

克鲁斯卡尔算法的执行步骤：

第一步：在带权连通图中，将边的权值排序；

第二步：判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。

第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。

关于有权图的实现，看如下实例：

![15117761521.png?20171024145319][15117761521.png_20171024145319]

Graph:

package kruskal;

public class Graph \{

final int max=100;

/\*

\* 顶点节点

\*/

public class VexNode\{

int adjvex;

int data;

VexNode\[\] vexNodes;

int\[\] thevexs;

//顶点集合

int\[\]\[\] edges = new int\[max\]\[max\];

//边集合

/\*

\* 创建图

\*/

public void createGraph(Graph graph,int\[\]\[\] A,int\[\] vexs) \{

thevexs=vexs;

for (int i = 0; i < vexs.length; i++) \{

for (int j = 0; j < vexs.length; j++) \{

graph.edges\[i\]\[j\] = A\[i\]\[j\];

/\*

\* 输出图

\*/

public void printGraph(Graph graph) \{

for (int i = 0; i < graph.thevexs.length; i++) \{

for (int j = 0; j < graph.thevexs.length; j++) \{

//没有路径则输出/

if (graph.edges\[i\]\[j\]==-1) \{

System.out.printf("%4s","/");

\} else \{

System.out.printf("%4d",graph.edges\[i\]\[j\]);

System.out.println("\\n");

算法：

package kruskal;

public class KruSkal \{

public class Edge\{

int start;

int end;

int weight;

public void SortEdge(Edge\[\] E,int e) \{

Edge temp;

int j;

for (int i = 0; i < e; i++) \{

temp=E\[i\];

j=i-1;

while (j>=0&&temp.weight

E\[j+1\] = E\[j\];

j--;

E\[j+1\] = temp;

public KruSkal(Graph graph) \{

int i,j,u1,v1,sn1,sn2,k;

int\[\] vset = new int\[100\];

Edge\[\] E = new Edge\[100\];

k=0;

for (i=0;i

for (j=0;j<=i;j++) \{

E\[k\] = new Edge();

if (graph.edges\[i\]\[j\]>0) \{

E\[k\].start=i;

E\[k\].end=j;

E\[k\].weight=graph.edges\[i\]\[j\];

k++;

SortEdge(E,k);

for (i=0;i

vset\[i\]=i;

k=1;

j=0;

while (k

u1=E\[j\].start;

v1=E\[j\].end;

sn1=vset\[u1\];

sn2=vset\[v1\];

if (sn1!=sn2) \{

System.out.printf("(%d,%d),权值：%d",E\[j\].weight);

System.out.println("\\n");

k++;

for (i=0;i

if (vset\[i\]==sn2) \{

vset\[i\]=sn1;

j++;

测试类：

package kruskal;

public class Test \{

public static void main(String\[\] args) \{

int\[\] vexs = \{0,1,2,3,4\};

int\[\]\[\] A = \{

\{0,4,7\},\{1,-1,-1\},\{3,5,8\},\{4,6\},\{7,8,6,0\}

\};

Graph graph = new Graph();

graph.createGraph(graph,A,vexs);

graph.printGraph(graph);

KruSkal kruSkal = new KruSkal(graph);

总结

以上就是本文关于Java语言基于无向有权图实现克鲁斯卡尔算法代码示例的全部内容，希望对大家有所帮助。有什么问题可以随时留言，小编尽力为您答复。

总结

如果觉得编程之家网站内容还不错，欢迎将编程之家网站推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

如您喜欢交流学习经验，点击链接加入交流1群：1065694478(已满)交流2群：163560250

[15117761521.png_20171024145319]: http://oudahe.com/uploads/201711/27/15117761521.png?20171024145319

无向图的深度java代码_Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

发表评论取消回复

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

相关阅读

相关克鲁斯卡尔kruskal算法（Java）

相关无向图以及图的java代码实现

相关 Java实现Kruskal克鲁斯卡尔算法

相关克鲁斯卡尔算法

相关算法——克鲁斯卡尔算法（Java代码实现）

相关迪克斯特拉算法python有向无环图

相关数据结构——图——克鲁斯卡尔（Kruskal）算法

相关克鲁斯卡尔算法

相关无向图的深度java代码_Java语言基于无向有权图实现克鲁斯卡尔算法代码示例

相关克鲁斯卡尔算法