Introduction To Graphs

Graphs are one of the fundamental data structures in computer science. They play a vital role in solving complex problems and are used in day-to-day problem-solving techniques. In this article, we will go into detail about what graphs are, how to create them, what types of graphs exist, and how to search within them.?

What is a?Graph?

In data structures, graphs (G) are non-linear data structures with a finite number of vertices or nodes (V) connected by edges (E). In G=(V, E), V is a finite set of data, where E is the relationship between V.

As we can see in the above image a graph with 5 nodes which also called vertices, and with 6 edges which are connected with vertices. This graph G is a set of vertices V = {1, 2, 3, 4, 5} with edges E = {(1,2), (1,3), (2,4), (3,4), (3,5), (4,5)}.

Types of Graphs

Finite Graph

A graph G=(V, E) is a finite graph when it has a finite number of vertices and edges. In other words, the number of vertices and edges are in limited numbers.

Infinite Graph

A graph G=(V, E) is an infinite graph when it has an unlimited number of edges and vertices. An infinite graph looks like hereinafter.

Trivial Graph

A trivial graph G=(V, E) is a graph where V is one and E is zero. In other words, this graph contains a single vertex and no edge. This graph will look like hereinafter.

Simple Graph

A simple graph G=(V, E) is a graph where each pair of vertices has only one edge. The edge should not start and end on the same vertex. As a result, each pair of vertices will have only one edge, there will be no multi-edges of self-loop. A simple graph will look like hereinafter,

Multi Graph

A multi-graph G=(V, E) is a graph in which vertices can have multiple edges. A multi-graph does not have any self-loop. A self-loop is when a vertex has self edge (edge to itself). The multi graph looks like hereinafter,

Null Graph

A null graph G=(V, E) is a graph which has only vertices and no edges. It is a version of the trivial graph but with multiple vertices.

Complete Graph

A complete graph G=(V, E ) is also a simple graph, which is called completed because all vertices V are connected with each other through edges. Let a graph have n number of vertices then in a complete graph degree of each vertex must be n-1.

Pseudo Graph

A pseudo graph G=(V, E) is a graph which has a self-loop beside other edges. As mentioned earlier a self-loop is an edge which starts and ends on the same vertex. The pseudo graph looks like hereinafter,

Directed Graph

A directed graph (D Graph) G=(V, E) is an ordered pairs graph where V are vertices and E are edges between vertices also representing the direction of edge from one vertex to another. Here is a representation of the directed graph,

Undirected Graph

An undirected graph G=(V, E) is an unordered pairs graph where V are vertices and E are edges between vertices without direction. A self-loop edge like the pseudo graph is not allowed in an undirected graph.

Regular Graph

A regular graph G=(V, E) is a graph where all vertices V have the same degree, which makes the whole graph a regular graph. In a graph, the degree of a vertex is several edges moving in or out of that vertex. Let's say a vertex Vi is connected with Vm & Vn using two edges Em & En which make Vi degree 2.

Weighted Graph

A weighted graph G=(V, E) is labelled or weighted which shows some values on each edge to show the weight or cost of travelling from one vertex to another vertex. Here is the representation of a weighted graph.

Connected Graph

A connected graph G=(V, E) is a graph in which any two vertexes are connected by a path (edge). Here is a representation of the connected graph,

In the above diagram, we can see two vertices A & D are connected as A->B->D which is enough to prove that the graph is connected, other vertices like C, B and D are also connected.

Disconnected Graph

A disconnected graph G=(V, E) is a graph where at least one pair of vertices is not connected by a path (edge). Here is a representation of the disconnected graph,

Here we can there is no path available between a few vertices like B->F, C->F, D->B etc that’s why it's a disconnected graph. A disconnected graph still can have a connected graph (as a subgraph) for example A->B->C.

Cyclic Graph

A graph G=(V, E) is considered as cyclic if it has at least one cycle. A cycle means a path which starts from a vertex Vi and ends at the same vertex. Let’s see an example here,

There is a cycle in this graph which is 1->2->4->3->1 and some others as well.

Acyclic Graph

A graph G=(V, E) is considered an acyclic graph if that graph does not have any cycles in it. An example of the acyclic graph is hereinafter,

DAG (Directed Acyclic Graph)

DAG graph G=(V, E) is a directed graph which has no cycles in it. Likewise, DAG can have undirected acyclic, directed cyclic graph, undirected cyclic graph etc, which are pretty much the same we discussed above.

Subgraph

A subgraph Gi = (Vn, Em) is a graph which is a subset of another graph G = (V, E). A subgraph is shown in the diagram below,

Graph 2 (A, B, F) is a subgraph of 1st one.

Here we finished discussing many types of graphs and understanding the differences between them using diagrams. Now we see what techniques we use to search for something or traverse a graph.

Traversal In Graph

Please note that hereinafter explanation is only related to special type of graph which are called binary trees. We will study more more details of representation of graphs and traversal in future articles.

The process of reading or updating a vertex inside a graph is called the traversal of a graph.

The order in which we wanted to visit vertexes defined the technique of traversal. Graphs have two types of traversals,

1. Breadth-First Traversal
2. Depth-First Traversal

Breadth First Traversal

BFS or breath first search or traversal is a technique in which we visit a vertex and all of its connected vertex before moving forward. In BFS we start with the root node (vertex) visit all of its child nodes (connected vertices) and then go further to other vertices in a first-in-first-out manner.

We use a queue to achieve FIFO behaviour and save the first vertex or root node and then traverse all of its connected vertices or child nodes and push it to our queue. Once we finish visiting all nodes of the root then we will pop out the first child of the root visit all of its child nodes and push it to the queue again.

Let's understand it with a diagram,

Depth First Traversal

DFS or depth-first traversal is a graph or tree traversal where we begin from the root node and traverse to all levels till the end then backtrack nodes to search or update a vertex. We use stack or recursion to perform a depth-first search. There are three types of depth-first traversal, which are in-order, pre-order and post-order traversal.

In pre-order we first search root and then move left and right. This traversal represents Root -> Left Children -> Right Children.

The Pseudo code for pre-order traversal is hereinafter,

function preorder(TreeNode root) {
  if(root == null) return;
    print(root);
    
    preorder(root.left);
    preorder(root.right);

 }        

In post-order we first traverse to left most and right and then the parent root (node). This traversal represents Left Children -> Right Children -> Root.

The Pseudo code for post-order traversal is hereinafter,

function preorder(TreeNode root) {
  if(root == null) return;
    preorder(root.left);
    preorder(root.right);
    
    print(root);

 }        

Lastly, in-order traversal is when we traverse to the leftmost and then print the actual parent node and then move to the right side before backtracking. This traverse represents Left Children -> Root-> Right Children.

The Pseudo code for in-order traversal is hereinafter,

function preorder(TreeNode root) {
  if(root == null) return;
    
    preorder(root.left);
    
    print(root);
    
    preorder(root.right);
  
  }        

Conclusion

In this article, we studied what graphs are, what they are made of, the many types of graphs, and the differences between them. We also looked into the most popular types of graphs, like directed graphs, undirected graphs, weighted graphs, and cyclic and acyclic graphs. We also understand traversal mechanics in graphs and see what is meant by “depth-first” and “breath-first” search. In the next article, we will see how to create graphs using Java language and will go through some of the popular algorithms.