CODEWITHSUNDEEP
c#algorithmgraph
Zag Gol
Zag Gol

Reputation: 1076

Check if all nodes in graph are in distance of <=k from each other

In a given graph, I need to check, if all nodes in graph, are in distance of <=k from each other.

I Wrote a solution (simple C#) that runs with a loop on every node, and then checks that he has a k-distance to all the other nodes, but the time complexity is V * (V + E). There is a more efficient way?

Code :

// 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;
}

Upvotes: 1

Views: 190

Answers (2)

ciamej
ciamej

Reputation: 7068

First of all, your algorithm is actually V * (V + E).

I'm not sure if you can get any better in practice. You could definitely improve your code.

There are algorithms for computing all-pairs shortest paths, e.g., Floyd-Warshall. The fastest one for your case (undirected unweighted graph) is called Seidel's algorithm.

Upvotes: 1

Maxim Rozhok
Maxim Rozhok

Reputation: 31

You can create a matrix from your graph, and then find the lower value in that matrix, it is also useful when you try to find the shorter way between nodes or apply some algorithm to your graph, etc.

Simple example of representing a graph as matrix

Upvotes: 2

Related Questions