Representation and Introduction of Graph

5 min readAug 26, 2020

In this Article , You will know how to Represent Graph and some of the basics terminologies also . And how to code Representation .

Introduction

In the real world, many problems are represented in terms of objects and connections between them. For example, in an airline route map, we might be interested in questions like: “What’s the fastest way to go from Hyderabad to New York?” or “What is the cheapest way to go from Hyderabad to New York?” To answer these questions we need information about connections (airline routes) between objects (towns). Graphs are data structures used for solving these kinds of problems.

Image Credit — https://dev.to/fahimulhaq/top-8-data-structures-for-coding-interviews-and-practice-interview-questions-2pb

Graph

A graph is a pair (V, E), where V is a set of nodes, called vertices, and £ is a collection of pairs of vertices, called edges.

Vertices and edges are positions and store elements

Definitions that we use:

Directed edge:

ordered pair of vertices (u, v)
first vertex u is the origin
second vertex v is the destination
Example: one-way road traffic

Undirected edge:

Unordered pair of vertices (u, v)
Example: railway lines

Similarly as in the case of edges , in graph if all the edges are one way then then it will be called as Directed Graph and if two way then it will be called as Undirected Graph . See the below images :

Note : A graph with no cycles is called a tree. A tree is an acyclic connected graph.

A self loop is an edge that connects a vertex to itself. see below :

The Degree of a vertex is the number of edges incident on it.

Graph Representation

In Graphs we need to represent them in some useful form. Basically, there are three ways of doing this:

Adjacency Matrix
Adjacency List
Adjacency Set

Adjacency Matrix

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w. (*this para is from Geeksforgeek) .

For the below graph , matrix will be :

The adjacency graph for the above graph will be :

Code Implementation of Adjacency Matrix


class Graph:
    def __init__(self , size):
        self.adjMatrix = []
        for i in range(size):
            self.adjMatrix.append([0 for j in range(size)])
                
    
    def add_edge(self, v1 , v2):
        if v1 == v2:
            print("For now, we are not learned about loop edges")
            return
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1
        
        
    def remove_edge(self , v1 , v2):
        if self.adjMatrix[v1][v2] == 0:
            print("For now, we are not learned about loop edges")
            return
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0
        
    def print_graph(self):
        for i in self.adjMatrix:
            print(i)
            
            
instance = Graph(4)
instance.add_edge(0 , 1)
instance.add_edge(1 , 2)
instance.add_edge(0 , 2)
instance.add_edge(2 , 3)
instance.print_graph()

Adjacency List

An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex.

Considering the same example as that of the adjacency matrix, the adjacency list representation can be given as:

Since vertex A has an edge for B and D, we have added them in the adjacency list for A. The same is the case with other vertices as well.

Code Implementation of Adjacency List

class Node:
    def __init__(self,v):
        self.vertex = v
        self.next = None
        
class Graph:
    def __init__(self,size):
        self.V = size
        self.graph = [None]*size
        
    def add__edge(self , source , destination):
        node = Node(destination)
        node.next = self.graph[source]
        self.graph[source] = node
        
        node = Node(source)
        node.next = self.graph[destination]
        self.graph[destination] = node
        
    def printGraph(self):
        for i in range(self.V):
            temp = self.graph[i]
            while temp :
                print(temp.vertex)
                temp = temp.next
            print("\n")
    
instance = Graph(4)
instance.add__edge(0 , 1)
instance.add__edge(0 , 2)
instance.add__edge(1 , 2)
instance.add__edge(2 , 3)
instance.printGraph()

Directed Graph : are having Directions 
UnDriected Graph : dont have the Directions
Cyclic Graph : A node can be reach again while traveling
Acyclic Graph : Vice Versa
Connected Graph : Every node can reach to every node
Disconnected Graph : Vice Versa

Sources

My LinkedIn :- linkedin.com/in/my-pro-file

Topics You may Interested IN :

BST , Tree : https://medium.com/dev-genius/trees-binary-search-trees-and-traversal-ab63e192f3a7
Heap and Prioriy Queue : https://medium.com/@mdcode2021/heap-and-priority-queue-fbd41333dc0d
All About Doubly Linked List : https://medium.com/@mdcode2021/all-about-doubly-linked-list-30f0f08afb9c
Merge Sort : https://medium.com/swlh/title-1692d9fb5ced
Insertion Sort : https://medium.com/dev-genius/insertion-sort-program-in-swift-31740a454573
Counting Sort : https://medium.com/@mdcode2021/counting-sort-algorithm-c32d71f2cc79
Selection Sort : https://medium.com/@mdcode2021/line-by-line-selection-sort-algorithm-explained-in-c-dd49638b15e