c# - 检查图中所有节点之间的距离是否 <=k

Question

在给定的图中，我需要检查图中的所有节点之间的距离是否为 <=k。

我写了一个解决方案(简单的 C#)，在每个节点上运行一个循环，然后检查他到所有其他节点的距离是否为 k，但时间复杂度为 V * (V + E)。 有更高效的方法吗？

代码:

// node defenition
public class GraphNode
{
   public GraphNode(int data, List<GraphNode> neighbours)
   {
        Data = data;
       Neighbours = neighbours;
   }
}

// Loop on every Node, and find all k-distance neighbours
public bool IfAllGraphNodesInKdistance1(List<GraphNode> nodes, int k)
{
    for(int i=1; i< nodes.Count; i++)
    {
         if(FindKdistanceNeighboursInGraph(nodes[i], k).Count != nodes.Count)
                return false;
        }
        return true;
    }
}


// Find k-distance neighbours of a Node
public HashSet<GraphNode> FindKdistanceNeighboursInGraph(GraphNode node, int distance )
{

    HashSet<GraphNode> resultHash = new HashSet<GraphNode>();

    if (node != null && distance > 0)
    {
        HashSet<GraphNode> visited = new HashSet<GraphNode>();
        Queue<GraphNode> queue1 = new Queue<GraphNode>();
        Queue<GraphNode> queue2 = new Queue<GraphNode>();
        queue1.Enqueue(node);
        visited.Add(node);
        int currentDistance = 0;
        while (queue1.Count > 0 && currentDistance < distance)
        {
            GraphNode current = queue1.Dequeue();
            foreach (GraphNode graphNode in current.Neighbours)
            {
                if (!visited.Contains(graphNode))
                {
                    queue2.Enqueue(graphNode);
                    visited.Add(graphNode);
                    resultHash.Add(graphNode);
                }
            }
            if (queue1.Count == 0)
            {
                queue1 = queue2;
                queue2 = new Queue<GraphNode>();
                currentDistance++;
            }
        }
    }
    resultHash.Add(node); // if it will include current
    return resultHash;
}

Answer 1

你可以从你的图中创建一个矩阵，然后在该矩阵中找到较低的值，当你试图找到节点之间的较短路径或对你的图应用某种算法等时，它也很有用。

Simple example of representing a graph as matrix