package?test.suanfa.findcycle2;

import?java.util.ArrayList;
import?java.util.HashMap;
import?java.util.List;
import?java.util.Map;
import?java.util.Stack;

/**
?*?@author?[QQ:371319819]
?*
?*/
public?class?Graph?
{
	private?List?vertexList?=?new?ArrayList（）;?//?節點集合
	private?Map>?adjMat?=?new?HashMap（）;??????//?邊關系集合
	private?Stack?theStack?=?new?Stack（）;
	??
	public?void?addVertex（String?lab）
	{
		vertexList.add（new?Vertex（lab））;
	}
	
	/**
	?*?邊連接
	?*?
	?*?@param?start
	?*?@param?end
	?*/
	public?void?addEdge（String?startNode?String?endNode）
	{
		List?nextNodeList?=?adjMat.get（startNode）;
		if?（nextNodeList?==?null）
		{
			nextNodeList?=?new?ArrayList（）;
			adjMat.put（startNode?nextNodeList）;
		}
		
		for?（String?oneNextNodeLabel?:?nextNodeList）
		{
			if?（oneNextNodeLabel.equals（endNode））
			{
				return;
			}
		}
		
		nextNodeList.add（endNode）;
	}
	
	/**
	?*?如果一條路徑，在舊有的所有路徑中都不存在，則代表是一條新路徑，可以繼續?遍歷：不依靠節點的是否已訪問標志來識別當前路徑是否可選，
	?*?在遍歷路徑中帶環的圖有效果
	?*?
	?*?@param?nextEnd
	?*?@param?curPath
	?*?@param?allPath
	?*?@return
	?*/
	public?boolean?existPath（String?nextEnd?List?curPath?List>?allPath）
	{
		String?head?=?curPath.get（0）;
		List?tmpPath?=?new?ArrayList（）;
		tmpPath.addAll（curPath）;
		
		if?（nextEnd?!=?null?&&?!nextEnd.equals（““））
		{
			tmpPath.add（nextEnd）;
		}
		
		for?（List?onePath?:?allPath）
		{
			if?（!onePath.get（0）.equals（head））
			{
				continue;
			}
			
			if?（tmpPath.size（）?>?onePath.size（））
			{
				continue;
			}
			
			int?sameCount?=?0;
			for?（int?i?=?0;?i?			{
				if?（tmpPath.get（i）.equals（onePath.get（i）））
				{
					sameCount++;
				}
			}
			
			if?（sameCount?==?tmpPath.size（））
			{
				return?true;
			}
		}
		
		return?false;
	}
	
	/**
	?*?深度優先遍歷
	?*?目前只選中一個節點作為開始節點來遍歷出所有路徑，如果希望遍歷所有路徑，可以在本方法外部增加一個for循環
	?*?
	?*/
	public?List>?mst（）??//?minimum?spanning?tree?（depth?first）
	{????????
		Vertex?firstVertex?=?vertexList.get（0）;
	????theStack.push（firstVertex）;

	????List>?allPathList?=?new?ArrayList（）;
	????List?onePath?=?new?ArrayList（）;
	????onePath.add（firstVertex.label）;
	????allPathList.add（onePath）;
	????
	????while（!theStack.isEmpty（）?）???????//?until?stack?empty
	????{???????????????????????????????//?get?stack?top
	????	Vertex?currentVertex?=?theStack.peek（）;
	????	String?currentVertexLabel?=?currentVertex.label;
	????	//?如果在for循環中沒有找到后續的節點，也要后退一個節點
	????	Vertex?nextNode?=?null;
	????	
	????	boolean?cycleEnd?=?false;
	????	boolean?existPath?=?false;
	????	
	????	List?nextNodeList?=?adjMat.get（currentVertexLabel）;
	????	if?（nextNodeList?!=?null?&&?!nextNodeList.isEmpty（））
	????	{
		????????for（String?oneNextNodeLabel?:?nextNodeList）
				{
					cycleEnd?=?false;
		????????	existPath?=?false;
		????????	
					if?（existPath（oneNextNodeLabel?onePat

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????5840??2015-11-12?21:12??Graph.java
?????文件????????2607??2015-11-12?21:07??MSTApp.java
?????文件?????????144??2015-11-12?21:07??Vertex.java