Graph Data Structure Concepts with Types, Representations, Traversal Techniques, and Real-World Applications

Dr.M.Usha Assistant Professor, Department of CSE Velammal engineering College Velammal Engineering College (An Autonomous Institution, Affiliated to Anna University, Chennai) (Accredited by NAAC & NBA) INTRODUCTION TO GRAPH

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 2 GRAPH  A Graph is a non-linear data structure consisting of nodes and edges.  The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.  Generally, a graph G is represented as G=(V,E) where V is set of vertices and E is set of edges.  In this above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 3

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 4 APPLICATIONS  Graphs are used to solve many real-life problems.  Graphs are used to represent networks.  The networks may include paths in a city or telephone network or circuit network.  Graphs are also used in social networks like linkedIn, Facebook.  For example, in Facebook, each person is represented with a vertex(or node).  Each node is a structure and contains information like person id, name, gender, locale etc.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 9 TYPES OF GRAPH  Directed Graph (or) Digraph  Directed graph is a graph which consists of directed edges, where each edge in E is unidirectional.  It is also referred as Digraph. If (v,w) is a directed edge then (v,w) # (w,v)  Undirected Graph  An undirected graph is a graph, which consists of undirected edges. If (v,w) is an undirected edge, then (v,w)=(w,v)

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 10 GRAPH TERMINOLOGIES  A path is a sequence of vertices such that there is an edge from each vertex to its successor.  A path is simple if each vertex is distinct/A path with no repeated vertices is called a simple path.  A circuit is a path in which the terminal vertex coincides with the initial vertex.(Vertices may repeat but edges are not allowed to repeat.)  Cycle: A circuit that doesn't repeat vertices is called a cycle.(Neither vertices (except possibly the starting and ending vertices) are allowed to repeat, Nor edges are allowed to repeat. 0-1-2-3-0 - CYCLE 0-1-2-4-2-3-0(CIRCUIT)

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 11  Self loop: If there is an edge whose starting and end vertices are same, that is, (vi, vj) is an edge, then it is called a self loop.  Adjacent Vertices Two vertices are said to be adjacent if there is an edge (arc) connecting them.  Adjacent Edges Adjacent edges are edges that share a common vertex.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 12 Degree of the Node  A degree of a node is the number of edges that are connected with that node. A node with degree 0 is called as isolated node.  In degree: Number of edges entering a node  • Out degree: Number of edges leaving a node  • Degree = Indegree + Outdegree

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 13 Connected and Disconnected  A graph G is said to be connected if there exists a path between every pair of vertices.  A connected graph is the one in which some path exists between every two vertices (u, v) in V.  There are no isolated nodes in connected graph.  UNCONNECTED/DisConnected GRAPH: A graph is said as unconnected graph if there exist any 2 unconnected components.  Example: • H1 and H2 are connected • H3 is disconnected

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 14 CONT..  Weighted Graph  A graph is said to be weighted graph if every edge in the graph is assigned a weight or value. It can be directed or undirected graph.  Complete Graph  A complete graph is a graph in which there is an direct edge between every pair of vertices.  A complete graph with n vertices will have n(n-1)/2 edges.  There is a path from every vertex to every other vertex.  All complete graphs are connected graphs, but not all connected graphs are complete graphs.  A complete digraph is a strongly connected graph.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 16 CONT..  Strongly Connected Graph  If there is a path from every vertex to every other vertex in a directed graph then it is said to be strongly connected graph.  Weakly Connected Graph:  If there does not exist a path from one vertex to another vertex then it is said to be a weakly connected graph.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 17  Regular Graph  A graph G is said to be regular, if all its vertices have the same degree. In a graph, if the degree of each vertex is ‘k’, then the graph is called a ‘k-regular graph’.  In the following graphs, all the vertices have the same degree. So these graphs are called regular graphs.  In both the graphs, all the vertices have degree 2. They are called 2-Regular Graphs.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 18 CYCLIC AND ACYCLIC GRPH  Cyclic Graph  A graph with at least one cycle is called a cyclic graph.  Example  In the above example graph, we have two cycles a-b-c-d-a and c-f-g-e-c. Hence it is called a cyclic graph  Acyclic Graph  A graph with no cycles is called an acyclic graph.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 19 CYCLIC AND ACYCLIC GRPH  Acyclic Graph  A directional graph which has no cycles is referred to as acyclic graph. It is abbreviated as DAG (Directional Acyclic Graph).  If there is a path containing one or more edges which starts from a vertex vi and terminates into the same vertex then the path is known as a cycle.  If a graph(digraph) does not have any cycle then it is called acyclic graph.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 20 GRAPH REPRESENTATION  Graph data structure is represented using following representations...  Adjacency Matrix  Incidence Matrix  Adjacency List

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 21 ADJACENCY MATRIX  The adjacency matrix A for a graph G = (V,E) with n vertices, is an n* n matrix of bits ,  such that A ij = 1 , if there is an edge from vi to vj and  Aij = 0, if there is no such edge

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 23 ADJACENCY LIST  A graph containing m vertices and n edges can be represented using a linked list, referred to as adjacency list.  The number of vertices in a graph forms a singly linked list.  Each vertex have a separate linked list, with nodes equal to the number of edges connected from the corresponding vertex..  Each nodes has at least 2 fields: VERTEX and LINK.  The VERTEX fields contain the indices of the vertices adjacent to vertex i.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 25 Incidence Matrix  A graph containing m vertices and n edges can be represented by a matrix with m rows and n columns.  The matrix formed by storing 1 in the ith row and jth column corresponding to the matrix, if there exists a ith vertex, connected to one end of the jth edge, and 0, if there is no ith vertex, connected to any end of the jth edge of the graph, such a matrix is referred as an incidence matrix.  IncMat [i] [j] = 1,if there is an edge Ejfrom vertex Vi  = 0, otherwise

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 26 EXAMPLE

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 27 Graph Traversals  A graph traversal is a systematic way of visiting the nodes in a specific order.  There are 2 types of graph traversals namely,   Breadth First Search(BFS)   Depth First Search(DFS)

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 29 Depth first search  Visit the first node initially, and then find the unvisited node which is adjacent to the first node, is visited and a DFS is initiated from the adjacent node (considering it as the first node).  If all the adjacent nodes have been visited, backtrack to the last node visited, and find another adjacent node and again initiate the DFS from adjacent node.  This traversal continues until all nodes have been visited once.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 30 Steps to Implement DFS  1. Select the start vertex  2. Visit the vertex ( place 1)  3. Find the adjacent vertices of visited node  Rule 1 − Visit any one of the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.  Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)  Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 32 EXAMPLE 2: top

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 33 top top

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 39 A-B-C-E-D-F-G

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 40 EXAMPLE 2 PREORDER TRAVERSAL S-A-D-G-E-B-F-C

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 41 Applications of DFS   To check whether the undirected graph is connected or not   To check if the connected undirected graph is bi- connected or not   To check whether the directed graph is a-cyclic or not

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 42 BFS (Breadth First Search)  Breadth First Search (BFS) of a graph G starts from an unvisited vertex u.  Then all unvisited vertices vi adjacent to u are visited and then all unvisited vertices wj adjacent to vi are visited and so on.  The traversal terminates when there are no more nodes to visit.  BFS uses a queue data structure to keep track of the order of the nodes whose adjacent nodes are to be visited.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 43 Steps to Implement BFS  1. Select the start vertex and mark it as visited (i.e) place the value 1  2. Enqueue the START vertex.  3. Dequeue the vertex.  4. Find all adjacent unvisited vertices of the dequeued vertex.  5. Mark all unvisited adjacent vertices as visited.  6. Enqueue all adjacent vertices.  7. Repeat from step 3 to step 6 until the queue becomes empty

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 44 Pseudo Code For BFS

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 45 EXAMPLE 2 Front, rear

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 46 FRONT REAR FRONT REAR

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 47 FRONT REAR FRONT REAR

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 48 FRONT REAR

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 49 A-D-B-E-C-F-G Front=1,rear=-1

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 50 EXAMPLE 2 LEVEL ORDER TRAVERSAL S-A-B-C-D-E-F-G

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 51 Applications of BFS  1. To find the shortest path from a vertex s to a vertex v in an unweighted graph  2. To find the length of such a path  3. To find out if a graph contains cycles  4. To construct a BFS tree/forest from a graph

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 52 Comparison between DFS and BFS DFS BFS DFS visit nodes of graph depth wise. It visits nodes until reach a leaf or a node which doesn’t have non-visited nodes. BFS visit nodes level by level in Graph. Usually implemented using a stack data structure. Usually implemented using a queue data structure. Generally requires less memory than BFS. Generally requires more memory than DFS. Not Optimal for finding the shortest distance. optimal for finding the shortest distance. DFS is better when target is far from source. BFS is better when target is closer to source.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 53 CONT.. DFS BFS DFS is more suitable for game or puzzle problems. We make a decision, then explore all paths through this decision. And if this decision leads to win situation, we stop. BFS considers all neighbors first and therefore not suitable for decision making trees used in games or puzzles. Time Complexity of BFS = O(V+E) where V is vertices and E is edges. Time Complexity of DFS is also O(V+E) where V is vertices and E is edges. Some Applications: Finding all connected components in a graph. Finding the shortest path between two nodes. Finding all nodes within one connected component. Testing a graph for bipartiteness. Some Applications: Topological Sorting. Finding connected components. Solving puzzles such as maze. Finding strongly connected components. Finding articulation points (cut vertices) of the graph.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 54 TOPOLOGICAL SORTING  It is a linear ordering of vertices in a directed a-cyclic graph, such that if there is a path from Vi to Vj, then Vj appears after Vi in the linear ordering.  Topological sort is not possible if the graph has a cycle.  Procedure  1. Find the indegree for every vertex  2. Place the vertices whose indegree is zero on the empty queue  3. Dequeue one vertex at a time from the queue and decrement the indegree of all its adjacent vertices  4. Enqueue a vertex to the queue if its indegree falls to zero  5. Repeat from step step 3 unitl the queue becomes empty  The topological ordering is the order in which the vertices are dequeued.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 55 Pseudo Code For Topological Sort

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 56 EXAMPLE  Step 1  Find the Indegree of vertices 1,2,3,4,5,6.  Indegree of a vertex is the number of edges entering into the vertex. Indegree of vertex 1 is 0, vertex 2 is 0, vertex 3 is 1, vertex 4 is 3, vertex 5 is 1, vertex 6 is 3.  Step 2  enqueue() the vertices with Indegree 0. Therefore enqueue() vertices 1 and 2.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 62 Applications:  Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs.  The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started  For example, in constructing a building, the basement must be completed before the first floor, which must be completed before the second floor and so on.  A topological sort gives an order in which we should perform the jobs.  In computer science, applications of this type arise in instruction scheduling, ordering of formula cell evaluation when recomputing formula values in spreadsheets,  Determining the order of compilation tasks to perform in make files  Data Serialization

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 63 Difference Between Tree and Graph TREE GRAPH A tree is a special kind of graph that there are never multiple paths exist. There is always one way to get from A to B. In graph there can be more than one path i.e graph can have uni-directional or bi-directional path (edges) between nodes. Pre-order, in-order, and post-order are some kind of the logarithms that are used in trees to through all elements. Breath First Search, Depth First Search are some kind of searching algorithms in graphs to traverse through each element. A tree cannot have a loop structure. A graph can have a loop structure, which means the last element and the first element are same. There is a unique node called root in trees. There is no unique node called root in graph Tree is a hierarchical model structure. Graph is network model.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 64 CONT.. All trees are graphs. But all graphs are not trees. Main use of trees is for sorting and traversing. Main use of graphs is coloring and job scheduling. Less in complexity compared to graphs. High complexity than trees due to loops. Trees are directed acyclic graphs. Graphs are cyclic or acyclic. Tree contains no loops, no circuits. Graph may contain self-loops, loops. Tree must be connected. Graph may not be connected.

08/17/2025 VELAMMAL ENGINEERING COLLEGE, Dept. of CSE 65 THANK YOU

Graph Data Structure Concepts with Types, Representations, Traversal Techniques, and Real-World Applications

More Related Content

Similar to Graph Data Structure Concepts with Types, Representations, Traversal Techniques, and Real-World Applications

More from usham61

Recently uploaded

Graph Data Structure Concepts with Types, Representations, Traversal Techniques, and Real-World Applications