CS Level Up Series (30 Part Series)

## Resources

- Graphs Overview
- Graphs Overview
- Another Overview
- Breadth First Search Explanation
- Depth First Search Explanation
- Breadth First Search Implementations
- Depth First Search Implementations
- 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!

CS Level Up Series (30 Part Series)

## Discussion