CODEWITHSUNDEEP
javaalgorithm
abx23
abx23

Reputation: 31

How do you calculate the number of connected graphs?

Given an array of node and an array of edges, how do you calculate the number of connected graphs?

Upvotes: 3

Views: 3124

Answers (5)

efficiencyIsBliss
efficiencyIsBliss

Reputation: 3093

For undirected graphs, this can be done in O(n) time, with a simple DFS. Here's how:

Define explore as a procedure that finds all the nodes that can be reached from a given node. This is just a recursive DFS-like procedure where at each node, you find all the children of that node and push them onto the stack.

To find the answer, start the DFS at any node and initiate the explore procedure on that node. Keep an integer(lets say cc) and pass it to the explore procedure every time it is called. Also, keep a hashmap/dictionary or such that maps cc to the corresponding node. At each level of the explore procedure, map the current node to cc at the moment. Every time the explore procedure is called recursively, pass it the same value of cc.

Every time explore returns to the DFS loop, increment cc and pass that value the next time. Once you are done with the entire DFS, you will have a dictionary that maps each node to it's corresponding connected component number. The value of cc at the end of this procedure can give you the number of connected components there are in the graph.

Here's the pseudo-code:

function explore(node, graph, cc, map){
    map(currentNode) = cc
    //find all children of current node, and push onto stack. 
    //mark current node as visited
    for i in stack:
        explore(i, graph, cc, map)
}

function DFS{
     int cc = -1
     for node in keysOfGraph:
          if not visited:
              cc++
              explore(node, graph, cc, map)

return cc
}

From Dasgupta Algorithms (section 3.2.3)

Upvotes: 0

Voo
Voo

Reputation: 30235

To elaborate on quasiverse's answer, here's a short pseudo code for it:

make_set(v) creates a new set whose only member is v.

union(x, y) unites the two sets x and y. The representative element for the new set is chosen from one of the two sets

get_representatve(v) returns the representative of the set the given node is a member of.

Find connected components in a graph G = (V, E):

foreach vertex v in V:
    make_set(v)

foreach edge (u, v) in E:
    if get_representatve(u) != get_representatve:
         union(u, v)

Implementing the necessary functions is an exercise for the reader ;-) Anyway it'll work fine for undirected graphs, but if you want strongly connected components you should look at Tarjan's algorithm.

For parallel implementations there exists afaik no work-efficient deterministic algorithm, but some interesting random ones.

Upvotes: 1

Zimbabao
Zimbabao

Reputation: 8250

  • Start at one of the node do the BFS or DFS to get all the nodes connected from this node.
  • Now iterate through the node list to find any node which is not included in already,
  • do the same procedure on the node. Repeat till all the nodes are visited.
  • By now you will have all the graphs in your data.

Upvotes: 1

flight
flight

Reputation: 7272

You can use a union find (you can search it up). Start with all of the nodes as separate sets, then for each edge join the two nodes that the edge connects into the same set. Then check how many different sets there are by going through all the nodes and finding how many different representatives there are.

Upvotes: 1

rlibby
rlibby

Reputation: 6021

Yes, there is an algorithm which is linear in the size of the graph, O(|V| + |E|).

visited := the empty set
count := 0
for each vertex v in vertices:
    if v not in visited:
        count++
        add v and all nodes reachable from v to visited
return count

Upvotes: 0

Related Questions