Types of Graphs
Learn the key differences between undirected and directed graphs, including how edges are formed and counted. Understand when to use each type as you build foundational knowledge in graph data structures for coding interviews.
We'll cover the following...
Types of Graphs
There are two common types of graphs:
- Undirected
- Directed
Undirected Graph
In an undirected graph, all the edges are undirected, i.e., there is no notion of direction to the edges. For a pair (2, 3), there exists an edge between vertex 2 and 3 without any specific direction. You can go from vertex 2 to 3 or from 3 to 2.
Let’s calculate the maximum possible edges for an undirected graph. We are denoting an edge between vertex a and b as (a, b). So, the maximum possible edges of a graph with n vertices will be all possible pairs of vertices of that graph, assuming that there are no self-loops.
If a graph has n vertices, then there are C(n,2) possible pairs of vertices, according to Combinatorics. Solving C(n,2) by binomial coefficients gives us ...