时间戳

首页 > 解决方案 > 图路径中未访问的邻居

algorithm - 图路径中未访问的邻居

问题描述

我试图在无向图中查找距离，但是当导航到不同的路径时，无法正确计算计数。

我不确定什么是最好的方法：

1) 计算排除不必要路径的路径值。

2）保持路径（我认为使用LinkedList或ArrayList等这种情况的最佳选择是什么。

任何帮助，将不胜感激。

标签： algorithmdata-structuresgraph

解决方案

这是解决此问题的代码：

void Measure(Node node)
{
    path.Add(node);
    node.IsVisited = true;

    if (node != destination)
    {
        foreach (var neighbor in node.Neighbors.Where(n=>!n.IsVisited))
        {
            Measure(neighbor);
        }
        path.RemoveAt(path.Count - 1);
    }
}

您可以使用任何动态长度结构，例如 List 或 LinkedList 来存储路径。为简单起见，推荐使用列表。

用法：

var path = new List<Node>()
Measure(firstNode);
Print(path.Count);

如果两个节点之间有路径，则此方法有效。否则路径为空。

class Node
{
     public string Name { get; set; }
     public bool IsVisited { get; set; }
     public List<Node> Neighbors { get; set; } = new List<Node>();
}

推荐阅读