A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them
So edges can be categorized as :
- Directed, weighted edges
- Directed, unweighted edges
- Undirected, weighted edges
- Undirected, unweighted edges
Uses of graphs
Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.
 |
| Delhi Metro Rail Map |
Each station is a vertex, the distance in between is a weighted edge.
 |
| A Maze |
Each corner is a vertex, Line between two corners is and edge.
Each team is a vertex, match between the teams is an edge.
Kind of graphs
There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:
 |
| Undirected Graph |
Characteristics:
- Order of vertices doesn't matter
- 1-2 is same as 2-1
 |
| Directed Graph |
Characteristics:
- Order of vertices does matter
- 1-2 is not same as 2-1
 |
| Vertex Labeled Graph |
Characteristics:
- Each vertex contains additional information. e.g {2,orange}, {4,green}
 |
| Cyclic Graph |
Characteristics:
- Graph contains at least one cycle.
 |
| Edge Labeled Graph |
Characteristics:
- Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}
 |
| Weighted Graph |
Characteristics:
- Each edge has some weight associated with it.
 |
| Direct Acyclic Graph(DAG) |
Characteristics:
- Graph has no cycles.
 |
| Disconnected Graph |
Characteristics:
- Vertices are disconnected
 |
| Mixed Graph |
Characteristics:
- Some edges may be directed and some may be undirected
 |
| Multigraph |
Characteristics:
- Multiple edges (and sometimes loops) are allowed
Characteristics:- Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.
Representation of graphs:
 |
| Fig. 1: An undirected graph |
 |
| Fig 2: A directed graph |
In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.
Adjacency Matrix :
For N vertices an adjacency matrix is an NxN array A such that
A[i][j] = 1 if there is an edge E(i,j)
= 0 otherwise
For an undirected graph, A[i][j] = A[j][i]
For weighted graphs,
A[i][j] = weight of the edge, if there is an edge E(i,j)
= a constant representing no edge (e.g a very large or very small value)
For Fig 1, the adjacency matrix would be
The adjacency matrix for directed graph in Fig 2 would be:
Adjacency List :
Adjacency matrix representation consume a lot of memory (O[N2]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.
Every vertex has a linked list of the vertices it is connected with.
Adjacency list for Fig 1 would be:
Adjacency list for Fig 2 would be:
No comments