当前位置: 首页 > 知识库问答 >
问题:

图中两节点之间的深度优先搜索和广度优先搜索

严升
2023-03-14

我有一个无向连通图。我使用邻接矩阵实现了它,它是一个2维数组。

据我所知,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);
            }   
        }
    }

}

如果让我执行一个从D到E的DFS,是D、C、a、E还是D、E。我以为DFS和BFS必须访问每个节点,在这种情况下B不能访问。我不知道我应该如何改变我目前的方法来满足这些要求。

共有1个答案

欧阳意蕴
2023-03-14

我不确定你是先去C还是先去E真的有什么关系。他们都是D的孩子,对吧?它是特定于实现的行为,DFS并不定义您首先访问哪个子级。

在DFS中,如果您先选择子C,那么您应该在访问E之前访问A。

在BFS中,您应该在访问A或B之前访问E和C。

 类似资料:
  • 主要内容:深度优先搜索(简称“深搜”或DFS),广度优先搜索,总结前边介绍了有关图的 4 种存储方式,本节介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种: 深度优先搜索和 广度优先搜索。 深度优先搜索(简称“深搜”或DFS) 图 1 无向图 深度优先搜索的过程类似于树的先序遍历,首先从例子中体会深度优先搜索。例如图 1 是一个无向图,采用深度优先算法遍历这个图的过程为: 首先任意找一个未被遍历过的顶点,例如从 V1 开始,由于 V1 率先访问过了,所以

  • 本文向大家介绍深度优先搜索,包括了深度优先搜索的使用技巧和注意事项,需要的朋友参考一下 图遍历是按某种系统顺序访问图的所有顶点的问题。遍历图主要有两种方法。 广度优先搜索 深度优先搜索 深度优先搜索(DFS)算法从顶点v开始,然后遍历到之前未访问过的相邻顶点(例如x),并将其标记为“已访问”,然后继续处理x的相邻顶点,依此类推。 如果在任何一个顶点上遇到所有相邻顶点都被访问过,则它将回溯直到找到具

  • 我正在研究BFS算法,我有一个关于如何将相邻节点插入队列的问题。 例如,假设我们正在处理一个无向图,我们希望执行BFS来输出图的内容,那么我们如何知道在从队列中取出一个初始节点后,相邻节点以什么顺序插入到队列中呢?还有,有没有办法修改邻居节点插入队列的方式? 任何帮助都将不胜感激,谢谢。

  • 我必须为一个算法开发伪代码,该算法计算给定顶点V和边E的图G=(V,E)中连通分量的数量。 我知道我可以使用深度优先搜索或广度优先搜索来计算连接组件的数量。 但是,我想用最高效的算法来解决这个问题,但是我不确定每个算法的复杂度。 下面是一个用伪代码形式写DFS的尝试。 下面尝试以伪代码形式编写 BFS。 我的讲师说BFS与DFS具有相同的复杂性。 然而,当我搜索深度优先搜索的复杂度时,它是O(V^

  • 3. 深度优先搜索 现在我们用堆栈解决一个有意思的问题,定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线

  • 我正在尝试在有向图上实现BFS。我完全确定我的算法是正确的,但是,下面的代码段返回错误: 图表。CPP文件: 以及在以下方面的实际BFS实施: 因此,除了源节点之外,队列中的其他节点都给出了错误的邻接列表。虽然队列顺序运行良好,但队列中的节点给出了错误的邻接。 我不确定为什么会发生这种情况,虽然我怀疑这是由于按值复制节点而不是引用。 这是我在很长一段时间后的CPP计划,所以如果我错过了什么,请启发