Graph: Is it a plane? Or a bird?

We all are familiar with a topic of Data Structure named Graph. Also, we often wondered, is it a plane? Or a bird? In the following paragraphs, I will discuss about this as much as I can.

So, what is Graph? According to the book, Graph is a data structure that consists of a set of nodes and a set of connections that relate the nodes to one another. The main question is HOW? To understand that, first we need to know what is Linked List.

I bet you can hear the Photo^

Now, Graph is a Linked List with a specific index numbers. We will talk about it in details later. As a matter of fact, Graphs has Vertices (Vertex in singular form) and Edges. In the Picture you can see, which is which.

Vertex and Edge

Vertex is a node in a Graph and Edge is a pair of Vertices representing a connection between two nodes in a Graph. Also, there are two types of Graphs. One is Undirected Graph and other is Directed Graph. Now, if you check the photo above, you will see one has arrows and other does not. Therefore, I guess you already got the idea of these two Graphs. However, the definition of Undirected Graph is a Graph in which the Edges have no direction. And Directed Graph is a graph in which each Edge is directed from one Vertex to another (or the same) Vertex.

Now I will be going directly to the technical terms:

A graph G is represented as G = (V,E), in where

V: set of vertices

E: set of edges connecting the vertices in V

An edge e = (u,v) is a pair of vertices

Here are some photos for your convenience:

Graph

Every Tree is a Graph but Every Graph is not Tree

There are some more types/things in Graphs:

1. Complete Graph: A graph in which every vertex is directly connected to every other vertex.
2. Weighted Graph: A graph in which each edge carries a value.
3. Adjacent Vertices: Two vertices in a graph that are connected by an edge.
4. Path: A sequence of vertices that connects two nodes in a graph.

Here is a photo to let you help visualizing…

This is a fare graph of some American states

You may think that “Enough with Theory shite, I want to see some implementation”. Well, I am not going to disappoint you. We implement the Graphs with 2D Arrays. The Indices contains the Vertices and the values that they store contains Edges. Basically the nodes of the Linked List contains the index of adjacent vertex, weight and the pointer to next Edge node.

Now, you know what are the specific indices 😉

Now, you may ask me I understood graphs, trees and such things. What is the use of this? Well, Graph is used in lot of network related algorithm. A common application of graph is seen in Markov Chaining which finds its application in predictive analysis. Text prediction etc. Facebook social media connections are nothing but a very big distributed graph. Basically, if you want to find a pattern or something, Graph is a very useful way to do so.

Also, let us consider the operating system that you are using. This file management system is a tree. You may use Facebook, that is based on graph and its algorithm. Plus, the google maps is based on graph algorithms too.

Finally

I know what you are feeling with this boring chitchat but guess what? It is about to end. I hope you find the “Graph” u n d e r s t a n d a b l e. Please do correct me if I made any mistake. I will be waiting, till then, kbye.

I can feel you ;_;