Graphs

Resources

1. Graphs Overview
2. Graphs Overview
3. Another Overview
4. Breadth First Search Explanation
5. Depth First Search Explanation
6. Breadth First Search Implementations
7. Depth First Search Implementations
8. In Depth Overview + Implementations of all things Graph

Takeaways:

• A graph is a data structure used to organize/represent things in an interconnected network.
• Graphs consist of vertices (nodes) and edges.
• An edge is what connects two vertices
• A good example of an interconnected network of vertices and edges is cities and the roads that connect them together. A city in this example would be a vertex, and the roads are the edges.
• Edges can have weights, using our city example the weight could be distance in miles between two vertices (cities).
• The degree of a vertex is how many other vertices it is connected to (I.E how many neighbours/successors it has)
• There are two main types of graph: Undirected and Directed
• Undirected graphs have edges that are bi-directional. In directed graphs the edges have a direction - meaning if vertices A to B are connected by an edge X, the same edge does not connect B to A (in that direction). For an undirected graph, an edge connecting A to B also connects B to A.
• In undirected graphs a vertex is said to have adjacent/neighbouring (neighbours) vertices (all the vertices it is connected to). However, in directed graphs we call the list of vertices it connects to successors. These are often used interchangeably, but if you think about it - when there is an explicit direction (like in directed graphs) it makes sense to call them successors, as the connection (edge) does not go both ways.
• Directed graphs are also called Digraphs
• A loop in a graph is a vertex with an edge connecting to itself
• Multi-edge is when more than one edge connects two vertices
• A simple graph is an undirected graph that has no loops and is not multi-edged.
• A graph is said to be cyclic if it has a cycle. A cycle is when there is a series of edges that connect back to the origin vertex. Similar to a circular linked list, where the tail connects to the head.
• If a graph has no cycles it is acyclic
• Colouring is when each vertex has a colour. Legal colouring is when no adjacent vertices have the same colour.
• The two common ways to represent a graph are: Adjacency List and Adjacency Matrix. I found the visual section on this Interview Cake article the best resource for visualizing these two representations
• Adjacency list is useful when we are working with vertices that are strings/objects and not integers.
• Use adjacency list when the graph has fewer edges than vertices
• Adjacency Matrix is good for graphs with more edges than vertices. It is easy to represent a graph in this way when the vertices are integers.
• Traversing a graph is much like traversing a tree, we use Breadth First Search (BFS) and Depth First Search (DFS)
• As with trees, BFS traverses a graph level by level. DFS traverses a graph depth ways - meaning we start at a vertex and traverse until it has no successors/neighbours, then backtrack until we find a vertex that does and repeat the process.
• Space complexity for an adjacency list is O(v + e), for adjacency matrix it is O(V^2).
• Adding an edge is O(1) for both.
• Removing an edge is O(1) for adjacency matrix and O(e) for adjacency list*
• I found the table on Wikipedia helpful for the big O

*My implementation appears to be O(1). I believe this is because the graph I implemented cannot be multi-edged. This is because instead of a list of edges I used a hash table - speeding up the find operation.

EDIT: Apparently when you use a hash table like I did, the implementation is actually an adjacency map not an adjacency list.

There is a lot more to graphs that I will cover when exploring graph algorithms, but for now below you'll find implementations of Directed & Undirected graphs using both an Adjacency List (Graph) and Adjacency Matrix (Graph2).

Here's are the finished implementation of the Graphs with some test code:

As always, if you found any errors in this post please let me know!