java最小生成树动态演示

支持鼠标绘制图输入，可以用鼠标画图，动态演示两种最小生成树算法（prim和dijkstra）的生成过程。

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;

public class Algorithm {

	/**
	 * @param args
	 */
	ArrayList EdgeGroup1 = new ArrayList（）; // 储存prim算法的添加边集及顺序
	ArrayList EdgeGroup2 = new ArrayList（）;// 储存kruskal算法的添加边集及顺序
	static ArrayList EdgeGroupExtra = new ArrayList（）;// 辅助作用

	public void Input（） {
		// TODO Auto-generated method stub
		System.out.println（“请输入图的顶点个数:“）;
		Scanner scan = new Scanner（System.in）;
		int v_num = scan.nextInt（）;
		System.out.println（“请输入录入的边的个数：“）;
		int v_edge = scan.nextInt（）;
		Graph graph = new Graph（v_num）;

		for （int i = 0; i < v_edge; i++） {
			System.out.println（“请按照\“顶点a顶点b权重\“的格式录入边:“）;
			int x = scan.nextInt（）;
			int y = scan.nextInt（）;
			int w = scan.nextInt（）;

			Edge e = new Edge（x y w）;
			graph.add（e）;
			System.out.println（“已录入“ + x + “————“ + y + “=“ + w）;

		}
		System.out.println（“您录入的图为：“）;

	}

	public boolean Kruskal（Graph g） {

		Graph base = g;
		Graph graph = new Graph（g.vertix_number）;// 存储最小生树
		ArrayList selected_vertix = new ArrayList（）;
		int selected_edge = 0;
		int base_edge_num = base.edge_number;

		// 将所有边都试着加一次..
		for （int i = 0; i < base_edge_num; i++） {
			Edge min = base.getMin（）; // 得到这些边中最小的边
			// System.out.println（“最小边为“ + min.x + “——“ + min.y）;

			// 如果新加入的边的产生环路有点猥琐，因为在触发算法那里
			// 执行kruskal方法前先执行一次Prim算法，获得了所有的应该添加的边
			// 这个边很小，而又不选，证明是回路
			if （!hasCheck（EdgeGroupExtra min）） {
				// System.out.println（“加入有环路舍弃“）;
				base.delete（min.x min.y）;// 从底图中删除这条边

			} else {

				graph.add（min）;// 加入这条边
				EdgeGroup2.add（min）;
				base.delete（min.x min.y）;// 底图中删除这条边
				// System.out.println（“可以加入“）;
				if （!selected_vertix.contains（new Integer（min.x））） {

					selected_vertix.add（new Integer（min.x））;// 生成图的点集中加入已选点

				}
				if （!selected_vertix.contains（new Integer（min.y））） {

					selected_vertix.add（new Integer（min.y））;// 生成图的点集中加入已选点

				}
				selected_edge++;
			}

			if （selected_edge == base.vertix_number - 1）
				// 对于n个顶点的图，一直无环路添加所有边，如果能保证添加到n-1条边，必为树
			{
				break;
			}
		}

		if （selected_edge == base.vertix_number - 1）// 可以生成最小生成树
		{
			// System.out.println（“成功最小生成树为：“）;
			// graph.output（）;
			return true;
		} else {
			// System.out.println（“无法生成“）;
			return false;
		}

	}

	public boolean Prim（Graph g） {
		Graph base = g;
		Graph graph = new Graph（g.vertix_number）;// 存储最小生成树
		ArrayList selected_vertix = new ArrayList（）;
		int selected_edge_num = 1;
		int selected_vertix_num = 2;// 初始时会选一条边，即至少1个边，两个顶点
		int base_edge_num = base.edge_number;

		// 第一次，先将最小边加入树
		Edge min = base.getMin（）;
		graph.add（min）;
		EdgeGroup1.add（min）;
		selected_vertix.add（new Integer（min.x））;// 生成图的点集中加入已选点
		selected_vertix.add（new Integer（min.y））;// 生成图的点集中加入已选点
		base.delete（min.x min.y）;// 原图删除最小边
		// System.out.println（“首先加入“

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        301  2014-02-27 15:38  最小生成树\.classpath

     文件        391  2014-03-13 18:02  最小生成树\.project

     文件        629  2014-02-27 15:38  最小生成树\.settings\org.eclipse.jdt.core.prefs

     文件       5119  2014-07-12 23:08  最小生成树\bin\Algorithm.class

     文件        377  2014-07-12 23:08  最小生成树\bin\Edge.class

     文件        422  2014-07-12 23:08  最小生成树\bin\Engine.class

     文件       2819  2014-07-12 23:08  最小生成树\bin\Graph.class

     文件        907  2014-07-12 23:08  最小生成树\bin\Mainframe.class

     文件        960  2014-07-12 23:08  最小生成树\bin\MainPanel$1.class

     文件       5474  2014-07-12 23:08  最小生成树\bin\MainPanel.class

     文件        394  2014-07-12 23:08  最小生成树\bin\Point.class

     文件        494  2014-07-12 23:08  最小生成树\bin\ShowPanel$1.class

     文件       1887  2014-07-12 23:08  最小生成树\bin\ShowPanel$MyListener.class

     文件       3380  2014-07-12 23:08  最小生成树\bin\ShowPanel.class

     文件       6458  2014-03-03 21:13  最小生成树\src\Algorithm.java

     文件       1994  2014-03-02 13:14  最小生成树\src\Edge.java

     文件        110  2014-03-01 15:21  最小生成树\src\Engine.java

     文件        624  2014-03-04 09:52  最小生成树\src\Mainframe.java

     文件       8429  2014-03-12 16:21  最小生成树\src\MainPanel.java

     目录          0  2014-03-13 18:01  最小生成树\.settings

     目录          0  2014-07-12 23:08  最小生成树\bin

     目录          0  2014-03-13 18:01  最小生成树\src

     目录          0  2014-03-13 18:01  最小生成树

----------- ---------  ---------- -----  ----

                41169                    23