一、图的广度优先搜索
1、图的遍历是怎么定义的？有哪两种常见的方式？
-
图的遍历：由图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次
- 常见的遍历方式有 2 种（有向图、无向图都适用）
- ①广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索
- ②深度优先搜索（Depth First Search，DFS），发明的科学家获得了图灵奖
image.png
2、下图按照广度优先搜索规则分层，动手分一分，要能分清楚？
image.png
image.png
3、广度优先搜索代码实现思路（思路很重要）？
- 参考二叉树的层序遍历
image.png
4、广度优先搜索代码代码实现？
@Override
public void bfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V, E>> visitedVertices = new HashSet<>();
Queue<Vertex<V, E>> queue = new LinkedList<>();
queue.offer(beginVertex);
visitedVertices.add(beginVertex);
while (!queue.isEmpty()) {
Vertex<V, E> vertex = queue.poll();
System.out.println(vertex.value);
vertex.outEdges.forEach((Edge<V, E> edge) -> {
if (!visitedVertices.contains(edge.to)) {
queue.offer(edge.to);
visitedVertices.add(edge.to);
}
});
}
}
二、图的深度优先搜索
1、什么是深度优先搜索（Depth First Search）？
- 之前所学的二叉树前序遍历就是一种深度优先搜索
-
深度优先：①沿着一条路（未走过的）有多深走多深，直到不能走了； ②回退一步；③重复①、②操作；
image.png
2、用深度优先搜索的思想，把下图的所有情况都走一遍？
image.png
image.png
3、既然二叉树的前序遍历也是深度优先的搜索，那么是否可以给我们启发呢？深度优先有哪两种遍历方式？
- 递归遍历
- while 遍历
4、思考下图中的 visitedVertices 变量是否可以写成 ListGraph 的成员变量？
image.png
- 我们不能为了一个方法内部的遍历操作的实现，去污染外部代码
- 所以比较好的是方法内部自己解决
5、DFS 的递归实现
public void dfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
dfs(beginVertex, new HashSet<>());
}
private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
System.out.println(vertex.value);
visitedVertices.add(vertex);
vertex.outEdges.forEach((Edge<V, E> edge) -> {
if (!visitedVertices.contains(edge.to)) {
dfs(edge.to, visitedVertices);
}
});
}
三、深度优先搜索非递归实现
1、递归算法转换成非递归算法的两个思路？
- ①首先抓住递归函数是不断开辟栈空间的，不断开辟的
栈空间其实和栈这种数据结构很相似。 - ②不断开辟，转换成非递归，肯定有个循环，一般是 while 循环。
2、深度优先搜索 - 非递归思路？
核心思路：弹出一条后，将 from 和 to 都加入 stack 中，然后 break；
image.png
3、在搜索遍历过程中，需要把每次遍历到的内容暴露给调用者，在 java 中如何实现？
- 声明一个接口 Visitor 类，再声明一个接口 visit 函数。
- 因为这个接口只有一个函数，所以也可以使用 lambda 表达式进行简写
public interface VertexVisitor<V> {
boolean visit(V v);
}
public abstract void bfs(V begin, VertexVisitor<V> visitor);
public abstract void dfs(V begin, VertexVisitor<V> visitor);
4、DFS 的非递归实现
- 以下是我自己的版本，我怎么觉得我的版本更简单，而且也是正确的丫
public void dfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V, E>> visitedVertices = new HashSet<>();
Stack<Vertex<V, E>> stack = new Stack<>();
Vertex<V, E> vertex = beginVertex;
stack.push(vertex);
visitedVertices.add(beginVertex);
while (!stack.isEmpty()) {
vertex = stack.pop();
System.out.print(vertex.value + "_");
vertex.outEdges.forEach((Edge<V, E> edge) -> {
if (!visitedVertices.contains(edge.to)) {
stack.push(edge.to);
visitedVertices.add(edge.to);
}
});
}
}
- 以下是正规版本
public void dfs(V begin, VertexVisitor<V> visitor) {
if (visitor == null) return;
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V, E>> visitedVertices = new HashSet<>();
Stack<Vertex<V, E>> stack = new Stack<>();
// 先访问起点
stack.push(beginVertex);
visitedVertices.add(beginVertex);
if (visitor.visit(begin)) return;
while (!stack.isEmpty()) {
Vertex<V, E> vertex = stack.pop();
for (Edge<V, E> edge : vertex.outEdges) {
if (visitedVertices.contains(edge.to)) continue;
stack.push(edge.from);
stack.push(edge.to);
visitedVertices.add(edge.to);
if (visitor.visit(edge.to.value)) return;
break;
}
}
}
四、图的基本操作补充
1、在 java 中一边遍历数组，一边删除遍历到的元素要怎么做？如何实现 graph 的 removeEdge 和 removeVertex 方法？
- 使用迭代器删除
for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
Edge<V, E> edge = iterator.next();
edge.to.inEdges.remove(edge);
// 将当前遍历到的元素edge从集合vertex.outEdges中删掉
iterator.remove();
edges.remove(edge);
}
- 实现 graph 的 removeEdge 和 removeVertex 方法
@Override
public void removeEdge(V from, V to) {
Vertex<V, E> fromVertex = vertices.get(from);
Vertex<V, E> toVertex = vertices.get(to);
if (fromVertex == null || toVertex == null) return;
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
if (fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
}
@Override
public void removeVertex(V v) {
Vertex<V, E> vertex = vertices.remove(v);
if (vertex == null) return;
for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();) {
Edge<V, E> edge = iterator.next();
edge.to.inEdges.remove(edge);
// 将当前遍历到的元素edge从集合vertex.outEdges中删掉
iterator.remove();
edges.remove(edge);
}
for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
Edge<V, E> edge = iterator.next();
edge.from.outEdges.remove(edge);
// 将当前遍历到的元素edge从集合vertex.inEdges中删掉
iterator.remove();
edges.remove(edge);
}
}
2、写代码时最好实现成有向图，为什么？
- 因为
有向图可以用来表达无向图 - 无向图却不能用来表达有向图
