図-最小ツリー

もし1つの図の中のすべての点がつながっているならば、最小の木を求めて図を遍歴して完成することができて、ここの最小は辺が最も少なくて、辺の長さと関係がありません.
アルゴリズムは深さ優先ループを用いて,各ループしたノードを記述し,ノードをループ順に記録することがいわゆる最小ツリーである.
深度優先パスについては、深度優先パスを参照してください.
しかし、ここで不思議なことに、
すべてのノード間が双方向に接続されている場合、配列を生成するだけで、{'a','b','c','d','d'}などのすべてのノードをロードします.
そして、各2つの点の間の線分は、a-->b,b-->c,c-->d,d-->eの最小ツリーの結果である.
このような複雑な構造支持は必要ないようだ.
しかし、ここでは図に従って最小の木を生成する方法を示した.
Graph.mst:最小ツリーを返します.
Graph.main:簡単なテストを提供します.
コードは次のとおりです.

class Stack {
	private int[] values;
	private int pos = -1;
	Stack(int size) {
		values = new int[size];
	}
	void push(int value) { values[++pos] = value; }
	int pop() { return values[pos--]; }
	int peek() { return values[pos]; }
	boolean isEmpty() { return pos == -1; }
}

class Vertex {
	private Object value;
	private boolean isVisited;
	Vertex(Object value) {
		this.value = value;
	}

	void visit() { isVisited = true; }
	void clean() {	isVisited = false; }
	boolean isVisited() { return isVisited; }
	Object value() { return value; }
}

class Graph {
	private Vertex[] vertexs;
	private int[][] adjMat;
	private int pos = -1;

	Graph(int size) {
		vertexs = new Vertex[size];
		adjMat = new int[size][size];
	}

	void add(Object value) {
		assert pos < vertexs.length;
		vertexs[++pos] = new Vertex(value);
	}

	void connect(int from, int to) {
		adjMat[from][to] = 1;
		adjMat[to][from] = 1;
	}

	void connectAll() {
		for(int i=0; i<= pos; i++)  
			for(int j=0; j<= pos; j++)
				adjMat[i][j] = i^j&1;
		
	}
	int findNeighbor(int index) {
		for(int i=0; i<=pos; i++) {
			if(adjMat[index][i] == 1 && !vertexs[i].isVisited()) return i;
		}
		return -1;
	}

	Object[] mst(int index) {	//               
		if(vertexs[index] == null) return new Object[0];	//            ，   

		Stack s = new Stack(vertexs.length);	//              
		Object[] result = new Object[pos+1];	//     
		int i = 0;	
		vertexs[index].visit();	//  0  
		result[i++] = vertexs[index].value();
		s.push(index);	//  0  

		while(!s.isEmpty()) {	//            
			index = findNeighbor(s.peek());	//              
			if(index != -1) {	//    
				vertexs[index].visit();	//     
				result[i++] = vertexs[index].value();
				s.push(index);	//     
			} else s.pop();		//         ，   
		}	//            
		clean();	//        
		return result;
	}

	void clean() { for(Vertex v: vertexs) if(v != null)v.clean(); }

	public static void main(String[] args) {
		Graph g = new Graph(20);
		g.add('a');
		g.add('b');
		g.add('c');
		g.add('d');
		g.add('e');
		g.connectAll();
		Object[] result = g.mst(0);
		for(int i=0; i<result.length-1; i++) {
			System.out.println(result[i] + " --> " + result[i+1]);
		}
	}
}