首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >检查图中的所有节点是否都在<=k距离内

检查图中的所有节点是否都在<=k距离内
EN

Stack Overflow用户
提问于 2019-05-26 05:49:54
回答 2查看 90关注 0票数 1

在给定的图中,我需要检查图中的所有节点是否都在<=k距离内。

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

代码:

代码语言:javascript
运行
复制
// 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;
}
EN

回答 2

Stack Overflow用户

发布于 2019-05-26 06:49:29

您可以从您的图创建一个矩阵,然后在该矩阵中找到较低的值,当您尝试查找节点之间的较短路径或将某些算法应用于您的图等时,它也很有用。

Simple example of representing a graph as matrix

票数 2
EN

Stack Overflow用户

发布于 2019-05-26 06:52:47

首先,你的算法实际上是V* (V + E)。

我不确定你是否能在实践中变得更好。你绝对可以改进你的代码。

存在用于计算所有对最短路径的算法,例如Floyd-Warshall。对于您的情况(无向无权重图),最快的算法称为Seidel算法。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56309005

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档