demo3
static int[][] nums = { { 0 , 1 , 1 , 1 , 0 , 0 , 0}, { 1 , 0 , 1 , 0 , 0 , 1 , 0}, { 1 , 1 , 0 , 1 , 1 , 0 , 0}, { 1 , 0 , 1 , 0 , 0 , 0 , 1}, { 0 , 0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 0 , 0 , 0 , 1}, { 0 , 0 , 0 , 1 , 0 , 1 , 0}, }; static String res[] = { "v1", "v2", "v3", "v4", "v5", "v6", "v7" };
对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
v1 v2 v3 v4 v7 v6 v5
广搜结果
v1 v2 v3 v4 v6 v5 v7
深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。
深搜遍历过程
从v1开始搜索可以看到a的子节点有v2、v3、v4系统会依次对其进行深度优先搜索
进程先对v2进行子节点的搜索可以看出v2有两个子节点v3、v4
进程会先对v3进行遍历会发现v3的子节点只有v4，然后v4只有一个子节点v7
进程遍历到v7的时候因为v7还有一个父节点v6没有被访问所以进程会走到v6的位置因为v6的根节点已经遍历了
所以进程会返回到发现v6这条边的起始点也就是v1，但是这个时候还有节点没有被遍历所以
进程会随便选择一个未发现的节点进入然后遍历从图中看出只有v5没有遍历了所以
对v5进行遍历之后进程也就随之结束了
广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点v1开始，会发现v1的子节点有v2、v3、v4三个子节点，进程会先对这三个节点进行访问然后再遍历其的子节点
对v2、v3、v4完成访问之后则会探寻这三个节点的子节点并对其进行遍历，可以从图中看出他们未访问的子节点只有v6、v5、v7
而v6、v7、v5没有子节点了所以程序对其遍历之后随之结束
深搜代码
public class dfs { private int[][] edges = { { 0 , 1 , 1 , 1 , 0 , 0 , 0}, { 1 , 0 , 1 , 0 , 0 , 1 , 0}, { 1 , 1 , 0 , 1 , 1 , 0 , 0}, { 1 , 0 , 1 , 0 , 0 , 0 , 1}, { 0 , 0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 0 , 0 , 0 , 1}, { 0 , 0 , 0 , 1 , 0 , 1 , 0}, }; // 构造图的顶点 private String[] vertexs = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"}; // 记录被访问顶点 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 , 1 , 1 , 0 , 0 , 0}, { 1 , 0 , 1 , 0 , 0 , 1 , 0}, { 1 , 1 , 0 , 1 , 1 , 0 , 0}, { 1 , 0 , 1 , 0 , 0 , 0 , 1}, { 0 , 0 , 1 , 0 , 0 , 0 , 0}, { 0 , 1 , 0 , 0 , 0 , 0 , 1}, { 0 , 0 , 0 , 1 , 0 , 1 , 0}, }; // 构造图的顶点 private String[] vertexs = {"v1", "v2", "v3", "v4", "v5", "v6", "v7"}; // 记录被访问顶点 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(); } }
demo4
static int[][] nums = { { 0 , 1 , 1 , 0 ,0 ,0}, { 1 , 0 ,1 , 1 ,0, 0}, { 1 , 1 , 0 ,1 , 1 , 0}, { 0 , 1 , 1 , 0 , 1 , 1}, { 0 , 0 , 1 , 1 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0}, }; static String res[] = { "a", "b", "c", "d", "e", "f"};
对此二维数组进行深度搜索与广度搜索，并遍历结果。
深搜结果
a b c d e f
广搜结果
a b c d e f
深搜的遍历过程就是尽可能深的搜索树的分支，当一个节点的所有子节点都被探寻过了，搜索将回溯到发现该节点的那那条边的起始节点
这个过程会一直持续到已发现节点可到达所有节点为止。
如果还存在未发现的节点则进程会随便选择一个未发现的节点重复以上的过程
整个进程直到所有节点都被访问过为止。
深搜遍历过程
从a开始搜索可以看到1的子节点有b、c两个，进程会依次对其进行深度优先搜索
进程先对b进行子节点的搜索可以看出b也有两个子节点c、d
然后进程又会对c进行子节点的搜索可以看出它也是有两个子节点d、e
进程又会查找d的子节点可以发现d也有两个子节点e、f
这个时候e和f都没有子节点了树的所有节点也都被遍历了
广搜遍历过程
和深搜不同广搜会沿着树的高度和宽度对节点进行依次遍历
从树的根节点a开始，会发现a的子节点有b、c两个子节点，进程会先对这两个节点进行访问然后再访问其的子节点
对b、c完成遍历之后进行则会探寻这两个节点的子节点并对其进行遍历，可以从图中看出他们未遍历的子节点有d、e
然后进程对着2个节点完成遍历之后会再次探寻其的子节点
可以看出只有一个f了且f没有子节点所以程序对f完成遍历之后整个进程也就随之结束了
深搜代码
public class dfs { // 构造图的边 private int[][] edges = { { 0 , 1 , 1 , 0 ,0 ,0}, { 1 , 0 ,1 , 1 ,0, 0}, { 1 , 1 , 0 ,1 , 1 , 0}, { 0 , 1 , 1 , 0 , 1 , 1}, { 0 , 0 , 1 , 1 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0}, }; // 构造图的顶点 private String[] vertexs = { "a", "b", "c", "d", "e", "f"}; // 记录被访问顶点 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 , 1 , 0 ,0 ,0}, { 1 , 0 ,1 , 1 ,0, 0}, { 1 , 1 , 0 ,1 , 1 , 0}, { 0 , 1 , 1 , 0 , 1 , 1}, { 0 , 0 , 1 , 1 , 0 , 0}, { 0 , 0 , 0 , 1 , 0 , 0}, }; // 构造图的顶点 private String[] vertexs = { "a", "b", "c", "d", "e", "f"}; // 记录被访问顶点 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(); } }
