# Graphs

Source: https://wisconsin.twango.dev/sp25-cs400/topics/graphs

# Graphs

Graphs are essentially a set of $V$ vertices and $E$ edges.

## Terminology

- **Vertex**: A node in the graph.
- **Edge**: A connection between two vertices, typically represented as a pair of vertices.
    - A graph is considered **sparse** if the number of edges is approximately $O(V)$, and **dense** if the number of edges is approximately $O(V^2)$.
- **Weights**: A value associated with an edge (optional).
- **Paths**: A sequence of vertices connected by edges.
- **Cycle**: A path that starts and ends at the same vertex.

> [!tip] 
>     A graph is **cyclic** if it contains a cycle, otherwise it is **acyclic**.
>
- **Connected**: A graph is connected if there is a path between every pair of vertices.
    - **Strongly Connected**: A directed graph is strongly connected if there is a path between every pair of vertices.
    - **Weakly Connected**: A directed graph is weakly connected if the underlying undirected graph is connected.
- **Degree**: The number of edges incident to a vertex.
    - **In-Degree**: The number of edges entering a vertex.
    - **Out-Degree**: The number of edges leaving a vertex.
- **Directed Graph**: A graph where edges have a direction.

## Common Graph Problems

-   s-t Path. Is there a path between vertices s and t?
-   Connectivity. Is the graph connected, i.e. is there a path between all vertices?
-   Biconnectivity. Is there a vertex whose removal disconnects the graph?
-   Shortest s-t Path. What is the shortest path between vertices s and t?
-   Cycle Detection. Does the graph contain any cycles?
-   Euler Tour. Is there a cycle that uses every edge exactly once?
-   Hamilton Tour. Is there a cycle that uses every vertex exactly once?
-   Planarity. Can you draw the graph on paper with no crossing edges?
-   Isomorphism. Are two graphs isomorphic (the same graph in disguise)?

## Matrix Representation

An adjacency matrix is a $V \times V$ matrix where $A_{ij} = 1$ if there is an edge between vertices $i$ and $j$, and $0$ otherwise. For graphs with weights, $A_{ij}$ is the weight of the edge.

> [!example] 
>
> |   | A | B | C | D | E |
> |---|---|---|---|---|---|
> | A | 0 | 1 | 1 | 0 | 0 |
> | B | 1 | 0 | 1 | 1 | 0 |
> | C | 1 | 1 | 0 | 1 | 1 |
> | D | 0 | 1 | 1 | 0 | 1 |
> | E | 0 | 0 | 1 | 1 | 0 |
>
> The above matrix represents the following graph:
>
> ```mermaid
> graph TD;
>     A --- B;
>     A --- C;
>     B --- C;
>     B --- D;
>     C --- D;
>     C --- E;
>     D --- E;
> ```
>
## Graph Types

### Spanning Trees

A spanning tree of a graph is a subgraph that is a tree and connects all vertices in the graph. It has $V-1$ edges and is acyclic.

By traversing the spanning tree with a depth-first search (DFS) or breadth-first search (BFS), we can visit all vertices in the graph and produce a spanning tree.

### Minimum Spanning Trees

A minimum spanning tree (MST) of a graph is a spanning tree with the smallest possible sum of edge weights.

#### Prim's Algorithm

Prim's algorithm is a greedy algorithm that constructs a MST by selecting the edge with the smallest weight that connects a vertex in the tree to a vertex outside the tree.

> [!note] 
> Prim's algorithm can also be referred to as Jarník's algorithm.
>
> [!example] Implementation
> Prim's algorithm can be implemented with a priority queue (min-heap) to efficiently select the edge with the smallest weight. We start with a single vertex, add it to the MST, then take the vertex's edges and add it to the priority queue. We take the smallest edge from the priority queue and add it to the MST. We repeat this process until all vertices are included in the MST.
>
#### Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that constructs a MST by selecting the edge with the smallest weight from the set of all edges.

> [!example] Implementation
> Kruskals algorithm can be implemented with a weighted quick-union data structure to efficiently check if adding an edge would create a cycle. We start with all vertices as separate components, then sort the edges by weight. We iterate through the edges and add them to the MST if they connect two different components. We repeat this process until all vertices are included in the MST.
>
## Traversing Graphs

### Depth-First Search (DFS)

Depth-first search is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

Implementation of DFS typically involves the use of a stack or recursion.

To prevent visiting the same vertex multiple times, we need to keep track of visited vertices, which can be accomplished using a boolean array or a set.

### Breadth-First Search (BFS)

Breadth-first search is a graph traversal algorithm that explores all vertices at the current depth before moving on to the next depth.

Implementation of BFS typically involves the use of a queue.

Similar to [DFS](#depth-first-search-dfs), we need to keep track of visited vertices to prevent visiting the same vertex multiple times.

## Shortest Path Algorithms

The shortest path is defined as the path of least resistance between two vertices in a graph.

### Dijkstra's Algorithm

Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

> [!example] Implementation
> Dijkstra's algorithm can be implemented with a priority queue (min-heap) to efficiently select the vertex with the smallest distance. We start with the source vertex, set its distance to 0, and all other vertices to infinity. We then take the vertex with the smallest distance from the priority queue and update its neighbors' distances. We repeat this process until all vertices have been visited.

## Connections

- [[sp25-cs400/topics/index|Topic index]]

Obvious technical and formatting errors repaired.