时间戳

首页 > 解决方案 > 如何开发一个自定义遍历算法来遍历图深度优先和广度其次？

algorithm - 如何开发一个自定义遍历算法来遍历图深度优先和广度其次？

问题描述

问题

您好，我是 DFS 和 BFS 的新手。今天一个新问题让我感到困惑：这个问题要求我开发一个自定义遍历算法，遍历图的深度优先和广度其次。这意味着你必须做这样的事情：遍历是深度优先的，直到它到达一个叶子节点。当它这样做时，它选择的下一个节点是遍历开始的根的下一个子节点。换句话说，选择类似于广度优先，即按顺序选择根的孩子。

我的想法

如果我有这样的图表：

[
 [1, 1, 2],
 [2, 3, 4], 
 [3, 5, 6], 
 [4],
 [5],
 [6],
 [7]
 ];

我认为应该像这样遍历图表： 图表

然而

但是，我不知道如何编写代码，因为我不知道： 1.如何知道遍历是否到达叶节点？2.我可以简单地调用BFS()和DFS()函数来编写代码吗？

如果您能帮助我，我将不胜感激！

标签： algorithmgraph

解决方案

  1. 如果你解决图问题，你应该知道图的边，如果你知道边，你可以找到没有任何边的节点，即叶节点。

  2. 不，我认为不会。如果您调用 BFS 和 DFS，如果您不做任何更改，BFS 和 DFS 只会遍历您的所有图表。

    我认为您只需要基于 BFS 和 DFS 构建自己的算法。我可以提供一个。这里有一些用 C# 编写的代码示例，试图做你的问题中描述的 rhat，深度优先，广度其次。

public static List<Node> DepthFirstBreathNext(Node startNode)
{
    var visitedNodes = new HashSet<Node>();
    var orderedVisited = new List<Node>();
    var depthStack = new Stack<Node>();
    var breadthQueue = new Queue<Node>();
    depthStack.Push(startNode);
    while (depthStack.Count > 0 || breadthQueue.Count > 0)
    {

        // Do depth-first while don't get to leaf
        while (depthStack.Count > 0)
        {
            var currentNode = depthStack.Pop();
            visitedNodes.Add(currentNode);
            orderedVisited.Add(currentNode);
            if (currentNode.PointTo == null || currentNode.PointTo.Where(x => !visitedNodes.Contains(x)).Count() == 0)
                break;

            // Push first node to the stack for depth-first
            depthStack.Push(currentNode.PointTo.Where(x => !visitedNodes.Contains(x)).First());

            // Push other nodes to the queue for breadth-next
            foreach (var node in currentNode.PointTo.Where(x => !visitedNodes.Contains(x)).Skip(1))
            {
                breadthQueue.Enqueue(node);
            }
        }

        // Do the breadth-next. Push to the stack first node from breadth queue.  
        if (breadthQueue.Count > 0)
        {
            while (visitedNodes.Contains(breadthQueue.Peek()))
            {
                breadthQueue.Dequeue();
            }

            if (breadthQueue.Count > 0)
            {
                depthStack.Push(breadthQueue.Dequeue());
            }
        }
    }

    return orderedVisited;
}

推荐阅读