Graphs introduction

A graph(G) consists of two sets Vertices and Edges ‘V’ is finite, nonempty set of vertices which are called edges. V(G) and E(G) represent a set of vertices and edges of the graph ‘G’.We can also denote a Graph as G=(V, E) or G(V, E)

Graphs data structures

Types of graphs

  • Directed graph
  • Undirected graph

Directed Graph

In a directed graph each edge is represented by <u,v> where u is tail and ‘V’ is head of the edge.therefore <u,v> and <v,u> are different edges in a directional graph

Directed Graph

undirected graph

In undirected graph no specific direction is given in this <u,v> and <v,u> are same edges

undirected graph

Applications of graphs

graph-theory mostly used in mathematics that deals with problems and applications such as

  1. shortest path problem
  2. scheduling algorithms
  3. network analysis and topology
  4. to resolve the connection problems
  5. to use in nodes and puzzles

Degree of a node/Vertex: no of edges coming into the vertex and going out from the vertex is said to be a degree of a node.

  • a number of edges coming into the vertex and going out from the vertex is said to be a degree of a node.
  • a number of edges of outgoing edges are said to be out degree of the vertex.
degree of a nodes

Representation of graphs

  • Adjacency Matrices
  • Adjacency lists
  • Adjacency Multi lists

Adjacency matrices

If a graph G=(V, E) has n vertices then the adjacency matrix shall contain ‘n’ rows and ‘n’ columns

If there exists an edge between the vertices Vi and Vj then the matrix shall represent by 1 in the ith row and jth column. Rest of the positions is marked by ‘0’

The adjacency matrix for the undirected graph is symmetric because if there is an edge from a to b then we also have an edge from b to a

The adjacency matrix for the directed graph is not symmetric.

Adjacency matrices

Adjacency Lists

In this representation of the graph, the n-rows of adjacency matrix are replaced by n-linked lists nodes for each vertex of the graph .the node of the linked lists

Graphs introduction 1

If the graph has ‘n’ vertices and ‘E’ number of edges then we need ‘n’ head nodes and 2E list nodes

Adjacency Lists

Adjacency multi lists

In order to reduce the duplicate entries of the edges between two vertices Vi and Vj we have adjacency multi-list representation

For each edge, there is exactly one node but this node is an adjacency list of both the vertices represent in the head node.

This representation has two parts:-

  • Head node containing all the vertices information
  • set of linked for list edges information
Adjacency multi lists

Default image
Vishal Devxo
Vishal Devxo is a DevOps engineer and a Backend developer, he spends all his time for creating good tutorials with better visuals and blogging, developed some projects based on Python-Django, some hacking modules and scripts in python