The following two are the most commonly used representations of a graph:
-
Adjacency Matrix
-
Adjacency List
-
Incidence Matrix
-
Incidence List
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Adjacency matrix for undirected graph is always symmetric.
- Graph node represented with adj[n][n]
- Edge = adj[i][j] = 1 | Edge / Path from i to j.
- Weigthted Graph = adj[i][j] = w (n)
Graph = [ [0, 1, 0, 0, 1] # Node 1 [1, 0, 1, 1, 1] # Node 2 [0, 1, 0, 1, 0] # Node 3 [0, 1, 1, 0, 1] # Node 4 [1, 1, 0, 1, 0] # Node 5
1 2 3 4 5
]
adjacency list is a collection of unordered lists used to represent a finite graph.
- Undirected graph
The edges do not point in any direction (ie. the edges are bidirectional), hence if there is a path between V a and V b you can go (a, b) or reverse (b, a).
- Connected graph
Paths are one direction, V a and V b, if only path (a, b) is set then you can't go (b, a).
- Spanning tree
A spanning tree is a sub-graph of an undirected or connected graph, which includes all the vertices of the graph with a minimum possible number of edges.
If a vertex is missed, then it is not a spanning tree.
The edges may or may not have weights assigned to them.
The total number of spanning trees with n vertices that can be created from a complete graph is equal to n(n-2).
If we have n = 4, the maximum number of possible spanning trees is equal to 44-2 = 16. Thus, 16 spanning trees can be formed from a complete graph with 4 vertices.
- Minimum Spanning Tree
A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as minimum as possible.
- Prim's Algorithm
- Kruskal's Algorithm
- Dijkstra's Algorithm
-
Set or ordered Pair (u, v) != (v, u)
-
directed graph | di-graph
-
weight | value | cost | Distance
-
Sparse Graph (containing less n of Edges)
-
Undirected Graph WIKI
-
Directed graphs
The A* algorithm is a generalization of Dijkstra's algorithm that cuts down on the size of the subgraph that must be explored,
Unlike Dijkstra's algorithm, the Bellman–Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s.
-
heapq — Heap queue algorithm --Python Docs--
-
Selection algorithm WIKI
-
Cache replacement policiesWIKI
-
Round-robin schedulingWIKI
-
Tail Recursion StackOverflow
-
Depth-first search Breadth-first search Iterative deepening depth-first search Monte Carlo tree search
- Bellman–Ford algorithm
- A* search
- Prim's algorithm
- Breadth-first search
- Asymptotic computational complexity