博客

完整代码

package Graph;

public class Graph {

	final int VERTEX_MAX = 10;  //最大结点数
	Vertex[] vertex;  //结点
	int num; //目前的结点数
	int [][] adjacency;  //临街矩阵
	//内部类表示结点
	class Vertex{  
		char content;
		boolean isSearch;
		public Vertex(char content) {
			this.content = content;
			this.isSearch = false;
		}
	}
	//内部类表示栈
	class Stack{
		final int STACK_MAX = 10;
		int stack[];
		int top;
		public Stack() {
			stack = new int[STACK_MAX];
			top = -1;
		}
		public void push(int content) {
			if(top==9) {
				System.out.println("栈已满，无法入栈啦");
			}else {
				stack[++top]=content;
			}
		}
		public int pop() {
			if(top==-1) {
				System.out.println("栈已空，无法出栈啦");
				return -1;
			}else {
				return stack[top--];
			}
		}
		public int peek() {
			return stack[top];
		}
		public boolean isEmpty() {
			return top==-1;
		}
	}
	class Queue{
		final int QUEUE_MAX = 10;
		int [] queue;
		int front;
		int rear;
		public Queue() {
			queue = new int[QUEUE_MAX];
			front = 0;
			rear = -1;
		}
		public void insert(int content) {
			if(rear==QUEUE_MAX) {
				rear=-1;
			}
			queue[++rear]=content;
		}
		public int remove() {
			if(front==QUEUE_MAX) {
				front=0;
			}
			int temp = queue[front++];
			return temp;
		}
		public boolean isEmpty() {
			return (rear+1==front || front+QUEUE_MAX-1==rear);
		}
	}
	//初始化图
	public Graph() {
		this.num = 0;
		this.vertex = new Vertex[VERTEX_MAX];
		this.adjacency = new int[VERTEX_MAX][VERTEX_MAX];
		for(int i=0;i<VERTEX_MAX;i++) {  //邻接矩阵的初始化 所有的结点都没有被访问过
			for(int j=0;j<VERTEX_MAX;j++) {
				adjacency[i][j] = 0;
			}
		}
	}
	//添加结点
	public void addVertex(char content) {
		if(num<VERTEX_MAX-1) {
			vertex[num++] = new Vertex(content);
		}else {
			System.out.println("图已满最大结点，不可以再添加结点了喔～");
		}
	}
	//无向图添加边
	public void addNAdj(int start, int end) {
		if(start<VERTEX_MAX && end<VERTEX_MAX) {
			adjacency[start][end] =  1;
			adjacency[end][start] = 1;
		}else {
			System.out.println("连接的图结点位置不合法，无法连接～");
		}
	}
	//有向图添加边
	public void addYAdj(int start, int end) {
		if(start<VERTEX_MAX && end<VERTEX_MAX) {
			adjacency[start][end] = -1;
		}else {
			System.out.println("连接的图结点位置不合法，无法连接～");
		}
	}
	//打印图中的某个结点
	public void printVertex(int index) {
		if(index>=0 && index<VERTEX_MAX) {
			System.out.print(this.vertex[index].content);
		}else {
			System.out.println("打印结点位置不合法，无法打印～");
		}
	}
	//打印邻接矩阵
	public void printAdjacency() {
		for(int i=0;i<num;i++) {
			for(int j=0;j<num;j++) {
				if(j!=num-1) {
					System.out.print(adjacency[i][j]+" ");
				}else {
					System.out.println(adjacency[i][j]);
				}
			}
		}
	}
	//寻找某一结点的未被访问的邻接点
	public int searchUnsearchVertex(int index) {
		for(int i=0;i<num;i++) {
			if(adjacency[i][index]==1 && vertex[i].isSearch==false) {
				return i;
			}
		}
		return -1;
	}
	//图的深度优先遍历 Depth-first traversal
	public void dpt() {
		Stack stack = new Stack();
		vertex[0].isSearch = true;
		printVertex(0);
		stack.push(0);
		while(!stack.isEmpty()) {
			int index = searchUnsearchVertex(stack.peek());
			if(index==-1) {
				stack.pop();
			}else {
				vertex[index].isSearch = true;
				printVertex(index);
				stack.push(index);
			}
		}
		//遍历结束后将原图返回初始值
		for(int i=0;i<num;i++) {
			vertex[i].isSearch=false;
		}
	}
	//图的广度优先遍历 Breadth-first traversal
	public void bpt() {
		Queue queue = new Queue();
		vertex[0].isSearch = true;
		printVertex(0);
		queue.insert(0);
		while(!queue.isEmpty()) {
			int v1 = queue.remove();
			int v2 = searchUnsearchVertex(v1); 
			if(v2!=-1) {
				vertex[v2].isSearch = true;
				printVertex(v2);
				queue.insert(v2);
			}
		}
		for(int i=0;i<num;i++) {
			vertex[i].isSearch = false;
		}
	}
	//最小生成树 Minimum spanning tree
	public void mst() {
		Stack stack = new Stack();
		vertex[0].isSearch = true;
		stack.push(0);
		while(!stack.isEmpty()) {
			int cur = stack.peek();
			int index = searchUnsearchVertex(0);
			if(index == -1) {
				stack.pop();
			}else {
				vertex[index].isSearch = true;
				stack.push(index);
				printVertex(cur);
				printVertex(index);
			}
		}
		for(int i=0;i<num;i++) {
			vertex[i].isSearch = false;
		}
	}
	public static void main(String[] args) {
		Graph graph = new Graph();
		graph.addVertex('F');
		graph.addVertex('O');
		graph.addVertex('R');
		graph.addVertex('E');
		graph.addVertex('V');
		graph.addVertex('E');
		graph.addVertex('R');
		graph.addNAdj(1, 3);
		graph.addNAdj(2, 5);
		graph.addNAdj(3, 6);
		graph.addNAdj(0, 4);
		graph.addNAdj(0, 1);
		graph.printAdjacency();
		graph.printVertex(3);
		System.out.println("深度优先遍历：");
		graph.dpt();
		System.out.println();
		System.out.println("广度优先遍历：");
		graph.bpt();
		System.out.println();
		System.out.println("最小生成树：");
		graph.mst();
	}
}

参考：

《大话数据结构》