一、图的遍历方法
1、深度优先遍历：
1.利用递归操作
2.首先定义一个visit数组，数组长度为节点个数，作用为判断每个节点是否访问过，在递归过程中，一但该节点访问过，就置为1
3.将visit数组所有元素置为0，表示还无元素被访问过
4.将每一个节点都作为开始点进行一次DFS操作，因为如果改图不是连通图，不能通过一次DFS访问所有节点，所以进行循环，将每个节点作为开始，进行一次DFS
5.从第一个节点开始，只要他的邻接节点没有被访问过，就一直继续访问，直到不能够走下去为止
6.类似于树的先序遍历
2、广度优先遍历：
1.类似于树的层序遍历，树的层序遍历是将根节点入队，如果它的左右孩子不为空，就将它的左右孩子入队，然后访问根节点，将它出队，不断循环这个操作，直到队列为空
2.首先将最先访问的节点入队，访问它，然后将它的所有邻接点全部入队，再将最开始访问的节点出队，不断循环，直到队列中无任何节点，出队的顺序即为图的广度优先遍历顺序
二、代码测试
import java.io.IOException; import java.util.Scanner; public class MatrixUDG { private char[] mVexs; // 图的顶点集合 private int[][] mMatrix; // 图的邻接矩阵 public MatrixUDG() { // 输入"顶点数"和"边数" System.out.printf("请输入顶点个数: "); int vlen = readInt(); System.out.printf("请输入边的个数: "); int elen = readInt(); if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) { System.out.printf("输入数据有误!\n"); return ; } // 初始化"顶点" mVexs = new char[vlen]; for (int i = 0; i < mVexs.length; i++) { System.out.printf("vertex(%d): ", i); mVexs[i] = readChar(); } // 初始化"边" mMatrix = new int[vlen][vlen]; for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 System.out.printf("edge(%d):", i); char c1 = readChar(); char c2 = readChar(); int p1 = getPosition(c1); int p2 = getPosition(c2); if (p1==-1 || p2==-1) { System.out.printf("input error: invalid edge!\n"); return ; } mMatrix[p1][p2] = 1; mMatrix[p2][p1] = 1; } } /* * 创建图(用已提供的矩阵) * * 参数说明： * vexs -- 顶点数组 * edges -- 边数组 */ public MatrixUDG(char[] vexs, char[][] edges) { // 初始化"顶点数"和"边数" int vlen = vexs.length; int elen = edges.length; // 初始化"顶点" mVexs = new char[vlen]; for (int i = 0; i < mVexs.length; i++) mVexs[i] = vexs[i]; // 初始化"边" mMatrix = new int[vlen][vlen]; for (int i = 0; i < elen; i++) { // 读取边的起始顶点和结束顶点 int p1 = getPosition(edges[i][0]); int p2 = getPosition(edges[i][1]); mMatrix[p1][p2] = 1; mMatrix[p2][p1] = 1; } } /* * 返回ch位置 */ private int getPosition(char ch) { for(int i=0; i<mVexs.length; i++) if(mVexs[i]==ch) return i; return -1; } /* * 读取一个输入字符 */ private char readChar() { char ch='0'; do { try { ch = (char)System.in.read(); } catch (IOException e) { e.printStackTrace(); } } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z'))); return ch; } /* * 读取一个输入字符 */ private int readInt() { Scanner scanner = new Scanner(System.in); return scanner.nextInt(); } /* * 返回顶点v的第一个邻接顶点的索引，失败则返回-1 */ private int firstVertex(int v) { if (v<0 || v>(mVexs.length-1)) return -1; for (int i = 0; i < mVexs.length; i++) if (mMatrix[v][i] == 1) return i; return -1; } /* * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1 */ private int nextVertex(int v, int w) { if (v<0 || v>(mVexs.length-1) || w<0 || w>(mVexs.length-1)) return -1; for (int i = w + 1; i < mVexs.length; i++) if (mMatrix[v][i] == 1) return i; return -1; } /* * 深度优先搜索遍历图的递归实现 */ private void DFS(int i, boolean[] visited) { visited[i] = true; System.out.printf("%c ", mVexs[i]); // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走 for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) { if (!visited[w]) DFS(w, visited); } } /* * 深度优先搜索遍历图 */ public void DFS() { boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记 // 初始化所有顶点都没有被访问 for (int i = 0; i < mVexs.length; i++) visited[i] = false; System.out.printf("DFS: "); for (int i = 0; i < mVexs.length; i++) { if (!visited[i]) DFS(i, visited); } System.out.printf("\n"); } /* * 广度优先搜索（类似于树的层次遍历） */ public void BFS() { int head = 0; int rear = 0; int[] queue = new int[mVexs.length]; // 辅组队列 boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记 for (int i = 0; i < mVexs.length; i++) visited[i] = false; System.out.printf("BFS: "); for (int i = 0; i < mVexs.length; i++) { if (!visited[i]) { visited[i] = true; System.out.printf("%c ", mVexs[i]); queue[rear++] = i; // 入队列 } while (head != rear) { int j = queue[head++]; // 出队列 for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点 if (!visited[k]) { visited[k] = true; System.out.printf("%c ", mVexs[k]); queue[rear++] = k; } } } } System.out.printf("\n"); } /* * 打印矩阵队列图 */ public void print() { System.out.printf("Martix Graph:\n"); for (int i = 0; i < mVexs.length; i++) { for (int j = 0; j < mVexs.length; j++) System.out.printf("%d ", mMatrix[i][j]); System.out.printf("\n"); } } public static void main(String[] args) { char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char[][] edges = new char[][]{ {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; MatrixUDG pG; // 自定义"图"(输入矩阵队列) //pG = new MatrixUDG(); // 采用已有的"图" pG = new MatrixUDG(vexs, edges); pG.print(); // 打印图 pG.DFS(); // 深度优先遍历 pG.BFS(); // 广度优先遍历 } }
