我有一个无向连通图 . 我使用邻接矩阵实现了它,它是一个二维数组 .
据我了解,DFS在兄弟姐妹之前访问子节点 . BFS在孩子面前拜访兄弟姐妹 .
我这样实现了这两个:
public void DFT(int firstVertex) {
connectedVertices = 0;
int v;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < numVertices; i++) {
if(vertex[i] != null){
vertex[i].setPushed(false);
}
}
stack.push(firstVertex);
connectedVertices++;
vertex[firstVertex].setPushed(true);
while(!stack.isEmpty()){
v = stack.pop();
vertex[v].visit();
for (int i = 0; i < numVertices; i++) {
if(adj[v][i] != 0 && !vertex[i].getPushed()){
stack.push(i);
connectedVertices++;
vertex[i].setPushed(true);
}
}
}
}
public void BFT(int firstVertex) {
connectedVertices = 0;
int v;
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numVertices; i++) {
if(vertex[i] != null){
vertex[i].setPushed(false);
}
}
queue.add(firstVertex);
connectedVertices++;
vertex[firstVertex].setPushed(true);
while(!queue.isEmpty()){
v = queue.remove();
vertex[v].visit();
for (int i = 0; i < numVertices; i++) {
if(adj[v][i] != 0 && !vertex[i].getPushed()){
queue.add(i);
connectedVertices++;
vertex[i].setPushed(true);
}
}
}
}
因为这些方法只需要一个参数,即起始顶点 . 如果我被要求将DFS和BFS从一个节点提供给另一个节点怎么办?这是一个连接的无向图的简单例子 .
如果我被要求从D到E执行DFS,那么它是D,C,A,E还是D,E . 我以为DFS和BFS必须访问每个节点,在这种情况下B不能被访问 . 我不知道如何改变我目前的方法来满足这些要求 .
1 回答
如果您先访问C或E,我不确定这是否真的很重要 . 他们都是D的孩子,对吗?它是特定于实现的行为,DFS没有定义您首先访问的子项 .
在DFS中,如果您先选择孩子C,那么您应该在访问E之前访问A.
在BFS中,您应该在访问A或B之前访问过E和C.