Types of Graphs
This lesson showcases the two main categories of graphs.
We'll cover the following
Types of Graphs
There are two common types of graphs:
- Undirected
- Directed
Undirected Graph
In an undirected graph, the edges are by default, bi-directional. 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 ,vice versa, 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 . Hence, there are maximum possible edges in an undirected graph.
You can see an example of an undirected graph below:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.