Tree Data Structure with Valued Edges

Question

I have a graph of - for example - bus stops and the distances between them.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

AB5: stop A to stop B with distance 5 etc.

Can you suggest a data structure or object design that can support this graph.

My take on this:

A Node - a bus stop in this case - can have one or more routes. A Route has a SourceNode and DestinationNode with a value - the distance. The Node has a Map destination name -> Route.

Then it will be a possible to workout the distance for A-B-C which is 9.

Answer 1

There are several data structures to represent a graph: Wikilink

If you would choose Adjacency matrix, you would have a n*n matrix where each slot would represent a distance between 2 vertices. I prefer this representation, when you know the number of vertices ( preferably not too many, so that your matrix doesn't take too much space). It is easy to find the distance between 2 vertices, as well as updating distance, if you need to. But if you are not sure about the number of vertices, or that number might grow in the future, other representation would be a better choice.

Here is some code snippet:

    static void Main(string[] args)
        {
            int length = 7; //number of vertices
            int [,] Matrix = new int[length-1,length-1];
            //instantiate Matrix with 0's
            for(int i = 0; i < length; i++)
            {
                for(int j = 0; j < length; j++)
                {
                    Matrix[i,j] = 0;
                }
            }
            // Import your distances:
            Matrix[0, 1] = 5; // AB5
            Matrix[1, 2] = 4; //BC4 and so on..

        }

Hope you get the idea on how to continue. If you have a lot of data to input, you might want to read it from some file and fill up data in Matrix iteratively.