package demo14;

/**
 * 顶点类
 * @author Richard
 */
public class Vertex {

	private String value;
	public boolean visited;

	public String getValue() {
		return value;
	}

	public void setValue(String value) {
		this.value = value;
	}

	public Vertex(String value) {
		super();
		this.value = value;
	}

	@Override
	public String toString() {
		return value;
	}

}

package demo14;

import demo2.MyStack;

/**
 * 图
 * @author Richard
 *
 */
public class Graph {

	private Vertex[] vertex;
	private int currentSize;
	public int[][] adjMat;
	private MyStack stack = new MyStack();
	//当前遍历的下标
	private int currentIndex;
	
	public Graph(int size) {
		vertex=new Vertex[size];
		adjMat=new int[size][size];
	}
	
	/**
	 * 向图中加入一个顶点
	 * @param v
	 */
	public void addVertex(Vertex v) {
		vertex[currentSize++]=v;
	}
	
	public void addEdge(String v1,String v2) {
		//找出两个顶点的下标
		int index1=0;
		for(int i=0;i<vertex.length;i++) {
			if(vertex[i].getValue().equals(v1)) {
				index1=i;
				break;
			}
		}
		int index2=0;
		for(int i=0;i<vertex.length;i++) {
			if(vertex[i].getValue().equals(v2)) {
				index2=i;
				break;
			}
		}
		adjMat[index1][index2]=1;
		adjMat[index2][index1]=1;
	}
	
	/**
	 * 深度优先搜索算法遍历图
	 */
	public void dfs() {
		//把第0个顶点标记为已访问状态
		vertex[0].visited=true;
		//把第0个顶点的下标。
		stack.push(0);
		//打印顶点的值
		System.out.println(vertex[0].getValue());
		//遍历
		out:while(!stack.isEmpty()) {
			for(int i=currentIndex+1;i<vertex.length;i++) {
				//如果和下一个遍历的元素是通的
				if(adjMat[currentIndex][i]==1&&vertex[i].visited==false) {
					//把下一个元素压入栈中
					stack.push(i);
					vertex[i].visited=true;
					System.out.println(vertex[i].getValue());
					continue out;
				}
			}
			//弹出栈顶元素
			stack.pop();
			//修改当前位置为栈顶元素的位置
			if(!stack.isEmpty()) {
				currentIndex=stack.peek();
			}
		}
	}
	
}

package demo14;

import java.util.Arrays;

public class TestGraph {

	public static void main(String[] args) {
		Vertex v1 = new Vertex("A");
		Vertex v2 = new Vertex("B");
		Vertex v3 = new Vertex("C");
		Vertex v4 = new Vertex("D");
		Vertex v5 = new Vertex("E");
		Graph g = new Graph(5);
		g.addVertex(v1);
		g.addVertex(v2);
		g.addVertex(v3);
		g.addVertex(v4);
		g.addVertex(v5);
		
		//增加边
		g.addEdge("A", "C");
		g.addEdge("B", "C");
		g.addEdge("A", "B");
		g.addEdge("B", "D");
		g.addEdge("B", "E");
		
		for(int[] a:g.adjMat) {
			System.out.println(Arrays.toString(a));
		}
		//深度优先遍历
		g.dfs();
	}
	
}