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?			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?se_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