说明

• 本程序中树是通过邻接矩阵实现的

源代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 图的创建
public class Graph {
	// 存储图的顶点 
	private ArrayList<String> vertexList;
	// 存储图的邻接矩阵
	private int[][] edges;
	// 边数
	private int numOfEdges;
	// 保存顶点是否被访问过
	private boolean[] isVisited;
	
	public static void main(String[] args) {
		// 顶点个数
		int n = 5;
		// 所有的顶点
		String[] vertexs = {"A", "B", "C", "D", "E"};
		// 创建图
		Graph graph = new Graph(n);
		
		// 添加点
		for(String v : vertexs) {
			graph.insertVertex(v);
		}
		// 添加边
		graph.insertEdge("A", "B");
		graph.insertEdge("A", "C");
		graph.insertEdge("C", "B");
		graph.insertEdge("B", "D");
		graph.insertEdge("B", "E");
		
		// 输出图的邻接矩阵
		graph.showGraph();
		
		System.out.println("深度优先遍历：");
		// 深度优先遍历 
		graph.dfs();
		System.out.println("\n广度优先遍历 ：");
		graph.bfs();
	}
	
	// 构造函数：传入顶点个数 
	public Graph(int n) {
		edges = new int[n][n];
		vertexList = new ArrayList<String>(n);
	}
	
	// 插入顶点 
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}
	
	// 插入边
	public void insertEdge(String v1,String v2) {
		int i = vertexList.indexOf(v1);
		int j = vertexList.indexOf(v2);
		
		edges[i][j] = 1;
		edges[j][i] = 1;
		numOfEdges++;
	}
	
	// 返回顶点数
	public int getNumOfVertex() {
		return vertexList.size();
	}
	
	// 返回边数
	public int getNumOfEdges() {
		return numOfEdges;
	}
	
	// 返回两点之间是否有边
	public boolean isEdge(String v1, String v2) {
		int i = vertexList.indexOf(v1);
		int j = vertexList.indexOf(v2);
		
		if(edges[i][j] == 1) {
			return true;
		}else {
			return false;
		}
	}
	
	// 返回该节点第一个邻接节点的下标
	private int getFirstNeighbor(int index) {
		for(int j = 0; j < vertexList.size(); j++) {
			if(edges[index][j] == 1) {
				return j;
			}
		}
		return -1;
	}
	
	// 返回该节点的下一个邻接节点
	private int getNextNeighbor(int v1, int v2) {
		for(int j = v2+1; j < vertexList.size(); j++) {
			if(edges[v1][j] == 1) {
				return j;
			}
		}
		return -1;
	}
	
	// 深度优先遍历,从第i个节点开始
	private void dfs(int i) {
		System.out.print(vertexList.get(i)+"->");
		// 将节点设置为已访问
		isVisited[i] = true;
		
		// 查找该节点的第一个邻接节点的下标
		int w = getFirstNeighbor(i);
		// 如果存在
		while(w != -1) {
			// 如果此邻接节点没有被访问过，继续向下遍历 
			if(!isVisited[w]) {
				dfs(w);
			}
			// 如果此邻接节点被访问过了，查找下一个邻接节点
			w = getNextNeighbor(i, w);
		}
	}
	
	// dfs重载，依次对每一个节点进行深度优先遍历 
	public void dfs() {
		isVisited = new boolean[getNumOfVertex()];
		
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				dfs(i);
			}
		}
	}
	
	// 广度优先遍历
	private void bfs(int i) {
		// 队列头结点的下标
		int u;
		// 邻接结点
		int w;
		// 使用一个链表充当队列 
		LinkedList<Integer> queue = new LinkedList<Integer>();
		// 输出当前结点
		System.out.print(vertexList.get(i) + "=>");
		isVisited[i] = true;
		// 将该结点入队
		queue.addLast(i);
		
		while( !queue.isEmpty() ) {
			// 取出队头结点
			u = queue.removeFirst();
			// 获取队头结点的第一个邻接结点 
			w = getFirstNeighbor(u);
			// 如果能够找到
			while(w != -1) {
				// 如果此结点没有被访问
				if(!isVisited[w]) {
					System.out.print(vertexList.get(w) + "=>");
					isVisited[w] = true;
					// 将此结点入队
					queue.addLast(w);
				}
				// 然后查找下一个邻接结点
				w = getNextNeighbor(u, w);
			}
		}
	}
	
	// 重载BFS
	public void bfs() {
		isVisited = new boolean[getNumOfVertex()];
		
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				bfs(i);
			}
		}
	}
	
	// 输出图的邻接矩阵
	public void showGraph() {
		for(String v : vertexList) {
			System.out.printf("%3s",v);
		}
		System.out.println();
		
		for(int i = 0; i < vertexList.size(); i++) {
			
			System.out.println(vertexList.get(i) + Arrays.toString(edges[i]));
		}
	}

}