首页 文章

查找两个节点之间是否存在深度优先搜索

提问于
浏览 次
3

我正在使用深度优先搜索和图表来查找是否存在2个节点之间的路由 . 但由于某种原因，即使有路径，我的方法总是会导致错误 .

Here is my search code:

static boolean search(Graph g, Node start, Node end)
{

if(start == null || end == null) return false;

start.state = State.Visited;

for(Node u: start.getChildNodes())
{
    if(u.state != State.Visited)
    {
        if(u.equals(end))
        {
            return true;
        }
        else
        {
            u.state = State.Visited;
            search(g,u,end);
        }
    }
}

return false;

}

I am calling the method like this:

public static void main(String[] args) {

        Graph gDfs = createNewGraph();

        System.out.println("path between A & B");
        System.out.println(search(gDfs,gDfs.getNode()[0],gDfs.getNode()[1]));
    }

createNewGraph()

public static Graph createNewGraph()
{

Graph g = new Graph();        
Node[] temp = new Node[8];

temp[0] = new Node("A", 3);
temp[1] = new Node("B", 3);
temp[2] = new Node("C", 1);
temp[3] = new Node("D", 1);
temp[4] = new Node("E", 1);
temp[5] = new Node("F", 1);

temp[0].addChildNode(temp[1]);
temp[0].addChildNode(temp[2]);
temp[0].addChildNode(temp[3]);

temp[1].addChildNode(temp[0]);
temp[1].addChildNode(temp[4]);
temp[1].addChildNode(temp[5]);

temp[2].addChildNode(temp[0]);
temp[3].addChildNode(temp[0]);
temp[4].addChildNode(temp[1]);
temp[5].addChildNode(temp[1]);

for (int i = 0; i < 7; i++) 
{
    g.addNode(temp[i]);
}
return g;

}

@amit =>这是你的建议吗？

for(Node u: start.getChildNodes())
        {
            if(u.state != State.Visited)
            {
                if (search(g,u,end)) return true;
            }
        }
algorithm data-structures graph binary-tree depth-first-search

2 回答

  • 4

    使用当前状态，而不是下一个或流行状态（无论是dfs还是bfs）总是更好 .

    boolean search(Graph g, Node current, Node target)
{

    if (current == null || target == null) return false;

    current.state = State.Visited;

    if (current == target) return true;

    for(Node u: current.getChildNodes())
    {
        if(u.state != State.Visited && search(g,u,target))
        {                
            return true;
        }
    }    
    return false;    
}

    并且某些顶点的“状态”可能未被标记为“State.Visited”，即使它可以从“A”实现 . 它可能会导致一些错误或错误的复杂性估计 . 我建议检查最坏情况

    void search(Graph g, Node v)
{
    v.state = State.Visited;     

    for(Node u: v.getChildNodes())
    {
        if(u.state != State.Visited)
        {                
            search(g,u);
        }
    }        
}

    并检查“B.state”是否为“State.Visited”

    回复于
  • 3

    如果递归调用也是正确的，那么你的递归调用应该结束为true：

    if (search(g,u,end)) return true;

    否则，你不会对从它返回的值做任何事情，并且只会到达 for 循环的末尾并最终产生 false .

    作为旁注，检查当前节点是否为目标节点的更好实践不是在 for 循环中，而是在它之前作为新的停止子句 . 请注意，对于 search(G,start,start) ，您的方法将失败，但每个节点与其自身之间存在一条路径（长度为0） .

    回复于

相关问题