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:
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?
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.
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]}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With