demo1
static String b[] = { "a", "b", "c", "d", "e", "f", "g" }; static int [][]arr= { {0,0,1,1,0,1,0}, {0,0,1,0,0,0,0}, {1,1,0,1,0,0,0}, {1,0,1,0,0,0,0}, {0,0,0,0,0,0,1}, {1,0,0,0,0,0,1}, {0,0,0,0,1,1,0} };
对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
a c b d f g e
广搜结果
a c d f b g e
深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。
深度优先搜索遍历过程
从a开始搜索可以看到a的子节点有c、d、f系统会依次对其进行深度优先搜索
进程先对c进行子节点的搜索可以看出c有两个子节点b、d
可以看出b没有子节点了，但是d节点作为c的子节点还没有被访问所有这个时候程序会走到d的位置
但是d也没有子节点这个时候进程会回溯到发现d的这条边的起始节点a的位置然后在对其进行搜索
a的子节点中只有f没有被遍历了所以进程只能进到f的位置然后在对其进行遍历可以看出f的两个子节点也没有子节点
所以进程在对g、e进行完遍历之后进程结束
广度优先搜索
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点a开始，会发现a的子节点有c、d、f三个子节点，进程会先对这三个节点进行访问然后再访问其的子节点
对c、d、f完成访问之后进行则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有c、g、e
可以看出c、g、e没有子节点了所以程序对其遍历之后随之结束
深搜代码
public class dfs { // 构造图的边 private int[][] edges = { {0,0,1,1,0,1,0}, {0,0,1,0,0,0,0}, {1,1,0,1,0,0,0}, {1,0,1,0,0,0,0}, {0,0,0,0,0,0,1}, {1,0,0,0,0,0,1}, {0,0,0,0,1,1,0} }; // 构造图的顶点 private String[] vertexs = { "a", "b", "c", "d", "e", "f", "g" }; // 记录被访问顶点 private boolean[] verStatus; // 顶点个数 private int vertexsNum = vertexs.length; public void DFSTra() { verStatus = new boolean[vertexsNum]; for (int i = 0; i < vertexsNum; i++) { if (verStatus[i] == false) { DFS(i); } } } // 递归深搜 private void DFS(int i) { System.out.print(vertexs[i] + " "); verStatus[i] = true; //深度搜索子节点 for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) { if (!verStatus[j]) { DFS(j); } } } // 返回与i相连的第一个顶点 private int firstAdjVex(int i) { for (int j = 0; j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 返回与i相连的下一个顶点 private int nextAdjvex(int i, int k) { for (int j = (k + 1); j < vertexsNum; j++) { if (edges[i][j] == 1) { return j; } } return -1; } // 测试 public static void main(String[] args) { new dfs().DFSTra(); } }
广搜代码
import java.util.LinkedList; import java.util.Queue; public class bfs { // 构造图的边 private int[][] edges = { {0,0,1,1,0,1,0}, {0,0,1,0,0,0,0}, {1,1,0,1,0,0,0}, {1,0,1,0,0,0,0}, {0,0,0,0,0,0,1}, {1,0,0,0,0,0,1}, {0,0,0,0,1,1,0} }; // 构造图的顶点 private String[] vertexs = { "a", "b", "c", "d", "e", "f", "g" }; // 记录被访问顶点 private boolean[] verStatus; // 顶点个数 private int vertexsNum = vertexs.length; // 广搜 private void BFS() { verStatus = new boolean[vertexsNum]; Queue<Integer> temp = new LinkedList<Integer>(); //遍历每个节点 for (int i = 0; i < vertexsNum; i++) { //判断当前节点是否被访问过 if (!verStatus[i]) {//如果没有被访问的话则将其加入队列 System.out.print(vertexs[i] + " "); verStatus[i] = true; temp.offer(i); while (!temp.isEmpty()) { //将最先进入队列的节点移除 int j = temp.poll(); //广度搜索子节点 for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) { if (!verStatus[k]) { System.out.print(vertexs[k] + " "); verStatus[k] = true; temp.offer(k); } } } } } } // 返回与i相连的第一个顶点 private int firstAdjvex(int i) { for (int j = 0; j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 返回与i相连的下一个顶点 private int nextAdjvex(int i, int k) { for (int j = (k + 1); j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 测试 public static void main(String args[]) { new bfs().BFS(); } }
demo2
static int[][] nums = { { 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0}, { 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0}, { 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0}, { 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0}, { 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0}, { 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1}, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0} }; static String res[] = {"1","2","3","4","5","6","7","8","9" };
对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
1 2 3 4 5 6 7 8 9
广搜结果
1 2 8 3 5 6 9 4 7
深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。
深搜遍历过程
从1开始搜索可以看到1的子节点有2、8两个，进程会依次对其进行深度优先搜索
进程先对2进行子节点的搜索可以看出2也有两个子节点3、5
然后进程又会对3进行子节点的搜索可以看出只有一个子节点4，而4没有子节点了这个时候进程就会回溯到2的位置然后对5进行子节点的搜索
可以看出5的子节点也是只有一个4，但是这个时候5还有一个父节点6没有被访问所以进程不会回溯到2的位置
而是对6进行子节点的搜索，6的子节点只有一个7这个时候进程又会发现6有父节点8没有访问过
所以进程会对8再次再次进行子节点的搜索，发现子节点只有6和9但是6已经访问过了，而9也没有子节点
到这里树的所有节点就完成了全部的探索了
广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点1开始，会发现1的子节点有2、8两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点
对2、8完成访问之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们的子节点有3、5、6、9
然后进程对着4个节点完成遍历之后会再次探寻其的子节点可以看出只有4和7了且无子节点
在对4和7完成遍历之后整个进程也就随之结束了
深搜代码
public class dfs { // 构造图的边 private int[][] edges = { { 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0}, { 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0}, { 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0}, { 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0}, { 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0}, { 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1}, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0} }; // 构造图的顶点 private String[] vertexs = {"1","2","3","4","5","6","7","8","9"}; // 记录被访问顶点 private boolean[] verStatus; // 顶点个数 private int vertexsNum = vertexs.length; public void DFSTra() { verStatus = new boolean[vertexsNum]; for (int i = 0; i < vertexsNum; i++) { if (verStatus[i] == false) { DFS(i); } } } // 递归深搜 private void DFS(int i) { System.out.print(vertexs[i] + " "); verStatus[i] = true; //深度搜索子节点 for (int j = firstAdjVex(i); j >= 0; j = nextAdjvex(i, j)) { if (!verStatus[j]) { DFS(j); } } } // 返回与i相连的第一个顶点 private int firstAdjVex(int i) { for (int j = 0; j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 返回与i相连的下一个顶点 private int nextAdjvex(int i, int k) { for (int j = (k + 1); j < vertexsNum; j++) { if (edges[i][j] == 1) { return j; } } return -1; } // 测试 public static void main(String[] args) { new dfs().DFSTra(); } }
广搜代码
import java.util.LinkedList; import java.util.Queue; public class bfs { // 构造图的边 private int[][] edges = { { 0 , 1 , 0 , 0 , 0 , 0 , 0, 1 , 0}, { 1 , 0, 1 ,0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 1 , 0 ,0 , 0 , 0 , 0}, { 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 ,0}, { 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0}, { 0 , 0 , 0 , 0 , 0 , 1, 0 , 0 , 0}, { 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1}, { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0} }; // 构造图的顶点 private String[] vertexs = {"1","2","3","4","5","6","7","8","9"}; // 记录被访问顶点 private boolean[] verStatus; // 顶点个数 private int vertexsNum = vertexs.length; // 广搜 private void BFS() { verStatus = new boolean[vertexsNum]; Queue<Integer> temp = new LinkedList<Integer>(); //遍历每个节点 for (int i = 0; i < vertexsNum; i++) { //判断当前节点是否被访问过 if (!verStatus[i]) {//如果没有被访问的话则将其加入队列 System.out.print(vertexs[i] + " "); verStatus[i] = true; temp.offer(i); while (!temp.isEmpty()) { //将最先进入队列的节点移除 int j = temp.poll(); //广度搜索子节点 for (int k = firstAdjvex(j); k >= 0; k = nextAdjvex(j, k)) { if (!verStatus[k]) { System.out.print(vertexs[k] + " "); verStatus[k] = true; temp.offer(k); } } } } } } // 返回与i相连的第一个顶点 private int firstAdjvex(int i) { for (int j = 0; j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 返回与i相连的下一个顶点 private int nextAdjvex(int i, int k) { for (int j = (k + 1); j < vertexsNum; j++) { if (edges[i][j] > 0) { return j; } } return -1; } // 测试 public static void main(String args[]) { new bfs().BFS(); } }
