Archives

Graph data structure tutorial 9. Euler Graph

Definition: A graph having Euler Path is called as Euler graph.  Sometimes Euler path is also called as Euler Circuit. So, what is Euler path or Euler Circuit? A path which starts and ends at same vertex is called as Euler Path. It means, you need to visit all the edges only one. Note: A […]

Graph data structure tutorial 8. Isomorphic Graph

Introduction to Isomorphic Graph and understanding with example In this chapter we shall learn about Isomorphic Graph with example. Definition: 2 graph G1 and G2 are said to be isomorphic if there exist a match between their vertices and edges such that their incidence relationship is preserved.  For 2 graph to be isomorphic, it should […]

Graph data structure tutorial 7. Graph colouring problem

In this tutorial we shall learn about 2 Colour Graph Problem In general graph colouring or edge colouring problem we need to assign colour to vertices in such a way that no edge link two vertices with the same colour. Consider the below set of images: Here graph a is valid. But graph b is […]

Graph data structure tutorial 6. Bipartite graph

In this tutorial we shall learn about bipartite graph. Definition: A graph G(V, E) is called as bipartite graph if all the vertices (V) can be divided into 2 distinct disjoint non empty sets V1 and V2 such that every edge in the graph connects a vertex in V1 and vertex in V2, so that […]

Graph data structure tutorial 5. Graph Traversal using Stack and Queue

In previous chapter we learnt about graph traversal in general. In this chapter we shall learn how to do graph traversal using Stack and Queue. DFS graph traversal using Stack: As in DFS traversal we take a node and go in depth, till we find that there is no further path. Then we backtrack to […]

Graph data structure tutorial 4. Graph Traversal

In the previous chapter we learnt about tree traversal. In this chapter we shall learn about graph traversal. Graph traversal can be done in 2 ways: 4.1 DFS: Depth first search 4.2 BFS: Breadth first search 4.1 Depth First Search As the name suggests, we take a node and follow deep in the node and […]

Graph data structure tutorial 3. Graph Representation Adjacency List

In this chapter we shall learn about: 3.1 Introduction 3.2 Representation in Linked List 3.3 Now why do we use Linked List to represent Adjacency Lists? 3.4 Implementation of Graph Representation using Adjacency Lists using C++ 3.5 Output 3.1 Introduction: In the previous chapter we have seen representing graph using Adjacency Matrix. The drawback is […]

Graph data structure tutorial 2. Graph Representation Adjacency Matrix

In this chapter we shall learn about: 2.1 Introduction 2.2 Understanding of Graph Representation adjacency matrix with an example 2.3 Implementation 2.4 Output 2.1 Introduction: In this tutorial we shall see how to store a graph with the help of a matrix. As it stores the path between 2 vertices, it is called as adjacency […]

Graph data structure tutorial 1. Graph Introduction

In this chapter we shall learn about: 1.1 Graph Definition 1.2 Types of graph 1.3 Usage of graph 1.1 Graph Definition Graph like trees is a non-linear data structure. Like trees, graph is also made of collection of nodes/vertices and edges. But unlike trees, graph will not have any root node. In fact, you can […]