CODEWITHSUNDEEP
algorithmdata-structuresgraph
Vivin Paliath
Vivin Paliath

Reputation: 95518

Number of connected-components in a undirected graph

I'm going over some graph algorithms (this is not homework; I'm just brushing up on algorithms and data-structures) and I have a question. Assume I have the following undirected graph:

var graph = {
    9: [19, 26],
    13: [19, 5],
    17: [],
    26: [11, 18],
    18: [9],
    19: [],
    23: [24],
    24: [],
    11: [],
    18: []
};

The graph basically looks like this:

enter image description here

How many connected-components are in this graph? From just looking at the graph, it looks like there are 3 components. But if I actually implement the algorithm (iterating over each vertex, and doing a bfs using that vertex as a starting point if that vertex is undiscovered. Also, the bfs will mark any vertex it encounters, as discovered).

If I start with 9, I end up discovering the following nodes: [19, 26, 11, 18]. However, 13 is not discovered because it is not in 19's adjacency list. However, 19 is in 13's adjacency list. This is why I end up with one extra component.

Is this correct? Are there actually 4 separate-components and if so, is my understanding of connected-components wrong?

Upvotes: 5

Views: 4564

Answers (2)

marcadian
marcadian

Reputation: 2618

You can change your adjacency list representation, your representation is 'directed' but your picture is undirected. For edge(a,b) graph {a: [b], b:[a]}

Upvotes: 3

us2012
us2012

Reputation: 16253

The problem is that for adjacency list representations of undirected graphs, you have to either

(1) use symmetric adjacency lists, i.e. when putting in a new edge ab, add b to adjlist[a] and vice versa

or

(2) traverse all vertices' adjacency lists everytim e you're looking for the existence of an edge.

Since (2) is horribly inefficient, you'd usually go with (1). This is also the convention for adj lists used in general. If I were presented with your adj list, I'd assume the graph was directed.

Upvotes: 4

Related Questions