Graphs

Here is a blank graph builder to play with.


Adjecancy list:


    
Adjacancy maitrix:

    

    
Multigraph?

    

    

    
A graph consists of nodes (verticies) and arcs (edges). Most graphs you will see in a textbook are labelled with letters, but numebrs are used in the graph builder as a simple way to allow for unlimited nodes. A multigraph is a graph where two or more arcs between nodes are permitted.

    
    
    
The graphs you can make with the buidler are undirected graphs. Directed graphs (digraphs) have an arrow at the end of a line to show their direction. The graphs build here are also unweighted. This means that each connection does not have a numerical value associated with it.

    
You can represent graphs using an ajacancy maitrix or adjacency list. This allows algorithms to interact with graphs.

    
Here is an example adjacency maitrix for the graph above.


    

      

         
        0
        1
        2
        3
      

      

        0
         
        1
        1
         
      

      

        1
        1
         
        1
         
      

      

        2
        1
        1
         
        1
      

      

        3
         
         
        1
         
      

    


    
In a real computer program, this might be implemented using a two-dimentional array. Because this is an undirected graph, it is symetrical, that is, the value of position [0][1] must be the same as the value of [1][0]. Additionally, there is only nothing or 1 in each entry. In a weighted graph, the value stored would be the weight of the connection, rather than this binary implementation for undirected graphs.

    
[[null, 1, 1, null], [1, null, 1, null], [1, 1, null, 1], [null, null, 1, null]]
 
    
This approach isn't very space-efficient, and this gets worse with a more sparsly-populated digraph. It is however, easier to read by humans. An alternative is an adjacancy list, as shown below.

    
An adjacancy list is more space-efficient but is harder for humans to read. It is implemented as a list of dictionaries.

    
[{1:1, 2:1}, {0:1, 2:1}, {0:1, 1:1, 3:1}, {2:1}]

    
The key is the node which is being connected to. The value is the weight of the connection.

    
Searching algorithms

    
A graph can be traversed using a depth-first or breadth-first traversal.

    
A depth-first traversal starts with a node, then goes along a path until it has no choice but to go back to a node which it has been to before. Along the way, it will have a rule to always turn left or always right at a junction. Once it is at a point where it must visit something it has been to before, it starts going backward along the way it came, until it reaches a junction where it can go somewhere else instead.