Connected components in an undirected graph in C#

My knowledge in graph theory is very limited. I have to look for elements in an (undirected) graph who are in the same connected component.

The idea is simple. First, build the graph. Then, allocate a "color" to a point and spread it to its neighbours recursively. Once there are no neighbours to color any more, pick a point without any color and repeat the same process. This ends when all the points have a color.

I wrote the following class :

```
using System.Collections.Generic;
using System.Linq;

namespace ConnectedComponents
{
public class UndirectedGraph
{
private Dictionary> _graph;
private Dictionary _colors;

public UndirectedGraph()
{
_graph = new Dictionary>();
}

private int SpreadColorFromPoint(int p1, int color, HashSet visitedVertices)
{

if (_colors.ContainsKey(p1))
{
_colors[p1] = color;
}
else
{
_colors.Add(p1, color);
}

visitedVertices.Add(p1);

foreach (int vertex in _graph[p1])
{
if (visitedVertices.Contains(vertex)) continue;
SpreadColorFromPoint(vertex, color, visitedVertices);
}

return visitedVertices.Count;
}

private void AddEdge(int p1, int p2)
{
if (_graph.ContainsKey(p1))
{
_graph[p1].Add(p2);
}
else
{
_graph.Add(p1, new List() { p2 });
}
}

public int Count
{
get
{
return _graph.Count;
}
}

public void AddUndirectedEdge(int p1, int p2)
{
AddEdge(p1, p2);
AddEdge(p2, p1);
}

public void Color()
{
int color = 1;
_colors = new Dictionary();
foreach (int key in _g

I’m not going to comment about tests.

Braces and Casing

Overall good use of braces and casing, though you slip a few times. In your Color method, I would suggest braces inside the foreach:

if (!_colors.ContainsKey(key))
{
    visited = SpreadColorFromPoint(key, color, new HashSet());
}

Naming

Naming could be better, e.g. p1 in methods without a p2 could simple be point. In methods with a p1 and p2, you could use point1 and point2 as names.

Code Changes

In SpreadColorFromPoint, I think this:

else
{
    _colors.Add(p1, color);
}

visitedVertices.Add(p1);

should be:

else
{
    _colors.Add(p1, color);
    visitedVertices.Add(p1);
}

If you are using C# 6.0 or better, the Count property could be shortened to:

public int Count => _graph.Count;

Likewise, CountConnectedComponents could be a one-liner as well.

public int CountConnectedComponents() => _colors.Values.Distinct().Count();

On one hand, this is proper to be a method in that it must take a wee-bit of time for .Distinct().Count(). On the other hand, if _colors was to be small enough, you may consider making it ConnectedComponentsCount property. Note that "Count" in the beginning is a verb and "Count" on the end is a noun.

Color: A verb or a noun?

Speaking of nouns vs verbs, for the Color method, I take issue with the name since whenever I see Color I tend to think of a the Color structure. Perhaps AppyColor or GenerateColors are suitable as action verbs. Granted “color” can be a verb or a noun, but again most developers may think noun.

That said, I don’t see where you do anything useful with visited. Looking at it further, there is no need that SpreadColorFromPoint should return a value. That would shorten up code in the Color (or GenerateColors) method.

StackExchange Code Review Q#132730, answer score: 3