一、图的遍历
图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点,需要特定策略，一般有两种访问策略:(1)深度优先遍历(2)广度优先遍历深度优先遍历基本思想。
二、深度优先遍历
图的深度优先搜索(Depth First Search)。
深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深1度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解: 每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
三、广度优先遍历
图的广度优先搜索(Broad First Search)。类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序.以便按这个顺序来访问这些结点的邻接结点 。
四、代码实现
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; public class Graph { //储存顶点的集合 private ArrayList<String> vertexList; //储存图对应的领接矩阵 private int[][] edges; //边的数目 private int numOfEdges; //记录某个节点是否被访问 private boolean[] isVisited; public Graph(int n) { //初始化矩阵 edges = new int[n][n]; vertexList = new ArrayList<>(n); numOfEdges = 0; isVisited = new boolean[n]; } /** * 深度优先遍历 */ public void dfs() { isVisited=new boolean[getNumOfVertex()]; // 遍历所有的节点，进行dfs for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { dfs(isVisited, i); } } } /** * 深度优先遍历 * * @param isVisited * @param i */ public void dfs(boolean[] isVisited, int i) { // 输出访问节点 System.out.print(getValueByIndex(i) + " "); // 将该节点设置为已经访问 isVisited[i] = true; // 查找节点i的第一个领结节点w int w = getFirstNeighbor(i); //如果存在邻接节点 while (w != -1) { //如果这个节点没有被访问； if (!isVisited[w]) { dfs(isVisited, w); } // 如果w节点应景访问了 w = getNextNeighbor(i, w); } } /** * 广度优先 * * @param isVisited * @param i */ private void bfs(boolean[] isVisited, int i) { //队列的头结点 int u; //队列的领结节点 int w; //队列，记录访问顺序 LinkedList<Integer> queue = new LinkedList(); //访问节点输出信息 System.out.print(getValueByIndex(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(getValueByIndex(w) + " "); // 标记已经访问过 isVisited[w] = true; // 入队 queue.addLast(w); } // 以u为前驱点，找w后面的下一个节点，此处体现广度优先 w = getNextNeighbor(u, w); } } } public void bfs() { isVisited=new boolean[getNumOfVertex()]; for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { bfs(isVisited, i); } } } /** * 得到第一个领结节点的下标 * * @param index * @return */ public int getFirstNeighbor(int index) { for (int i = 0; i < vertexList.size(); i++) { //判断边是否存在，存在默认为1 if (edges[index][i] > 0) { return i; } } return -1; } /** * 根据当前节点v1,v2寻找下一个领结节点 * * @param v1 * @param v2 * @return */ public int getNextNeighbor(int v1, int v2) { for (int i = v2 + 1; i < vertexList.size(); i++) { if (edges[v1][i] > 0) { return i; } } return -1; } /** * 返回节点的个数 * * @return */ public int getNumOfVertex() { return vertexList.size(); } /** * 得到边的数目 * * @return */ public int getNumOfEdges() { return numOfEdges; } /** * 根据下标，返回对应的数据 * * @param index * @return */ public String getValueByIndex(int index) { return vertexList.get(index); } /** * 获取val1,val2的权值 * * @param val1 * @param val2 * @return */ public int getWeight(int val1, int val2) { return edges[val1][val2]; } /** * 插入节点 * * @param vertex */ public void insertVertex(String vertex) { vertexList.add(vertex); } /** * 添加边 * * @param val1 表示点的下标 * @param val2 表示点的下标 * @param weight 表示对应的值 */ public void insetEdge(int val1, int val2, int weight) { edges[val1][val2] = weight; edges[val2][val1] = weight; numOfEdges++; } /** * 显示图对应的矩阵 */ public void showGraph() { for (int[] item : edges) { System.out.println(Arrays.toString(item)); } } }
五、测试
public class GraphDemo { public static void main(String[] args) { // 测试图 String[] vertexs = {"1", "2", "3", "4", "5","6","7","8"}; // 创建图形 Graph graph = new Graph(vertexs.length); // 循环的添加订单 for (String vertex : vertexs) { graph.insertVertex(vertex); } // 添加边 graph.insetEdge(0, 1, 1); graph.insetEdge(0, 2, 1); graph.insetEdge(1, 3, 1); graph.insetEdge(1, 4, 1); graph.insetEdge(3, 7, 1); graph.insetEdge(4, 7, 1); graph.insetEdge(2, 5, 1); graph.insetEdge(2, 6, 1); graph.insetEdge(5, 6, 1); //显示领接矩阵 graph.showGraph(); // 深度遍历邻接矩阵 System.out.println("深度优先"); graph.dfs(); System.out.println(); System.out.println("广度优先"); graph.bfs(); } }
[0, 1, 1, 0, 0, 0, 0, 0] [1, 0, 0, 1, 1, 0, 0, 0] [1, 0, 0, 0, 0, 1, 1, 0] [0, 1, 0, 0, 0, 0, 0, 1] [0, 1, 0, 0, 0, 0, 0, 1] [0, 0, 1, 0, 0, 0, 1, 0] [0, 0, 1, 0, 0, 1, 0, 0] [0, 0, 0, 1, 1, 0, 0, 0] 深度优先 1 2 4 8 5 3 6 7 广度优先 1 2 3 4 5 6 7 8
