Types of Graphs with Examples

A graph is a non-linear data structure that consists of vertices and edges. The vertices contain the information or data, and the edges work as a link between pair of vertices.

Graphs can be of multiple types, depending on the position of the nodes and edges. Here’re some important types of Graphs:

Directed Graph

The edges of the Directed Graph contain arrows that mean the direction. The arrow determines where the edge is pointed to or ends.

Here’s an example of the Directed Graph.

• We can go from Node A to D.
• However, we can’t go from node D to node A as the edge points from A to D.
• As the Graph does not have weights, traveling from vertex A to D will cost the same as traveling from D to F.

Undirected Graph

Undirected Graph contains edges without pointers. It means we can travel vice versa between two vertices.

Here’s a simple example of the undirected Graph.

In the above Graph,

• We can move from A to B
• We can also move from B to A
• Edges contain no directions.

It’s an example of an undirected graph having a finite number of vertices and edges with no weights.

Weighted Graph

Graph that contains weights or costs on the edges is called a weighted Graph. The numerical value generally represents the moving cost from one vertex to another vertex. Both Directed and Undirected Graph can have weights on their edges.

Here’s an example of a weighted graph (Directed).

• A to B, there’s an edge, and the weight is 5, which means moving from A to B will cost us 5.
• A point to B, but in this Graph, B has no direct edge over A. So, we can’t travel from B to A.
• However, If we want to move from A to F, there are multiple paths. The paths are ADF, ABF. ADF will cost (10+11) or 21.
• Here, the path ABF will cost (5+15) or 20. Here we’re adding the weight of each edge in the path.

Here’s an example of an Undirected Graph with weights:

Here, the edge has weight but no direction. So, it means traveling from vertex A to D will cost 10 and vice versa.

Bi-Directional Graph

Bi-directional and undirected graphs have a common property. That is

• Generally, the undirected Graph can have one edge between two vertexes.

For example:

• Here, moving from A to D or D to A will cost 10.
• In a Bi-Directional Graph, we can have two edges between two vertices.

Here’s an example:

Traveling from A to D will cost us 17, but traveling from D to A will cost us 12. So, we can’t assign two different weights if it is an undirected graph.

Infinite Graph

The Graph will contain an infinite number of edges and nodes. If a graph is Infinite and it’s also a connected graph, then it will contain an infinite number of edges as well. Here, the extended edges mean that more edges might be connected to these nodes via edges.

Here’s an example of the infinite Graph:

Null Graph

Null Graph contains only nodes or vertices but with no edges. If given a Graph G = (V, E), where V is vertices and E is edges, it will be null if the number of edges E is zero.

Here’s an example of a Null Graph:

Trivial Graph

A graph data structure is considered trivial if only one vertex or node is present with no edges.

Here’s an example of a Trivial Graph:

Multi Graph

A graph is called a multigraph when multiple edges are present between two vertices, or the vertex has a loop. The term “Loop” in Graph Data Structure means an edge pointing to the same node or vertex. Multigraph can be directed or undirected.

Here’s an example of a Multi Graph:

There’re two edges from B to A. Moreover, vertex E has a self-loop. The above Graph is a directed graph with no weights on edges.

Complete Graph

A graph is complete if each vertex has directed or undirected edges with all other vertices.

Suppose there’s a total V number of vertices and each vertex has exactly V-1 edges. Then, this Graph will be called a Complete Graph. In this type of Graph, each vertex is connected to all other vertices via edges.

Here’s an example of a Complete Graph with five vertices:

You can see in the image the total number of nodes is five, and all the nodes have exactly four edges.

Connected Graph

A Graph is called a Connected graph if we start from a node or vertex and travel all the nodes from the starting node. For this, there should be at least one edge between each pair of nodes or vertices.

Here’s an example of a Connected Graph:

Here’s some explanation of the above Graph:

• Assuming there’s no edge between C and F, we can’t travel from A to G. However, the edge C to F enables us to travel to any node from a given node.
• A complete Graph is a Connected Graph because we can move from a node to any other node in the given Graph.

Cyclic Graph

A graph is said to be cyclic if there are one or more cycles present in the Graph.

Here’s an example of a Cyclic Graph:

Here, vertex A, B, and C form a cycle.

A graph can have multiple cycles inside it.

Directed Acyclic Graph (DAG)

A Graph is Called Directed Acyclic Graph or DAG if there’re no cycles inside a graph. DAG is important while doing the Topological Sort or finding the execution order. DAG is also important for creating scheduling systems or scanning dependency of resources etc. However, the above Graph above doesn’t contain any cycle inside.

Here’s a simple example of a Directed Acyclic Graph (DAG):

Cycle Graph

Cycle Graph is not the same as the cyclic Graph. In Cycle Graph, each node will have exactly two edges connected, meaning each node will have exactly two degrees.

Here’s an example of a Cycle Graph:

Bipartite Graph

These kinds of Graphs are special kinds of Graph where vertices are assigned to two sets.

Bipartite Graph must follow the rule:

• Two sets of vertices should be distinct, which means all the vertices must be divided into two groups or sets.
• Same set Vertices should not form any edges.

Euler Graph

A Graph Data Structure is said to be an Euler Graph if all the vertices have an even-numbered degree. The term degree of vertices means the number of edges pointing to or pointing out from a particular vertex.

Here’s an example of a Euler graph:

All the vertices have even degrees. Vertex A, D, E, and H have two degrees. Here, node C has four degrees, which is even.

Hamilton Graph

Hamilton Graph is a Connect Graph, where you can visit all the vertices from a given vertex without revisiting the same node or using the same edge. This kind of Connected Graph is known as the “Hamilton Graph.” The path you visit to verify if the given Graph is Hamilton Graph or not is known as Hamiltonian Path.

Here’s a simple example of a Hamilton graph:

In this image, we can visit all the vertices from any node in the above Graph. One of the paths can be A-D-C-H-B-E. It’s also possible to find a Hamilton Cycle. Hamilton Cycle starts and ends at the same vertex. So, the Hamilton Cycle will be A-D-C-H-B-E-A.