Graphs
Tags: computerscience, algorithms, datastructures, csharp
Published: 2019-12-10 01:39:08

## Resources

1. [Graphs Overview](https://www.interviewcake.com/concept/java/graph)
1. [Graphs Overview](https://bradfieldcs.com/algos/graphs/introduction/)
1. [Another Overview](https://en.wikibooks.org/wiki/A-level_Computing/AQA/Paper_1/Fundamentals_of_data_structures/Graphs)
1. [Breadth First Search Explanation](https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/)
1. [Depth First Search Explanation](https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/)
1. [Breadth First Search Implementations](https://www.techiedelight.com/breadth-first-search/)
1. [Depth First Search Implementations](https://www.techiedelight.com/depth-first-search/)
1. [In Depth Overview + Implementations of all things Graph](https://algs4.cs.princeton.edu/40graphs/)

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](https://www.interviewcake.com/concept/java/graph) 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](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)#Representations) 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:

{% gist https://gist.github.com/jbolton209/c70a2ed4c51948f6049eb51bccf297e6 %}

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