Improve Graph Adjacency List Implementation and Operations

I am studying graphs and I am trying to make a library in C# for myself and anyone else interested, that is didactic and simple, so I can remember how to solve common problems.

I would like to improve it.

How can I improve, for example, the DFS, complete the Prim's algorithm and implement the Kruskal's and Dijkstra's algorithms ?

Create an interface that can be derived for representing different kinds of graphs, like Undirect and Direct Graph, for example.

public interface IGraph
{
            void InsertDirectEdge(int edgeAKey, int edgeBKey,int weight = 0);
            void IsertNewVertex(int vertexKey);
            bool ExistKey(int vertexKey);
            Vertex InitializeDFS(int vertexKeyToFind);
            bool MakeItBipartite();
            Vertex DFS(Vertex root, int vertexKeyToFind);
            void FindNumberOfConnectedComponents();
            void BFS(int startVertexKey);
            Vertex InitialiazeBFS(int vertexKeyToFind);
            bool IsVisited(Vertex v);

            Vertex MarkVertexAsVisited(Vertex v);
            Vertex GetFirstElementOfTheList(int findKey);
            void InsertUndirectedEdge(int vertexAKey, int vertexBKey, int Weight = 0);
            GraphDirect PrimAlgorithm();
            Vertex FindByKey(int vertexKey);
        }

Created a direct graph, with a Dictionary to represent a Graph Adjacency List, where the key is an integer.

```
public class GraphDirect : IGraph
{
private Dictionary Vertices { get; set; }

//For use on the DFS to "break" the recursion.
private bool finished;

public GraphDirect()
{
Vertices = new Dictionary();
}

//Initialize all vertices with Unvisited value.
private void InitializeVertices()
{
foreach(int key in this.Vertices.Keys)
{
this.Vertices[key].Status = State.UnVisited;
}

You have put too many responsibilities in a single interface and class. Your IGraph interface knows not only about graph itself, but also about all the possible methods of traversing this graph. It breaks Single-responsibility principle, Open/closed principle (as you'll have to edit Graph if you want to add more search methods) and Interface segregation principle.

What you should do is refactor your interface and implementation so that:

• There is an interface IGraph that describes all necessary methods and properties of a graph, i.e. ability to get adjacent vertices of a certain vertex, and methods of mutating a graph if needed (I would start with immutable graph first). Also I would add a generic parameter that defines the type of vertices. It should not include any functionality related to methods of traversing the graph, that is no BFS/DFS/Bipartite etc.

• Graph class should not contain any data related to searching, that is no Visited states, no colors, etc.

• Define a new class for each method of working with graph, e.g. BreadthFirstSearch class, DepthFirstSearch class, etc. Each of those should work with IGraph and store information required for their processing, e.g. all those vertex visited states, etc. If there is some common functionality (like visited states) you may introduce a base class that all others will inherit from.

That will make your code decoupled, different graph traversal methods would be independent from others, and code would be much easier to read and understand.

Example of Graph and BreadthFirstSearch implementation:

public interface IGraph
{
    bool Contains(TVertex vertex);
    IEnumerable GetAdjacent(TVertex vertex);
}

public class Graph : IGraph
{
    private readonly Dictionary> _edges;

    public Graph(params Tuple[] directEdges)
    {
        _edges = directEdges
            .GroupBy(tuple => tuple.Item1, tuple => tuple.Item2)
            .ToDictionary(g => g.Key, g => g.ToList());

        //Adding vertices that are used as a target to the list of available vertices
        foreach (var missingVertex in directEdges
            .Where(tuple => !_edges.ContainsKey(tuple.Item2))
            .Select(tuple => tuple.Item2))
        {
            _edges[missingVertex] = new List();
        }
    }

    public bool Contains(TVertex vertex)
    {
        return _edges.ContainsKey(vertex);
    }

    public IEnumerable GetAdjacent(TVertex vertex)
    {
        List adjacentVertices;
        return _edges.TryGetValue(vertex, out adjacentVertices) ? adjacentVertices : Enumerable.Empty();
    }
}

public class BreadthFirstSearch
{
    private readonly IGraph _graph;

    public BreadthFirstSearch(IGraph graph)
    {
        _graph = graph;
    }

    public IEnumerable GetAllReachableVertices(TVertex startingVertex)
    {
        HashSet visited = new HashSet { startingVertex };
        Queue horizon = new Queue { startingVertex };

        while (horizon.Count > 0)
        {
            var nextVertexToExpand = horizon.Dequeue();
            yield return nextVertexToExpand;

            foreach (var vertex in _graph.GetAdjacent(nextVertexToExpand).Where(vertex => !visited.Contains(vertex)))
            {
                visited.Add(vertex);
                horizon.Enqueue(vertex);
            }
        }
    }
}

Usage:

public class Program
{
    public static void Main()
    {
        var graph = new Graph(
            Tuple.Create(2, 7),
            Tuple.Create(7, 4),
            Tuple.Create(4, 6),
            Tuple.Create(8, 3),
            Tuple.Create(6, 2));

        var breadthFirstSearch = new BreadthFirstSearch(graph);

        foreach (var vertex in breadthFirstSearch.GetAllReachableVertices(4))
        {
            Console.WriteLine("Next vertex is {0}", vertex);
        }
    }
}

StackExchange Code Review Q#19580, answer score: 4