1. Description
A graph is a mathematical structure used to model pairwise relations between objects. It is defined as an ordered pair: G = (V, E) where V is a set of vertices and E is a set of Edges.
There are different types of graph, based on how you classify them.
1.1. Based on Edge Direction
- Undirected Graph
- Directed Graph
1.2. Based on Edge weights
- Unweighted Graph
- Weighted Graph
1.3. Based on Conectivity
- Connected Graph : Every vertex is reachable from any other (for undirected graphs).
- Strongly Connected Graph: In a directed graph, every vertex is reachable from any other vertex via directed paths.
- Weakly Connected Graph: In a directed graph, connectivity is possible if directions are ignored.
1.4. Based on Cycles:
- Acyclic Graph: No cycles (rg. like tree)
- Cyclic Graph
- Directed Acyclic Graph (DAG) : A directed graph with no cycles. (used in scheduling: Topological Sort)
1.5. Special Graphs:
- Tree : A connected acyclic undirected graph
- Forest: A disjointed set of trees
- Complete Graph: Every vertex is connected to every other vertex.
- Bipartite Graph: Vertices can be divided into two disjoint sets with edges only between sets.
2. how to present a graph?
Assume the node in the graph with an integer and also have weight, we can represent the graph as
2.1. Ajacent list
unordered_map<int, vector<pair<int, int>>> graph; graph[node1] gives the list of node {node2, weight}, in whcih weight represent the distance between node1 -> node2 can also be represented as: vector<vector<pair<int, int>>> graph;
2.2. Ajacent matrix
vector<vector<int>> graph; graph[node1][node2] gives the distance between node1 -> node2
2.3. Special case: 2D-array graph
Sometimes, we are given a 2D array and need to traverse the graph from one node to another. How can we represent the graph.
// graph is m * n array vector<vector<int>> graph(m, vector<int>(n)); // each node at coordinate (i, j) can be represented with id i * n + j // to traverse ajacently, you can use the following array to specify the up, down, left, right directions vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
3. Neighbour
In non directed theory, the neighbors (or adjacent vertices) of a node n are all the vertices that are directly connected to n by an edge.
If the graph is directed, there are 2 types of neighbuor, outgoing neighbours