深度优先搜索（Depth-First-Search，简称DFS）：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发（具体是左，右，上，下，顺时针方向什么的都可以，统一就行），遇到访问过的节点（数组保存所有访问过的节点）或者是没有路（该节点向下没有邻接点）就回退到上一节点（栈），已上一个节点为当前节点继续向下搜索，重复（2）；
（3）若此时图中尚有顶点未被访问（改节点只有出度没有入度，从任何节点都不能到达），则从一个未被访问的顶点出发，重新进行（1），直到图中所有顶点均被访问过为止。
for (int i = 0; i < index; i++) {//for: 尚有顶点未被访问（改节点只有出度没有入度，从任何节点都不能到达）
if (!visiabed[i])
dfs(i);
}
private void dfs(int index) {Stack stack = new Stack<>();
if (!visiabed[index]) {//元素没有访问过
System.out.println(vertex[index]);
visiabed[index] = true; // 入栈
stack.push(index);
}
for (int i = getFirst(index); i >= 0; i = getFirst(i)) {//第一个邻接点
if (!visiabed[i]) {
System.out.println(vertex[i]);
visiabed[i] = true;// 入栈
stack.push(i);
} else {// 遇到访问过的元素就回退, 以栈顶的2个元素向后查找下一个邻接点
while (stack.size() > 1) {
int pre = stack.pop();
int ret = keyNext(stack.peek(), pre); //while 没有路了回退(该点从栈顶向后找不到下一个邻接点)
if (ret >= 0) {//找到下一个邻接点 该点为当前点递归
dfs(ret);
break;
}
}
if (stack.size() == 1) {// 自己指向自己(从头开始找，有改进)
dfs(stack.pop());
}
break;
}
}
}
广度（宽度）优先搜索（ Breadth First Search，BFS ）：
1、把节点的所有邻接点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有邻接点，把它们放到队列的末尾。重复（2）直到队列为空。
4、若此时图中尚有顶点未被访问（改节点只有出度没有入度，从任何节点都不能到达），则从一个未被访问的顶点出发，重新进行（1）
for (int i = 0; i < index; i++) {// for: 尚有顶点未被访问（改节点只有出度没有入度，从任何节点都不能到达）
if (!visiabed[i])
bfs(i);
}
private void bfs(int index) {//类似树（不换行）的层次遍历
LinkedList que = new LinkedList<>();
if (!visiabed[index]) {// 元素没有访问过
System.out.println(vertex[index]);
visiabed[index] = true;
que.offer(index); //队尾
}
for (int i = getFirst(index); i >= 0; i = keyNext(index, i)) {// 该点的所有邻接点入队
if (!visiabed[i]) {
System.out.println(vertex[i]);
visiabed[i] = true;
que.offer(i);
}
}
que.poll();
if (!que.isEmpty())//
bfs(que.peek());
}
网友评论