1
$\begingroup$

I wrote a Java program that builds a graph from an input txt file. The file just has a list of integer pairs constituting an edge between the two vertices (indicated by the two integers). In the Undirected implementation both vertices are marked as having an edge to each other, while in the Directed implementation the first is marked as having an edge to the second.

Everything else seems to line up, but when I calculate the number of connected components using the same input file, but the two implementations, I am getting two results for the number of connected components (specifically the Directed Graph always comes up with more). Intuitively this doesn't make sense to me, since a connected component is just a grouping of connected vertices, it shouldn't matter if those connections are directed or not.

$\endgroup$
4
$\begingroup$

That’s as it should be if you’re calculating strongly connected components of the directed graphs. The graph

$$\bullet\longleftrightarrow\bullet\longleftrightarrow\bullet$$

has one strongly connected component, because each vertex is reachable from each other vertex, but the graph

$$\bullet\longleftarrow\bullet\longleftarrow\bullet$$

has three: any subgraph with more than one vertex has a vertex that cannot be reached from another vertex of the subgraph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.