Traverse a graph represented in an adjacency matrix

breadth-first-search, c#, depth-first-search, matrix, traversal

Solution

Every problem in computer science except one can be solved by adding more abstraction.

Start by writing the breadth-first-traversal in the most abstract way possible:

void BreadthFirstTraversal(Graph graph, Vertex start)
{
    /* A miracle happens */
}

We have a method that does what we want. Except that it hasn't been written yet. So write it with slightly less abstraction:

void BreadthFirstTraversal(Graph graph, Vertex start)
{
    /* make a queue of vertices */
    /* make a mark set of vertices */
    /* enqueue and mark start */
    /* while the queue is not empty */
        /* dequeue a vertext */
        /* enqueue and mark all the unmarked neighbours of the vertex */
}

Keep on going, removing more and more abstraction.

void BreadthFirstTraversal(Graph graph, Vertex start)
{
    var queue = new VertexQueue();
    var markSet = new VertexMarkSet();
    queue.Enqueue(start);
    markSet.Add(start);
    while(queue.NotEmpty())
    {
        var vertex = queue.Dequeue();
        foreach(Vertex neighbour in graph.ListNeighbours(vertex))
        {
            if (!markSet.Contains(neighbour))
            {
                markSet.Add(neighbour);
                queue.Enqueue(neighbour);
            }
        }
     }
}

OK, now you've got an algorithm that will work for any graph, no matter what its representation internally. So all you have to do is write `ListNeighbours(Vertex)` and you're done. (Assuming that you already know how to write a queue and a set, or are willing to use the types that come with the base class library.) How are you going to do that?

You see how I used abstraction there? I really don't care whether its an adjacency matrix or an adjacency list, all I care about is that the graph provides me the service of giving me the neighbours of a vertex.

So, how are you going to write `ListNeighbours(Vertex)` given your adjacency matrix?

Two possible solutions to investigate:

Make the `Graph.ListNeighbours(Vertex)` method return a `List<Vertex>`. Construct the list and hand it out.

Make it return `IEnumerable<Vertex>` and use `yield return` to yield a sequence of neighbouring vertices.

UPDATE: OK, so how do we actually make a sequence of neighbours out of an adjacency matrix?

Let's suppose that every vertex is numbered, so `Vertex` is really `int`; this is traditionally how things are done with adjacency matrices. We want to take in a vertex -- an int -- and return a sequence of vertices that are its neighbours.

We have an array that has the property that `array[i, j]` is non-zero if vertex `j` is a neighbour of vertex `i`.

Again, start abstract and work your way towards implementation:

public List<int> ListNeighbours(int vertex)
{
    /* a miracle happens */
}

What do we need to do to make that miracle happen?

public List<int> ListNeighbours(int vertex)
{
    /* create a new list */
    /* for each vertex j in the graph */
        /* if j is a neighbour of i then add it to the list */
    /* return the list */
}

Alternatively, you can use `yield return` to create a sequence:

public IEnumerable<int> ListNeighbours(int vertex)
{
    /* for each vertex j in the graph */
        /* if j is a neighbour of i then yield return j */
}

`yield return` iterators tend to be simpler, but beginner programmers often have a hard time sussing out the control flow. Try writing it both ways and see how it goes.

Problem

Original source