## I. Graph#

## 1. What is a Graph#

Represents a "many-to-many" relationship, consisting of:

- A set of vertices: usually represented by V (Vertex) for the set of vertices
- A set of edges: usually represented by E (Edge) for the set of edges
- An undirected edge is a pair of vertices: (v, w) ∈ E, where v, w ∈ V
- A directed edge <v,w> represents an edge pointing from v to w (single line)
- Does not consider multiple edges and self-loops

### Abstract Data Type Definition#

Type Name: Graph (Graph)

Data Object Set: G(V,E) consists of a non-empty finite set of vertices V and a finite set of edges E.

Operation Set: For any graph G ∈ Graph, and v ∈ V, e ∈ E

- Graph Create(): creates and returns an empty graph;
- Graph InsertVertex(Graph G, Vertex v): inserts vertex v into graph G
- Graph InsertEdge(Graph G, Edge e): inserts edge e into graph G
- void DFS(Graph G, Vertex v): performs depth-first traversal of graph G starting from vertex v;
- void BFS(Graph G, Vertex v): performs breadth-first traversal of graph G starting from vertex v;
- void ShortestPath(Graph G, Vertex v, int Dist[]): calculates the shortest distance from vertex v to any other vertex in graph G;
- void MST(Graph G): calculates the minimum spanning tree of graph G

Common Terms:

Undirected graph, directed graph, network, etc.

### How to Represent a Graph in a Program#

#### Adjacency Matrix#

Benefits of Adjacency Matrix

- Intuitive, simple, easy to understand
- Convenient to check if there is an edge between any pair of vertices
- Convenient to find all "
**adjacent points**" (vertices directly connected by edges) of any vertex - Convenient to calculate the "
**degree**" of any vertex (the number of edges emanating from that point is "out-degree", the number of edges pointing to that point is "in-degree")**Undirected graph**: the number of non-zero elements in the corresponding row (or column)**Directed graph**: the number of**non-zero elements in the row**is the**out-degree**, the number of**non-zero elements in the column**is the**in-degree**

### Adjacency List#

Pointer array + linked list, very efficient when points are sparse

Benefits of Adjacency List:

- Convenient to find all "adjacent points" (vertices directly connected by edges) of any vertex
- Saves space for sparse graphs
- Requires N head pointers + 2E nodes (each node has at least 2 fields)

- Convenient to calculate the "degree" of any vertex in an undirected graph, but can only calculate the out-degree for directed graphs.

## 2. Graph Traversal#

### DFS Depth First Search#

Depth First Search (DFS), explores each possible branch path until it can no longer go deeper, and each node can only be visited once.

Pseudocode description:

```
void DFS(Vertex V) {
visited[V] = true;
for each adjacent point W of v
if (!visited[W])
DFS(W);
}
```

### BFS Breadth First Search#

Breadth First Search (BFS), implemented using a queue (first in, first out)

Pseudocode description:

```
void BFS(Vertex V) {
visited[V] = true;
Enqueue(V, Q); // Put this vertex into the queue
while(!IsEmpty(Q)) { // End search when the queue is empty
V = Dequeue(Q); // V is the front element
for each adjacent point W of V {
if (!visited[W]) {
visited[W] = true; // Mark this point as visited
Enqueue(W, Q); // Push this point into the queue
}
}
}
}
```

### What to do if the graph is disconnected?#

**Path**: A path from V to W is a set of vertices {V, V1, V2, ..., Vn, W}, where there is an edge in the graph between any pair of adjacent vertices. The**length of the path**is the number of edges in the path (if weighted, it is the sum of all edge weights). If all vertices between V and W are different, it is called a**simple path****Connected**: If there exists a (undirected)**path**from V to W, then V and W are said to be connected**Cycle**: A path where the starting point equals the endpoint**Connected Graph**: A graph where any two vertices are connected**Connected Component**: The**maximal connected subgraph**of an undirected graph- Maximal vertex count: adding one more vertex would make it disconnected
- Maximal edge count: contains all edges connecting all vertices in the subgraph

**Strongly Connected**: If there exists a bidirectional path between vertices V and W in a directed graph, then V and W are said to be strongly connected**Strongly Connected Graph**: A directed graph where any two vertices are strongly connected**Strongly Connected Component**: The maximal strongly connected subgraph of a directed graph

**Each time DFS is called, it actually traverses the connected component containing V. The same goes for BFS.**

```
void ListComponents ( Graph G ) { // Traverse connected components
for (each V in G)
if (!visited[V]) {
DFS(V);
}
}
```

## 3. How to Construct a Graph#

### (1) Establishing a Graph Represented by an Adjacency Matrix#

#### Definition#

```
const int MaxVertexNum = 100;
typedef int DataType;
typedef bool WeightType;
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // Number of vertices
int Ne; // Number of edges
WeightType G[MaxVertexNum][MaxVertexNum];
DataType Data[MaxVertexNum]; // Store vertex data
};
typedef PtrToGNode MGraph; // Graph type stored by adjacency matrix
```

#### Initialization#

Initialize a graph with VertexNum vertices but no edges

```
typedef int Vertex;
MGraph CreateGraph(int VertexNum) {
Vertex V, W;
MGraph Graph;
Graph = (MGraph) malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
// Vertex numbering starts from 0, up to Graph->Nv-1
for (V = 0; V < Graph->Nv; V++) {
for(W = 0; W < Graph->Nv; W++) {
Graph->G[V][W] = 0; // In directed graphs, 0 can be changed to INF, etc.
}
}
return Graph;
}
```

#### Inserting Edges into the Graph#

Definition of an edge

```
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // Directed edge <V1,V2>
WeightType Weight; // Weight
};
typedef PtrToENode Edge;
```

Insertion operation

```
void InsertEdge(MGraph Graph, Edge E) {
// Insert edge <V1,V2>
Graph->G[E->V1][E->V2] = E->Weight;
// If it is an undirected graph, also insert edge <V2,V1>
Graph->G[E->V2][E->V1] = E->Weight;
}
```

#### Complete Establishment of an MGraph#

Input format

Nv Ne

V1 V2 Weight

……

```
MGraph BuildGraph() {
MGraph Graph;
Edge E;
Vertex V;
int Nv;
cin >> Nv;
Graph = CreateGraph(Nv); // Establish a graph with Nv vertices
cin >> Graph->Ne; // Number of edges Ne
if(Graph->Ne != 0) {
E = (Edge)malloc(sizeof(struct ENode));
for (int i = 0; i < Graph->Ne; i++) {
cin >> E->V1 >> E->V2 >> E->Weight;
InsertEdge(Graph, E);
}
}
// If vertices have data, read in the data
for(V = 0; V < Graph->Nv; V++) {
cin >> Graph->Data[V];
}
return Graph;
}
```

### (2) Establishing a Graph Represented by an Adjacency List#

Can be modified based on the adjacency matrix

#### Definition#

```
const int MaxVertexNum = 100;
typedef int DataType;
typedef int Vertex;
typedef bool WeightType;
// Definition of adjacency list
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
Vertex AdjV; // Index of adjacent point
WeightType Weight; // Edge weight
PtrToAdjVNode Next;
};
typedef struct VNode {
PtrToAdjVNode FirstEdge;
DataType Data; // Store vertex data
} AdjList;
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // Number of vertices
int Ne; // Number of edges
AdjList G; // Adjacency list
};
typedef PtrToGNode LGraph; // Graph type stored by adjacency list
```

#### LGraph Initialization#

```
LGraph CreateGraph(int VertexNum) {
Vertex V, W;
LGraph Graph;
Graph = (LGraph) malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
// Vertex numbering starts from 0, up to Graph->Nv-1
for (V = 0; V < Graph->Nv; V++) {
Graph->G[V].FirstEdge = NULL;
}
return Graph;
}
```

#### Inserting Edges into LGraph#

```
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // Directed edge <V1,V2>
WeightType Weight; // Weight
};
typedef PtrToENode Edge;
void InsertEdge(LGraph Graph, Edge E) {
PtrToAdjVNode NewNode;
// Insert edge <V1,V2>
// Create a new adjacent point for V2
NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
NewNode->AdjV = E->V2;
NewNode->Weight = E->Weight;
// Insert V2 adjacent point at the head of V1's list
NewNode->Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
// If it is an undirected graph, also insert edge <V2,V1>
// Create a new adjacent point for V1
NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
NewNode->AdjV = E->V1;
NewNode->Weight = E->Weight;
// Insert V1 adjacent point at the head of V2's list
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}
```

#### Complete Establishment of an LGraph#

Just replace MGraph with LGraph and make slight changes to store Data

```
LGraph BuildGraph() {
LGraph Graph;
Edge E;
Vertex V;
int Nv;
cin >> Nv;
Graph = CreateGraph(Nv); // Establish a graph with Nv vertices
cin >> Graph->Ne; // Number of edges Ne
if(Graph->Ne != 0) {
E = (Edge)malloc(sizeof(struct ENode));
for (int i = 0; i < Graph->Ne; i++) {
cin >> E->V1 >> E->V2 >> E->Weight;
InsertEdge(Graph, E);
}
}
// If vertices have data, read in the data
for(V = 0; V < Graph->Nv; V++) {
cin >> Graph->G[V].Data;
}
return Graph;
}
```

## II. Shortest Path Problem#

## 1. Concept Overview#

- In a network, find the path with the minimum sum of edge weights among all paths between two different vertices
- This path is called the
**shortest path**(Shortest Path) between the two points - The first vertex is called the
**source**(Source) - The last vertex is called the
**destination**(Destination)

- This path is called the

## 2. Problem Classification#

**Single-source**shortest path problem: From a fixed source point, find the shortest path to all other vertices- (Directed) unweighted graph
- (Directed) weighted graph

**Multi-source**shortest path problem: Find the shortest path between any two vertices

## 2. Single-source Shortest Path Algorithm for Unweighted Graphs#

Find the shortest path to each vertex in increasing order, similar to the idea of BFS!

First, define an array dist, **dist[W] stores the shortest distance from S to W**, where S is the starting point, dist[S]=0, and dist needs to be initialized to -1 (or infinity) for later determination of whether it has been visited.

Next, define an array path, **path[W] stores a vertex passed through from S to W.**

Both dist and path arrays need to be initialized to -1, then set the dist[S] of the starting point to 0, and enqueue to start visiting.

Pseudocode:

```
void Unweighted(Vertex S) {
Enqueue(S, Q);
while(!IsEmpty(Q)) {
V = Dequeue(Q);
for each adjacent point W of V
if(dist[W] == -1) {
dist[W] = dist[V] + 1;
path[W] = V;
Enqueue(W, Q);
}
}
}
```

## 3. Single-source Shortest Path Algorithm for Weighted Graphs#

### Dijkstra's Algorithm!#

- Let s={source s + vertices v~i~ that have already determined the shortest path}
- For any unrecorded vertex v, define dist[v] as the shortest path length from s to v, but this path
**only passes through vertices in S**, i.e., the minimum length of the path {s→(v~i~∈S)→v} - If the path is generated in
**increasing**order, then- The true shortest path must only pass through vertices in S (can be proven by contradiction)
- Each time, select one vertex with the minimum dist from the unrecorded vertices (greedy)
- Adding a vertex v into S may affect the dist value of another w! (So check all adjacent points w of v!)
- dist[w] = min{ dist[w], dist[v] + <weight of edge (v,w)>}

Initialize dist: the dist of all adjacent points W of S can be initialized to the weight from s to w, while others are defined as positive infinity.

- dist[w] = min{ dist[w], dist[v] + <weight of edge (v,w)>}

Pseudocode description:

```
void Dijkstra(Vertex s) {
while (1){
V = the vertex with the minimum dist among unrecorded vertices;
if (no such V exists)
break;
collected[V] = true;
for each adjacent point W of V
if(collected[W] == false)
if(dist[V] + E<v,w> < dist[W]) {
dist[W] = dist[V] + E<v,w>;
path[W] = V;
}
}
} // Cannot solve cases with negative edges
```

In the pseudocode, dist[W]=dist[V]+E~<V,W>~; is not a simple assignment, but if a shorter distance is found, it needs to be updated to the shorter distance.

#### Core Code of Dijkstra#

```
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1005;
const int inf = 0x3f3f3f;
int T,N,x,y,z;
int edge[maxn][maxn];
int dist[maxn];
bool vis[maxn];
void init() {
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= N; ++j) {
edge[i][j] = inf;
}
edge[i][i] = 0;
}
}
void Dijstra(int u) {
for(int i = 1; i <= N; ++i) {
vis[i] = false;
dist[i] = edge[u][i];
}
vis[u] = true;
for(int i = 1; i <= N; ++i) {
int t, mindis = inf;
for(int j = 1; j <= N; ++j) {
if(!vis[j] && dist[j] < mindis) {
mindis = dist[j];
t = j;
}
}
vis[t] = true;
for(int j = 1; j <= N; ++j)
if(!vis[j] && dist[j] > edge[t][j] + dist[t])
dist[j] = edge[t][j] + dist[t];
}
}
```

## III. Minimum Spanning Tree#

## 1. What is a Minimum Spanning Tree (MST)#

- It is a
**tree**- No cycles
- A tree with |V| vertices must have |V|-1 edges

- It is a
**spanning**tree- Contains all vertices
- |V|-1 edges are all in the graph
- Adding any edge to the spanning tree will definitely form a cycle

- The sum of the edge weights is
**minimum**

The minimum spanning tree is equivalent to the graph being connected.

#### 2. Solving the Minimum Spanning Tree Problem#

Usually involves a greedy algorithm:

- "Greedy": Always choose the best at each step
- "Best": The edge with the smallest weight
- Constraints needed:
- Only use edges that exist in the graph
- Must use exactly |V|-1 edges
- Cannot have cycles

This is discussed in another blog.

Graph Theory - Solving the Minimum Spanning Tree Problem (Kruskal's Algorithm & Prim's Algorithm)