representation of the data structure

01 Career Opportunities

• DSA Roadmap: A to Z Guide to Learn DSA From Scratch

02 Beginner

• Differences Between Stack and Queue Data Structures
• Breadth First Search vs Depth First Search
• Differences Between Array and Linked List
• Abstract Data Type in Data Structures
• Priority Queue in Data Structures
• One dimensional Array in Data Structures with Example
• Two dimensional Array In Data Structure
• Multi dimensional array in Data Structures
• What are Data Structures - Types of Data Structures (Complete Guide)
• Data Structures and Algorithms
• Recursion in Data Structures: Recursive Function
• Complexity Analysis of Data Structures and Algorithms
• Big O Notation in Data Structures: Time and Space Complexity
• Arrays in Data Structures - Types, Representation & Algorithm (With Examples)
• Types of Arrays in Data Structures: 2D, 3D, Jagged Arrays
• Linked List in Data Structures - Types of Linked Lists & Its Applications
• Doubly Linked List Algorithm in Data Structures with Examples
• Implementing Stack in Data Structures
• Queue in Data Structures - Types & Algorithm (With Example)
• Searching in Data Structures - Its Types, Methods & Techniques
• Brute Force Algorithm in Data Structures: Types, Advantages, Disadvantages

03 Intermediate

• Binary Trees in Data Structures - Types, Implementation, Applications
• Binary Search Tree in Data Structures
• Circular Linked Lists in Data Structures
• What is Linear Search in Data Structures - Its Algorithm, Working, & Complexity
• Binary Search in Data Structures
• Sorting in Data Structures - Types of Sorting Algorithms ( With Examples )
• Bubble Sort in Data Structures
• Selection Sort in Data Structures
• Insertion Sort in Data Structures - Algorithm, Working, & Advantages
• Merge Sort in Data Structures and Algorithms: With Implementation in C++/Java/Python
• Quick Sort Algorithm in Data Structures - Its Types ( With Examples )
• Counting Sort in Data Structures
• Radix Sort in Data Structures - Its Algorithm, Working, & Complexity
• Bucket Sort in Data Structures
• Shell Sort in Data Structures - Algorithm, Visualization, & Complexity
• Divide and Conquer Algorithm in Data Structures - Its Working, Advantages & Disadvantages
• Greedy Algorithm in Data Structures

04 Advanced

• Heap in Data Structures
• Heap Sort Algorithm in Data Structures - Its Working, Implementation & Applications
• Hashing in Data Structures: Types and Functions [With Examples]
• Hash Table in Data Structures

Graphs in Data Structures - Types of Graphs, Representation & Operations

• Breadth First Traversal and Depth First Traversal
• Spanning Tree and Minimum Spanning Tree in Data Structures - Kruskal's and Prim's Algorithms
• AVL Tree in Data Structures with Examples
• Trees in Data Structures - Its Structure, Operations & Applications
• Segment Tree in Data Structures: Operations, Advantages and Disadvantages
• Suffix Array and Suffix Tree in Data Structures & Applications
• K-Dimensional Tree in Data Structures
• Tower of Hanoi in Data Structures
• Bellman Ford’s Algorithm in Data Structures - Working, Example and Applications

05 Questions

• DSA Interview Questions and Answers (Freshers to Experienced)

06 Training Programs

• Java Programming Course
• C++ Programming Course
• Data Structures and Algorithms Training
• Datastructures
• Graphs In Data Structures..

Data Structures & Algorithms Free Course

Graphs in data structures: an overview.

Graph in Data Structures is a type of non-primitive and non-linear data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them. In this DSA tutorial , we will see a detailed starting of the graph concept i.e. its features, types, implementation, etc. To further enhance your understanding and application of graph concepts, consider enrolling in the Dsa Course , where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Graph in Data Structures?

A graph is a collection of nodes that consist of data and are connected to other nodes of the graph. formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E) .

The most common real-life examples of graphs are social media where a User, Photo, Album, Event, Group, Page, Comment, Story, Video, etc represents a node. Every relationship is an edge from one node to another. Whenever you post a photo, join a group, like a page, etc., a new edge is created for that relationship. Thus, it can be said that a social media platform is a collection of nodes and edges.

Graph Terminologies in Data Structures

Graph terminology in data structure refers to the specific vocabulary and concepts used to describe and analyze graphs, which are mathematical structures composed of nodes (also called vertices) connected by edges.

• Node/Vertex: A fundamental unit of a graph. It represents an entity or an element and is usually depicted as a point.
• Edge/Arc: A connection between two nodes. It represents a relationship or a link between the corresponding entities. An edge can be directed (arc), indicating a one-way connection, or undirected, representing a two-way connection.
• Adjacent Nodes: Two nodes that are directly connected by an edge. In an undirected graph, both nodes are considered adjacent to each other. In a directed graph, adjacency depends on the direction of the edge.
• Degree: The degree of a node is the number of edges incident to it, i.e., the number of edges connected to that node. In a directed graph, the degree is divided into two categories: the in-degree (number of incoming edges) and the out-degree (number of outgoing edges).
• Path: A path in a graph is a sequence of edges that connects a sequence of nodes. It can be a simple path (no repeated nodes) or a closed path/cycle (starts and ends at the same node).
• Bipartite Graph: A graph whose nodes can be divided into two disjoint sets such that every edge connects a node from one set to a node from the other set. In other words, there are no edges between nodes within the same set.
• Spanning Tree: A subgraph of a connected graph that includes all the nodes of the original graph and forms a tree (a connected acyclic graph) by eliminating some of the edges.
• Cycle: A closed path in a graph, where the first and last nodes are the same. It consists of at least three edges.

Read More - Best Data Structure Interview Questions and Answers

Types of Graphs in Data Structures

Finite graph.

If the graph, G=(V, E) has a finite number of edges and vertices, it is a finite graph. In other words, both the number of vertices and the number of edges in a finite graph are limited and can be counted.

Infinite Graph

If the graph G=(V, E) has an infinite number of edges and vertices, it is an infinite graph.

Trivial Graph

If a finite graph G=(V, E) has just one vertex and no edges, it is referred to as trivial. It is also known as a singleton graph or a single vertex graph.

Simple Graph

A graph G=(V, E) is a simple one if each pair of nodes or vertices contains just one edge. In order to represent one-to-one interactions between two elements, there is only one edge connecting two vertices.

Multi Graph

A graph G=(V, E) is referred to as a multigraph if it has some parallel edges between two vertices but doesn't contain any self-loop. An edge of a graph that starts from a vertex and ends at the same vertex is called a loop or a self-loop.

It's a revised version of a trivial graph. A graph G=(V, E) is a null graph if it has many vertices but none of them are connected by any edges. A null graph can also be referred to as an edgeless graph, an isolated graph, or a discrete graph.

Complete Graph

A simple graph G=(V, E) with n vertices is also called a complete graph if the degree of each vertex is n-1, i.e. one vertex is attached with n-1 edges or the rest of the vertices in the graph. A complete graph is also called a Full Graph.

Pseudo Graph

A pseudograph exists when a graph G= (V, E) contains some self-loop in addition to some multiple edges.

Regular Graph

Weighted Graph

A graph G=(V, E) in which edges have weights or costs associated with them is a weighted graph.

Directed Graph

A directed graph, also known as a digraph, is a collection of nodes connected by edges, each with a distinct direction.

Undirected Graph

A graph G=(V, E) in which edges have no direction, i.e., the edges do not have arrows indicating the direction of traversal is an undirected graph.

Connected Graph

A graph G = (V, E) is said to be connected if there exists at least one path between each and every pair of vertices in the graph.

Disconnected Graph

If in a graph G = (V, E), there does not exist any path between at least one pair of vertices, it is a disconnected graph. A null graph with n vertices is a disconnected graph.

Cyclic Graph

A graph is termed cyclic if it forms at least one cycle.

Acyclic Graph

A graph is said to be acyclic if it contains no cycles.

Directed Acyclic Graph

It is a graph with directed edges but no cycle.

A subgraph is a set of vertices and edges in one graph that are subsets of another.

Graph Representation in Data Structures

• Graph representation is a way of structuring and visualizing data using nodes (vertices) and edges. It is a technique to store graphs in the memory of a computer.
• In a graph, nodes represent individual entities, while edges represent the relationships or connections between those entities. The connections can be directional or undirected, depending on whether the edges have a specific direction or not.

There are two ways to represent a graph

Adjacency Matrix

An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes in a graph. It is used to represent a finite graph, with 0's and 1's. Since it's a V x V matrix, it is known as a square matrix. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph i.e. if there is any edge connecting a pair of nodes in the graph.

Representation of Undirected Graph

Representation of a Directed Graph

Weighted Undirected Graph Representation

A weighted graph representing these values in the matrix is indicated at the graph's edge.

• Adjacency List

An adjacency list represents a graph as an array of linked lists . The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

Weighted Undirected Graph Representation Using Linked-List

Weighted Undirected Graph Representation Using an Array

Operations on Graphs in Data Structures

The following common operations are performed on graphs in data structures:

Insert vertex

It is a simple addition of a vertex(node) in a graph. It need not be connected to any other vertex(node) through an edge.

Delete vertex

To delete a nod, we also have to remove all the edges associated with that vertex.

Insert Edge

It adds an edge between a pair of vertices.

Delete Edge

An edge can be deleted by severing the link between its vertices or nodes. If all the edges from a particular vertex(node) are removed, then that vertex(node) becomes an isolated vertex.

Graph Traversal

Graph traversal is the process of going through or updating each vertex in a graph. Such traversals are classified according to the order in which the algorithm visits the vertices. A subset of tree traversal is graph traversal.

There are two algorithms/ways to visit a graph:

• Breadth-first search
• Depth-first search

We will study all these two in the section Breadth First Traversal and Depth First Traversal

Application of Graphs

• Maps GPS Systems can be represented using graphs and then can be used by computers to provide various services.
• When various tasks depend on each other, it can be represented using a Directed Acyclic graph and we can find the order in which tasks can be performed using topological sort.
• State Transition Diagram represents what can be the legal moves from current states.
• Graphs can be used to represent the topology of computer networks, such as the connections between routers and switches.

Advantages of Graphs

• Graphs can be used to represent a wide range of relationships and data structures.
• They can be used to model and solve a wide range of problems, including pathfinding, data clustering, network analysis, and machine learning.
• Graph algorithms are often very efficient and can be used to solve complex problems quickly and effectively.
• They can be used to represent complex data structures simply and intuitively, making them easier to understand and analyze.

Disadvantages of Graphs

• Graphs can be complex and difficult to understand, especially for people not familiar with graph theory or related algorithms.
• Creating and manipulating graphs can be computationally expensive, especially very large or complex graphs.
• Graph algorithms can be difficult to design and implement correctly and can be prone to bugs and errors.
• Graphs can be difficult to visualize and analyze, especially for very large or complex graphs, which can make it challenging to extract meaningful insights from the data.

So, here we saw a detailed introduction to graphs in data structures. You might have got at least some idea regarding graphs and their applications. We will cover all its aspects one by one in the upcoming tutorials. To also gain a practical understanding of graphs, enroll in our Best Dsa Course .

Q1. What is a path in a graph?

Q2. what is meant by degree of a node in a graph, q3. what are the two ways to represent a graph.

• Adjacency Matrix 

Live Classes Schedule

Can't find convenient schedule? Let us know

About Author

We use cookies to make interactions with our websites and services easy and meaningful. Please read our Privacy Policy for more details.

Data Structures 101: Graphs — A Visual Introduction for Beginners

Get to know the data structures that you use every day

👋 Welcome! Let’s Start with Some Vital Context. Let me ask you something: ✅ Do you use Google Search? ✅ Do you use Google Maps? ✅ Do you use social media sites?

If your answer is “yes” to any of these questions, then you’ve definitely used graphs and you didn’t even know it! Surprised? 😲 I was, too! This article will give you a visual introduction to the world of graphs, their purpose, elements, and types.

These data structures really caught my attention due to their amazing capabilities. They are so powerful that you won’t even imagine how diverse their real-world applications can be. Let’s begin! 😁

🌐 Real-World Applications — The Magic Begins!

Graphs are used in diverse industries and fields:

• GPS systems and Google Maps use graphs to find the shortest path from one destination to another.
• Social Networks use graphs to represent connections between users.
• The Google Search algorithm uses graphs to determine the relevance of search results.
• Operations Research is a field that uses graphs to find the optimal path to reduce the cost of transportation and delivery of goods and services.
• Even Chemistry uses graphs to represent molecules!!! ❤️

Their applications are amazing, right? Let’s start our journey through this world! 😄

🔵 Meet Graphs!

Now that you have some context, let’s start by talking about their main purpose and elements.

Graphs are used to represent, find, analyze, and optimize connections between elements (houses, airports, locations, users, articles, etc.).

This is an example of what a graph looks like:

💠 Building-Blocks

I’m sure that you noticed two main elements in the diagram above: circles and thick lines connecting them. They are called, respectively, Nodes and Edges .

Let’s see them in more detail! 👍

• Nodes: they are the elements that create the network. They could represent houses, locations, airports, ports, bus stops, buildings, users, basically anything that you could represent as being connected to other similar elements in a network.
• Edges: they are connections between the nodes. They could represent streets, flights, bus routes, a connection between two users in a social network, or anything that could possibly represent a connection between the nodes in the context that you are working with.

😱 What Happens If There Is No Connection?

If two nodes are not connected by an edge, that means that there is no direct connection between them. But don’t panic! 😩 You might still be able to go from one node to another by f ollowing a sequence of edges, similar to driving through several streets to reach your final destination. 🚛️ 🚛 🚛

For example, in the diagram below, even though there is no direct connection ( edge ) between the purple node (left) and the yellow node (right), you can go from the purple node to the orange node, to the pink node, to the green node, and finally reach the yellow node. 🏁

This is a key aspect of graphs, that you can search for the element that you are looking for by following the paths available.

🌟 Notation & Terminology

It’s very important to learn the formal “language” to work with graphs:

• |V| = Total number of vertices ( nodes ) in the graph.
• |E| = Total number of connections ( edges ) in the graph.

In the example below, |V| = 6 because there are six nodes (circles) and |E| = 7 because there are seven edges (lines).

📚 Types of Graphs

Graphs are classified based on the characteristics of their edges (connections). Let’s take a look them in detail! 😃

1️⃣ Directed Graphs

In directed graphs, edges have a direction. They go from one node to another, and there is no way to return to the initial node through that edge.

As you can see in the diagram below, the edges (connections) now have arrows that point to a specific direction. Think of these edges as one-way streets. You can go in one direction and reach your destination, but you can’t return through that same street, so you need to find an alternative path.

🍕 For example, if we create a graph for a pizza delivery service, representing a city, two houses (nodes) may be connected by a one-way street (edge). You could get from house A to house B through this street, but you couldn’t go back, so you would have to take an alternative path.

💡 Note: In a directed graph, y ou may not be able return at all to your initial location i f there is no path with the appropriate directions. 😞 In the diagram below, you can see that you can successfully go from the purple node to the green node, but notice that there is no way to return from the green node to the purple node because the edges are “one-way streets.”

2️⃣ Undirected Graphs

In this type of graph, edges are undirected (they do not have a specific direction). Think of undirected edges as two-way streets. You can go from one node to another and return through that same “path”.

💡 Note: When you see a diagram of a graph where the edges don’t have arrows pointing in a specific direction, you can assume that the graph is undirected.

🍕 For our pizza delivery service, this would mean that the delivery motorcycle can go from the source to the destination through the same street or path (To their relief! 😇).

In the graph below, you could go from the purple node to the green node and back through the same path , so you don’t reach a point no return. 😌

🏋 Weights? — Yes, Weights!

1️⃣ weighted graphs.

In weighted graphs, each edge has a value associated with it (called weight) . This value is used to represent a certain quantifiable relationship between the nodes they connect.

For example, weights could represent distance, time, the number of connections shared between two users in a social network, or anything that could be used to describe the connection between nodes in the context that you are working with.

These weights are used by Dijkstra’s Algorithm to optimize routes by finding the shortest or least expensive paths between nodes in a network. (Stay tuned for an article on Dijkstra’s Algorithm! 😃).

2️⃣ Unweighted Graphs

In contrast, unweighted graphs do not have weights associated with their edges. An example of this type of graph can be found in social networks, where edges represent the connection between two users. The connection cannot be quantified. Therefore, the edge has no weight.

💡 Note: You may have noticed that, so far, our graphs only have one edge connecting each pair of nodes. It’s natural to ask if there could be more than one edge between a pair of nodes. A ctually, this is possible with M ultigraphs! T hey can have multiple edges connecting the same pair of nodes.

🏆 Number of Edges! — An Important Factor

It’s very important to know if a graph has many or few edges because this is a crucial factor to decide how you will represent this data structure in your code. Let’s see the different types! 👍

1️⃣ Dense Graphs

Dense graphs have many edges. But, wait! ⚠️ I know what you must be thinking, how can you determine what qualifies as “many edges”? This is a little bit too subjective, right? 😇 I agree with you, so let’s quantify it a little bit:

👉 Let’s find the maximum number of edges in a directed graph. If there are |V| nodes in a directed graph (in the example below, six nodes), that means that each node can have up to |v| connections (in the example below, six connections).

Why? Because each node could potentially connect with all other nodes and with itself (see “loop” below) . Therefore, the maximum number of edges that the graph can have is |V|*|V| , which is the total number of nodes multiplied by the maximum number of connections that each node can have.

When the number of edges in the graph is close to the maximum number of edges, the graph is dense. 😉

💡 Note: “Loops” occur when a node has an edge that connects it to itself. Strange and interesting, right? 😄

2️⃣ Sparse Graphs

Sparse Graphs have few edges. As you can see in the diagram below, there aren’t many connections between the nodes.

When the number of edges in the graph is significantly fewer than the maximum number of edges, the graph is sparse. 😉

⭕️ Meet Cycles!

Now let’s see a vital concept to understand graphs, cycles.

You probably noticed that if you follow a sequence of connections in a graph, you may find a path that will take you back to the same node. This is like “walking in circles”, exactly as if you were driving around your city and you took a path that could take you back to your initial location.

In graphs, these “circular” paths are called “cycles”. They are valid paths that start and end at the same node. For example, in the diagram below, you can see that if you start at any node, you can return to that same node by following the edges.

Cycles are not always “isolated” because they can be part of a larger graph. You can detect them by starting your search on a specific node and finding a path that takes you back to that same node.

👋 In Summary…

• Graphs are awesome data structures that you use every day through Google Search, Google Maps, GPS, and social media.
• They are used to represent elements that share connections .
• The elements in the graph are called Nodes and the connections between them are called Edges .
• Graphs can be directed, when their edges have a specific orientation, similar to one-way streets, or undirected, when their edges don’t have a specific orientation, similar to two-way streets.
• Edges can have a value associated with them, called weight .
• If a graph has many edges, it’s called a dense graph. Otherwise, if it has few edges, it’s called a sparse graph.
• A series of connections can form a cycle if they create a path that lets you to return to the same node.

Continue learning about these amazing data structures! It will be totally worth it for your future as a developer. I’m learning about data structures right now, and I find them completely fascinating. 😃 🎆 ❤️

The important thing is to not stop questioning. Curiosity has its own reason for existing. — Albert Einstein

👋 Thank you!

I really hope that you liked my article. ❤️ Follow me on Twitter . 😃

Developer, technical writer, and content creator @freeCodeCamp. I run the freeCodeCamp.org Español YouTube channel.

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

DSA Tutorial

Linked lists, stacks & queues, hash tables, shortest path, minimum spanning tree, maximum flow, time complexity, dsa reference, dsa examples, introduction to data structures and algorithms.

Data Structures is about how data can be stored in different structures.

Algorithms is about how to solve different problems, often by searching through and manipulating data structures.

Theory about Data Structures and Algorithms (DSA) helps us to use large amounts of data to solve problems efficiently.

What are Data Structures?

A data structure is a way to store data.

We structure data in different ways depending on what data we have, and what we want to do with it.

First, let's consider an example without computers in mind, just to get the idea.

If we want to store data about people we are related to, we use a family tree as the data structure. We choose a family tree as the data structure because we have information about people we are related to and how they are related, and we want an overview so that we can easily find a specific family member, several generations back.

With such a family tree data structure visually in front of you, it is easy to see, for example, who my mother's mother is—it is 'Emma,' right? But without the links from child to parents that this data structure provides, it would be difficult to determine how the individuals are related.

Data structures give us the possibility to manage large amounts of data efficiently for uses such as large databases and internet indexing services.

Data structures are essential ingredients in creating fast and powerful algorithms. They help in managing and organizing data, reduce complexity, and increase efficiency.

In Computer Science there are two different kinds of data structures.

Primitive Data Structures are basic data structures provided by programming languages to represent single values, such as integers, floating-point numbers, characters, and booleans.

Abstract Data Structures are higher-level data structures that are built using primitive data types and provide more complex and specialized operations. Some common examples of abstract data structures include arrays, linked lists, stacks, queues, trees, and graphs.

What are Algorithms?

An algorithm is a set of step-by-step instructions to solve a given problem or achieve a specific goal.

A cooking recipe written on a piece of paper is an example of an algorithm, where the goal is to make a certain dinner. The steps needed to make a specific dinner are described exactly.

When we talk about algorithms in Computer Science, the step-by-step instructions are written in a programming language, and instead of food ingredients, an algorithm uses data structures.

Algorithms are fundamental to computer programming as they provide step-by-step instructions for executing tasks. An efficient algorithm can help us to find the solution we are looking for, and to transform a slow program into a faster one.

By studying algorithms, developers can write better programs.

Algorithm examples:

• Finding the fastest route in a GPS navigation system
• Navigating an airplane or a car (cruise control)
• Finding what users search for (search engine)
• Sorting, for example sorting movies by rating

The algorithms we will look at in this tutorial are designed to solve specific problems, and are often made to work on specific data structures. For example, the 'Bubble Sort' algorithm is designed to sort values, and is made to work on arrays.

Data Structures together with Algorithms

Data structures and algorithms (DSA) go hand in hand. A data structure is not worth much if you cannot search through it or manipulate it efficiently using algorithms, and the algorithms in this tutorial are not worth much without a data structure to work on.

DSA is about finding efficient ways to store and retrieve data, to perform operations on data, and to solve specific problems.

By understanding DSA, you can:

• Decide which data structure or algorithm is best for a given situation.
• Make programs that run faster or use less memory.
• Understand how to approach complex problems and solve them in a systematic way.

Where is Data Structures and Algorithms Needed?

Data Structures and Algorithms (DSA) are used in virtually every software system, from operating systems to web applications:

• For managing large amounts of data, such as in a social network or a search engine.
• For scheduling tasks, to decide which task a computer should do first.
• For planning routes, like in a GPS system to find the shortest path from A to B.
• For optimizing processes, such as arranging tasks so they can be completed as quickly as possible.
• For solving complex problems: From finding the best way to pack a truck to making a computer 'learn' from data.

DSA is fundamental in nearly every part of the software world:

• Operating Systems
• Database Systems
• Web Applications
• Machine Learning
• Video Games
• Cryptographic Systems
• Data Analysis
• Search Engines

Theory and Terminology

As we go along in this tutorial, new theoretical concepts and terminology (new words) will be needed so that we can better understand the data structures and algorithms we will be working on.

These new words and concepts will be introduced and explained properly when they are needed, but here is a list of some key terms, just to get an overview of what is coming:

Where to Start?

In this tutorial, you will first learn about a data structure with matching algorithms, before moving on to the next data structure.

Further into the tutorial the concepts become more complex, and it is therefore a good idea to learn DSA by doing the tutorial step-by-step from the start.

And as mentioned on the previous page, you should be comfortable in at least one of the most common programming languages, like for example JavaScript , C or Python , before doing this tutorial.

On the next page we will look at two different algorithms that prints out the first 100 Fibonacci numbers using only primitive data structures (two integer variables). One algorithm uses a loop, and one algorithm uses something called recursion.

Click the 'Next' button to continue.

COLOR PICKER

Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail: [email protected]

Report Error

If you want to report an error, or if you want to make a suggestion, send us an e-mail: [email protected]

Top Tutorials

Top references, top examples, get certified.

Visu Algo .net/en

Visualising data structures and algorithms through animation.

VisuAlgo project is funded by Optiver for 2023-2024. We now open VisuAlgo account registration to every Computer Science students/teachers worldwide and have started various upgrading (sub)-projects.

Do You Know? Next Random Tip

VisuAlgo is a trilingual site. Try visiting the other versions of VisuAlgo other than the default English version , e.g.,  Chinese  or  Indonesian . Users can see the translation statistics for these three pages. We aim to make all three has near 100% translation rate. Unfortunately the translation progress with other languages are too far behind and they are thus redirected to English.

In VisuAlgo, you can use your own input for any algorithm instead of using only the provided sample inputs. This is one of the key feature of VisuAlgo. Try the graph drawing feature in these 9 graph-related visualizations: Graph DS , DFS/BFS , MST , SSSP , Max Flow , Matching , MVC , Steiner Tree , and TSP . You can also click tag 'graph' in any of these 9 graph-related visualization boxes or type in 'graph' in the search box.

Here are some of the newer visualization features: ability to show two visualization scales (1.0x and 0.5x), the zoom-out scale is used to show operations of a slightly bigger test cases,  /list (the linked list are no longer automatically re-layout for most cases to strengthen the O(1) impression of almost all Linked List operations).

Breaking news [Fri, 09 Jun 23]: VisuAlgo project is funded by Optiver starting today. We now open VisuAlgo account registration to every Computer Science students/teachers worldwide. Go to the login page and follow the on-screen instructions to create a new VisuAlgo account (no longer restricted to 'nus.edu'-related emails).

To compare 2 related algorithms, e.g., Kruskal's vs Prim's on the same graph, or 2 related operations of the same data structure, e.g., visualizing Binary (Max) Heap as a Binary Tree or as a Compact Array, open 2 VisuAlgo pages in 2 windows and juxtapose them. Click here to see the screenshot. This juxtaposition technique can be used anytime you want to compare two similar data structures or algorithms.

You can visualize the recursion tree (or DAG, if there are overlapping subproblems and Dynamic Programming (DP) is applicable) of ANY valid recursive function that can be written in JavaScript. Click here to see the screenshot. Obviously do not try visualizing recursion with a gigantic recursion tree as doing so will crash your own web browser/computer.

VisuAlgo loads fast for first time visitors (we use Cloudflare global CDN), but it loads 'almost instantly' for returning visitors as we also cache lots of static content of VisuAlgo :). So, do not use incognito or private browsing mode to keep the cache. Moreover, for NUS students with VisuAlgo accounts, we will load VisuAlgo according to your preferences/class setup after you login .

Each visualization page has an 'e-Lecture Mode' that is accessible from that page's top right corner. This mode is automatically shown to first time (or non logged-in) visitors to showcase the data structure or algorithm being visualized. The quality of e-Lecture mode for many visualization pages have reached the lecture standard of algorithm classes in National University of Singapore :).

Please check the newest features of VisuAlgo: 1). User accounts system for NUS students and verified CS lecturers worldwide (and also read the latest Privacy Policy popup at the bottom right corner), 2). More mobile-friendly setup, 3). More polished e-Lecture notes to reach "NUS standard", and 4). Trilingual capability (/en, /zh, or /id).

VisuAlgo has two main components: The 24 visualization pages and their associated Online Quiz component (more questions are currently being added into the question bank). We do not script any of the questions in Online Quiz :O and all answers will be graded almost instantly :). You can this online quiz system by clicking the 'Training' button on the visualization module.

Array ✍

Sorting ✍ training, bitmask ✍ training, linked list ✍ training, binary heap ✍ training, hash table ✍ training, binary search tree ✍ training, graph structures ✍ training, union-find ds ✍ training, fenwick tree ✍ training, segment tree ✍ training, recursion tree/dag ✍ training, graph traversal ✍ training, min spanning tree ✍ training, ss shortest paths ✍ training, cycle finding ✍ training, suffix tree ✍ training, suffix array ✍ training, geometry (polygon) ✍ training, convex hull ✍ training, network flow ✍ training, graph matching ✍ training, min vertex cover ✍ training, steiner tree ✍ training, traveling salesper... ✍ training, np-complete reduct... ✍.

Reload screen or rotate device for a pathway suiting your device orientation

Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

Project Leader & Advisor (Jul 2011-present) Associate Professor Steven Halim , School of Computing (SoC), National University of Singapore (NUS) Dr Felix Halim , Senior Software Engineer, Google (Mountain View)

Undergraduate Student Researchers 1 CDTL TEG 1: Jul 2011-Apr 2012 : Koh Zi Chun, Victor Loh Bo Huai

Final Year Project/UROP students 1 Jul 2012-Dec 2013 : Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun , Ivan Reinaldo

Undergraduate Student Researchers 2 CDTL TEG 2: May 2014-Jul 2014 : Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Final Year Project/UROP students 2 Jun 2014-Apr 2015 : Erin Teo Yi Ling, Wang Zi Jun 2016-Dec 2017 : Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir Aug 2021-Apr 2023 : Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Undergraduate Student Researchers 3 Optiver: Aug 2023-Oct 2023 : Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Final Year Project/UROP students 3 Aug 2023-Apr 2024 : Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

Acknowledgements NUS CDTL gave Teaching Enhancement Grant to kickstart this project. For Academic Year 2023/24, a generous donation from Optiver will be used to further develop VisuAlgo.

Terms of use

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors . You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website ( https://visualgo.net ) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Associate Professor Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Associate Professor Steven Halim. His contact is the concatenation of his name and add gmail dot com.

Privacy Policy

Version 1.2 (Updated Fri, 18 Aug 2023).

Since Fri, 18 Aug 2023, we no longer use Google Analytics. Thus, all cookies that we use now are solely for the operations of this website. The annoying cookie-consent popup is now turned off even for first-time visitors.

Since Fri, 07 Jun 2023, thanks to a generous donation by Optiver, anyone in the world can self-create a VisuAlgo account to store a few customization settings (e.g., layout mode, default language, playback speed, etc).

Additionally, for NUS students, by using a VisuAlgo account (a tuple of NUS official email address, student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your course lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the course smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the course unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Prof Halim himself.

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.

Data Structures and Algorithms

Chapter 10 graphs.

Show Source |    | About    «   9. 12. Hashing Chapter Summary Exercises   ::   Contents   ::   10. 2. Graph Implementations   »

10. 1. Chapter Introduction: Graphs ¶

10. 1.1. graph terminology and implementation ¶.

Graphs provide the ultimate in data structure flexibility. A graph consists of a set of nodes, and a set of edges where an edge connects two nodes. Trees and lists can be viewed as special cases of graphs.

Graphs are used to model both real-world systems and abstract problems, and are the data structure of choice in many applications. Here is a small sampling of the types of problems that graphs are routinely used for.

Modeling connectivity in computer and communications networks.

Representing an abstract map as a set of locations with distances between locations. This can be used to compute shortest routes between locations such as in a GPS routefinder.

Modeling flow capacities in transportation networks to find which links create the bottlenecks.

Finding a path from a starting condition to a goal condition. This is a common way to model problems in artificial intelligence applications and computerized game players.

Modeling computer algorithms, to show transitions from one program state to another.

Finding an acceptable order for finishing subtasks in a complex activity, such as constructing large buildings.

Modeling relationships such as family trees, business or military organizations, and scientific taxonomies.

The rest of this module covers some basic graph terminology. The following modules will describe fundamental representations for graphs, provide a reference implementation, and cover core graph algorithms including traversal, topological sort, shortest paths algorithms, and algorithms to find the minimal-cost spanning tree. Besides being useful and interesting in their own right, these algorithms illustrate the use of many other data structures presented throughout the course.

A graph \(\mathbf{G} = (\mathbf{V}, \mathbf{E})\) consists of a set of vertices \(\mathbf{V}\) and a set of edges \(\mathbf{E}\) , such that each edge in \(\mathbf{E}\) is a connection between a pair of vertices in \(\mathbf{V}\) . 1 The number of vertices is written \(|\mathbf{V}|\) , and the number of edges is written \(|\mathbf{E}|\) . \(|\mathbf{E}|\) can range from zero to a maximum of \(|\mathbf{V}|^2 - |\mathbf{V}|\) .

Some graph applications require that a given pair of vertices can have multiple or parallel edges connecting them, or that a vertex can have an edge to itself. However, the applications discussed here do not require either of these special cases. To simplify our graph API, we will assume that there are no duplicate edges.

A graph whose edges are not directed is called an undirected graph , as shown in part (a) of the following figure. A graph with edges directed from one vertex to another (as in (b)) is called a directed graph or digraph . A graph with labels associated with its vertices (as in (c)) is called a labeled graph . Associated with each edge may be a cost or weight . A graph whose edges have weights (as in (c)) is said to be a weighted graph .

Figure 10.2.1: Some types of graphs.

An edge connecting Vertices \(a\) and \(b\) is written \((a, b)\) . Such an edge is said to be incident with Vertices \(a\) and \(b\) . The two vertices are said to be adjacent . If the edge is directed from \(a\) to \(b\) , then we say that \(a\) is adjacent to \(b\) , and \(b\) is adjacent from \(a\) . The degree of a vertex is the number of edges it is incident with. For example, Vertex \(e\) below has a degree of three.

In a directed graph, the out degree for a vertex is the number of neighbors adjacent from it (or the number of edges going out from it), while the in degree is the number of neighbors adjacent to it (or the number of edges coming in to it). In (c) above, the in degree of Vertex 1 is two, and its out degree is one.

A sequence of vertices \(v_1, v_2, ..., v_n\) forms a path of length \(n-1\) if there exist edges from \(v_i\) to \(v_{i+1}\) for \(1 \leq i < n\) . A path is a simple path if all vertices on the path are distinct. The length of a path is the number of edges it contains. A cycle is a path of length three or more that connects some vertex \(v_1\) to itself. A cycle is a simple cycle if the path is simple, except for the first and last vertices being the same.

An undirected graph is a connected graph if there is at least one path from any vertex to any other. The maximally connected subgraphs of an undirected graph are called connected components . For example, this figure shows an undirected graph with three connected components.

A graph with relatively few edges is called a sparse graph , while a graph with many edges is called a dense graph . A graph containing all possible edges is said to be a complete graph . A subgraph \(\mathbf{S}\) is formed from graph \(\mathbf{G}\) by selecting a subset \(\mathbf{V}_s\) of \(\mathbf{G}\) ’s vertices and a subset \(\mathbf{E}_s\) of \(\mathbf{G}\) ‘s edges such that for every edge \(e \in \mathbf{E}_s\) , both vertices of \(e\) are in \(\mathbf{V}_s\) . Any subgraph of \(V\) where all vertices in the graph connect to all other vertices in the subgraph is called a clique .n

A graph without cycles is called an acyclic graph . Thus, a directed graph without cycles is called a directed acyclic graph or DAG .

A free tree is a connected, undirected graph with no simple cycles. An equivalent definition is that a free tree is connected and has \(|\mathbf{V}| - 1\) edges.

10. 1.1.1. Graph Representations ¶

There are two commonly used methods for representing graphs. The adjacency matrix for a graph is a \(|\mathbf{V}| \times |\mathbf{V}|\) array. We typically label the vertices from \(v_0\) through \(v_{|\mathbf{V}|-1}\) . Row \(i\) of the adjacency matrix contains entries for Vertex \(v_i\) . Column \(j\) in row \(i\) is marked if there is an edge from \(v_i\) to \(v_j\) and is not marked otherwise. The space requirements for the adjacency matrix are \(\Theta(|\mathbf{V}|^2)\) .

The second common representation for graphs is the adjacency list . The adjacency list is an array of linked lists. The array is \(|\mathbf{V}|\) items long, with position \(i\) storing a pointer to the linked list of edges for Vertex \(v_i\) . This linked list represents the edges by the vertices that are adjacent to Vertex \(v_i\) .

Here is an example of the two representations on a directed graph. The entry for Vertex 0 stores 1 and 4 because there are two edges in the graph leaving Vertex 0, with one going to Vertex 1 and one going to Vertex 4. The list for Vertex 2 stores an entry for Vertex 4 because there is an edge from Vertex 2 to Vertex 4, but no entry for Vertex 3 because this edge comes into Vertex 2 rather than going out.

Figure 10.2.7: Representing a directed graph.

Both the adjacency matrix and the adjacency list can be used to store directed or undirected graphs. Each edge of an undirected graph connecting Vertices \(u\) and \(v\) is represented by two directed edges: one from \(u\) to \(v\) and one from \(v\) to \(u\) . Here is an example of the two representations on an undirected graph. We see that there are twice as many edge entries in both the adjacency matrix and the adjacency list. For example, for the undirected graph, the list for Vertex 2 stores an entry for both Vertex 3 and Vertex 4.

Figure 10.2.8: Representing an undirected graph.

The storage requirements for the adjacency list depend on both the number of edges and the number of vertices in the graph. There must be an array entry for each vertex (even if the vertex is not adjacent to any other vertex and thus has no elements on its linked list), and each edge must appear on one of the lists. Thus, the cost is \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\) .

Sometimes we want to store weights or distances with each each edge, such as in Figure 10.2.1 (c). This is easy with the adjacency matrix, where we will just store values for the weights in the matrix. In Figures 10.2.7 and 10.2.8 we store a value of “1” at each position just to show that the edge exists. That could have been done using a single bit, but since bit manipulation is typically complicated in most programming languages, an implementation might store a byte or an integer at each matrix position. For a weighted graph, we would need to store at each position in the matrix enough space to represent the weight, which might typically be an integer.

The adjacency list needs to explicitly store a weight with each edge. In the adjacency list shown below, each linked list node is shown storing two values. The first is the index for the neighbor at the end of the associated edge. The second is the value for the weight. As with the adjacency matrix, this value requires space to represent, typically an integer.

Which graph representation is more space efficient depends on the number of edges in the graph. The adjacency list stores information only for those edges that actually appear in the graph, while the adjacency matrix requires space for each potential edge, whether it exists or not. However, the adjacency matrix requires no overhead for pointers, which can be a substantial cost, especially if the only information stored for an edge is one bit to indicate its existence. As the graph becomes denser, the adjacency matrix becomes relatively more space efficient. Sparse graphs are likely to have their adjacency list representation be more space efficient.

Example 10.2.1

Assume that a vertex index requires two bytes, a pointer requires four bytes, and an edge weight requires two bytes. Then, each link node in the adjacency list needs \(2 + 2 + 4 = 8\) bytes. The adjacency matrix for the directed graph above requires \(2 |\mathbf{V}^2| = 50\) bytes while the adjacency list requires \(4 |\mathbf{V}| + 8 |\mathbf{E}| = 68\) bytes. For the undirected version of the graph above, the adjacency matrix requires the same space as before, while the adjacency list requires \(4 |\mathbf{V}| + 8 |\mathbf{E}| = 116\) bytes (because there are now 12 edges represented instead of 6).

The adjacency matrix often requires a higher asymptotic cost for an algorithm than would result if the adjacency list were used. The reason is that it is common for a graph algorithm to visit each neighbor of each vertex. Using the adjacency list, only the actual edges connecting a vertex to its neighbors are examined. However, the adjacency matrix must look at each of its \(|\mathbf{V}|\) potential edges, yielding a total cost of \(\Theta(|\mathbf{V}^2|)\) time when the algorithm might otherwise require only \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\) time. This is a considerable disadvantage when the graph is sparse, but not when the graph is closer to full.

10. 1.2. Graph Terminology Questions ¶

Contact Us | | Privacy | | License    «   9. 12. Hashing Chapter Summary Exercises   ::   Contents   ::   10. 2. Graph Implementations   »

Contact Us | | Report a bug

• Data Structure and Algorithm

Introduction to Graph Data Structure with Practical Examples

• Graph Data Structure
• Components of a Graph Data Structure
• Types of Graphs
• Adjacency Matrix:
• Adjacency List:
• Depth-First Search (DFS):
• Breadth-First Search (BFS):
• Dijkstra’s Algorithm:
• Bellman-Ford Algorithm:
• Prim’s Algorithm & Kruskal’s Algorithm:
• A* Search Algorithm:
• Min-Cost Flow Algorithm:
• Applications of Graph Data Structure
• Run C Programming Online Compiler

Have you ever tried to find the quickest way to get somewhere on a map when the streets are busy? And have you noticed how easy it is to see who your friends know on social media? Well, both of these things use something called a graph. It’s like a map that helps computers figure out connections and the best routes. It’s what makes finding friends and navigating streets so smooth.

¶ Graph Data Structure

A graph is a collection of nodes (vertices) interconnected by edges . This abstraction allows us to represent various relationships between objects or entities. Formally, a graph G is defined as a pair (V, E) , where V represents the set of vertices or nodes, and E represents the set of edges connecting these nodes. In computer science and mathematics, the graph data structure stands as a fundamental concept with far-reaching applications. From social networks to transportation systems, algorithms leveraging graphs power a wide range of modern technologies.

¶ Components of a Graph Data Structure

A graph is comprised of multiple components that work together to define its structure and properties. These components include,

Vertices: Vertices are synonymous with nodes and represent the entities within the graph. They are often associated with attributes or properties that describe the entity they represent.

Edges: Edges define the relationships or connections between vertices. Depending on the type of graph, edges may be directed or undirected, indicating the flow or lack thereof between connected vertices.

Weight: In weighted graphs, edges are assigned numerical values that quantify the strength or distance between connected vertices. These weights are crucial for algorithms that optimize paths or analyze network efficiency.

Degree: The degree of a vertex refers to the number of edges incident to it. In directed graphs, vertices have both an in-degree (number of incoming edges) and an out-degree (number of outgoing edges).

Cycle: A cycle in a graph occurs when a sequence of edges forms a closed loop, allowing traversal from a vertex back to itself. Detection of cycles is essential for various graph algorithms and ensures the integrity of certain graph structures.

Connected Components: In undirected graphs, connected components are subsets of vertices where each vertex is reachable from every other vertex within the same subset. Understanding connected components helps analyze the connectivity of a graph.

¶ Types of Graphs

Graphs can be categorized in various ways depending on the types of nodes and edges, as well as their relationships.

Directed Graph (Digraph): Directed graphs have edges with a direction, indicating a one-way relationship between vertices. Each edge connects a source vertex to a target vertex, denoting the direction of the relationship. They are commonly used to model scenarios with asymmetric relationships, such as precedence constraints in project scheduling or flow of information in networks.

Undirected Graph: Undirected graphs have edges without a direction, implying a two-way relationship between vertices. Edges connect vertices in both directions, indicating mutual connections or interactions. They are suitable for modeling symmetric relationships, such as friendships in social networks or physical connections in transportation networks.

Weighted Graph: Weighted graphs assign numerical values known as weights to edges, representing additional information about the relationship between vertices. These weights typically denote metrics such as distance, cost, or capacity associated with traversing the edge. Weighted graphs are used in various applications, including route optimization, resource allocation, and network analysis.

Sparse Graph: Sparse graphs have relatively few edges compared to the maximum possible number of edges. They typically have a low edge-to-vertex ratio, resulting in a sparse representation. Examples include social networks with a large number of users but relatively few connections between them.

Dense Graph: Dense graphs contain a significant number of edges compared to the maximum possible. They have a high edge-to-vertex ratio, resulting in a dense representation. Examples include fully connected networks or graphs representing complete graphs.

Connected Graph: Connected graphs have a path between every pair of vertices. All vertices are reachable from any other vertex through a series of edges. They are integral in network analysis, communication systems, and transportation networks.

Disconnected Graph: Disconnected graphs consist of two or more connected components, where there is no path between vertices in different components. Disconnected graphs may arise in scenarios where there are isolated clusters of vertices with no connections to other parts of the graph.

Understanding the different types of graphs and their characteristics is essential for effectively modeling real-world scenarios and selecting appropriate algorithms for graph analysis and manipulation.

¶ Representation of a Graph in Graph Data Structure

Graphs can be represented in programming using various data structures, each offering unique advantages depending on the specific requirements of the application. Here are some common representations:

¶ Adjacency Matrix:

An adjacency matrix is a 2D array where each cell represents the presence or absence of an edge between two vertices. For an unweighted graph, the cell value can be either 0 or 1 to denote absence or presence of an edge respectively. For a weighted graph, the cell value can represent the weight of the edge. This representation is efficient for dense graphs but can be memory-intensive for sparse graphs.

¶ Adjacency List:

An adjacency list is a collection of lists or arrays where each list corresponds to a vertex in the graph. Each list contains the vertices adjacent to the corresponding vertex. This representation is more memory-efficient for sparse graphs compared to adjacency matrices. It allows for fast traversal of neighbors of a vertex.

¶ Edge List:

An edge list is a list of tuples or objects, where each tuple/object represents an edge in the graph. Each tuple/object contains information about the vertices that the edge connects and, optionally, the weight of the edge. This representation is simple and compact, making it suitable for small graphs.

¶ Notable Graph Algorithms

Graph algorithms are essential tools in computer science and are widely used in various applications. Here are some useful graph algorithms and their common applications:

¶ Depth-First Search (DFS):

• Usage: Traversing or searching a graph deeply, exploring as far as possible along each branch before backtracking.
• Applications: Topological sorting, cycle detection, pathfinding, maze solving, graph connectivity analysis.

¶ Breadth-First Search (BFS):

• Usage: Traversing or searching a graph level by level, exploring neighbors of a vertex before moving to the next level.
• Applications: Shortest path finding in unweighted graphs, connected components, network broadcasting, puzzle solving.

¶ Dijkstra’s Algorithm:

• Usage: Finding the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.
• Applications: Navigation systems, network routing protocols, shortest path problems in transportation and logistics.

¶ Bellman-Ford Algorithm:

• Usage: Finding the shortest path from a single source vertex to all other vertices in a graph, even with negative edge weights (but no negative cycles).
• Applications: Network routing algorithms, distributed systems, traffic management.

¶ Prim’s Algorithm & Kruskal’s Algorithm:

• Usage: Finding the minimum spanning tree (MST) of a connected, undirected graph.
• Applications: Network design, clustering, sensor networks, electrical circuit design.

¶ A* Search Algorithm:

• Usage: Finding the shortest path from a starting node to a target node in a weighted graph, using a heuristic function to guide the search.
• Applications: Pathfinding in video games, route planning in navigation systems, robotics, AI applications.

¶ Min-Cost Flow Algorithm:

• Usage: Finding the flow through a flow network that minimizes the total cost of sending the flow from source to sink, considering both capacities and costs on edges.
• Applications: Transportation and logistics optimization, network routing with costs, resource allocation with variable costs.

¶ Applications of Graph Data Structure

The graph data structure finds application in various domains. Here are some notable applications:

Finding Shortest Path in Map: Various graph algorithms can be applied to find the shortest path between two locations on the map..

Network Routing and Optimization: Graphs model communication and transportation networks, such as the internet, road networks, and airline routes. Algorithms like Dijkstra’s algorithm and A* search are used for finding the shortest path, while minimum spanning tree algorithms optimize network connectivity.

Social Network Analysis: Social media platforms utilize graphs to represent connections between users. Graph algorithms help identify influential users, detect communities, and recommend friends or content.

Circuit Design and Verification: Electronic circuits are represented as graphs, with components as vertices and connections as edges. Graph algorithms verify circuit correctness, optimize circuit layouts, and automate circuit design processes.

Computer Networking: Graphs model network topologies, routing tables, and dependencies between network components. Graph algorithms are employed for tasks like routing packets, detecting network anomalies, and optimizing network performance.

Data Mining and Machine Learning: Graphs are used to represent data structures like decision trees, neural networks, and knowledge graphs. Graph-based algorithms are applied in recommendation systems, fraud detection, and pattern recognition.

Semantic Web and Knowledge Representation: Graphs are used to represent semantic relationships between concepts and entities in the Semantic Web. Graph-based languages like RDF and SPARQL enable querying and reasoning over linked data.

Software Engineering: Graphs model software dependencies, control flow, and data flow within software systems. Graph algorithms aid in software analysis, debugging, and optimization.

These applications highlight the versatility and importance of graph data structures in solving complex problems across various domains, making them a fundamental concept in computer science and beyond.

¶ Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online

All Tutorials in this playlist

Introduction to Linked List Data Structure with Practical Examples

Introduction to Queue Data Structure with Practical Examples

Introduction to Stack Data Structure with Practical Examples

Introduction to Set Data Structure with Practical Examples

Introduction to Map Data Structure with Practical Examples

Priority Queue Data Structure with Practical Examples

Introduction to Trie Data Structure with Practical Examples

Depth First Search - DFS Algorithm with Practical Examples

Breadth First Search - BFS Algorithm with Practical Examples

Single-Source Shortest Paths Algorithm - Dijkstra's Algorithm

Introduction to Tree Data Structure with Practical Examples

Introduction to Binary Search with Practical Examples

Popular tutorials, vue js 3 - complete advance crud example with vuex, vue-validate, pagination, searching and everything, laravel eloquent vs db query builder [performance and other statistics], laravel role permission management system full example with source code, start wordpress plugin development with react js easily in just few steps, laravel membership management full project demo with source codes, numerical methods for engineers ebook & solution download - download pdf, connect your react app with websocket to get real time data, #ajax with laravel api and more - learn laravel beyond the limit, laravel ecommerce complete web application with admin panel, what is seeder in laravel and why we need it.

• Artificial Intelligence (AI)
• Bash Scripting

Bootstrap CSS

• C Programming
• Code Editor
• Computer Engineering

Design Pattern in PHP

Design Patterns - Clean Code

• Git Commands

Interview Prepration

Java Programming

Laravel PHP Framework

Online Business

• Programming

React Native

Rust Programming

Tailwind CSS

Uncategorized

Windows Operating system

• Woocommerce

WordPress Development

• C-sharp programming
• Design pattern
• Mathematics
• Rust Programming Language
• Windows terminal
• WordPress Plugin Development

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons

Margin Size

• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

8.4: Graph Representations

• Last updated
• Save as PDF
• Page ID 49318

• Wikibooks - Data Structures

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

Adjacency Matrix Representation

An adjacency matrix is one of the two common ways to represent a graph. The adjacency matrix shows which nodes are adjacent to one another. Two nodes are adjacent if there is an edge connecting them. In the case of a directed graph, if node \(j\) is adjacent to node \(i\), there is an edge from \(i\) to \(j\). In other words, if \(j\) is adjacent to \(i\), you can get from \(i\) to \(j\) by traversing one edge. For a given graph with \(n\) nodes, the adjacency matrix will have dimensions of \(n\times n\). For an unweighted graph, the adjacency matrix will be populated with boolean values.

For any given node \(i\), you can determine its adjacent nodes by looking at row \(\left(i,\left[1..n\right]\right)\) of the adjacency matrix. A value of true at \(\left(i,j\right)\) indicates that there is an edge from node \(i\) to node \(j\), and false indicating no edge. In an undirected graph, the values of \(\left(i,j\right)\) and \(\left(j,i\right)\) will be equal. In a weighted graph, the boolean values will be replaced by the weight of the edge connecting the two nodes, with a special value that indicates the absence of an edge.

The memory use of an adjacency matrix is \(O(n^{2})\).

Adjacency List Representation

The adjacency list is another common representation of a graph. There are many ways to implement this adjacency representation. One way is to have the graph maintain a list of lists, in which the first list is a list of indices corresponding to each node in the graph. Each of these refer to another list that stores the index of each adjacent node to this one. It might also be useful to associate the weight of each link with the adjacent node in this list.

Example: An undirected graph contains four nodes 1, 2, 3 and 4. 1 is linked to 2 and 3. 2 is linked to 3. 3 is linked to 4.

3 - [1, 2, 4]

It might be useful to store the list of all the nodes in the graph in a hash table. The keys then would correspond to the indices of each node and the value would be a reference to the list of adjacent node indices.

Another implementation might require that each node keep a list of its adjacent nodes.

Learn Python practically and Get Certified .

Popular Tutorials

Popular examples, reference materials, learn python interactively, dsa introduction.

• What is an algorithm?

Data Structure and Types

• Why learn DSA?
• Asymptotic Notations
• Master Theorem
• Divide and Conquer Algorithm

Data Structures (I)

• Types of Queue
• Circular Queue
• Priority Queue

Data Structures (II)

• Linked List
• Linked List Operations
• Types of Linked List
• Heap Data Structure
• Fibonacci Heap
• Decrease Key and Delete Node Operations on a Fibonacci Heap

Tree based DSA (I)

Tree Data Structure

• Tree Traversal
• Binary Tree
• Full Binary Tree
• Perfect Binary Tree
• Complete Binary Tree
• Balanced Binary Tree
• Binary Search Tree

Tree based DSA (II)

• Insertion in a B-tree
• Deletion from a B-tree
• Insertion on a B+ Tree
• Deletion from a B+ Tree
• Red-Black Tree
• Red-Black Tree Insertion
• Red-Black Tree Deletion

Graph based DSA

• Graph Data Structure
• Spanning Tree
• Strongly Connected Components
• Adjacency Matrix
• Adjacency List
• DFS Algorithm
• Breadth-first Search
• Bellman Ford's Algorithm

Sorting and Searching Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Counting Sort
• Bucket Sort
• Linear Search
• Binary Search

Greedy Algorithms

• Greedy Algorithm
• Ford-Fulkerson Algorithm
• Dijkstra's Algorithm
• Kruskal's Algorithm
• Prim's Algorithm
• Huffman Coding
• Dynamic Programming
• Floyd-Warshall Algorithm
• Longest Common Sequence

Other Algorithms

• Backtracking Algorithm
• Rabin-Karp Algorithm

DSA Tutorials

Graph Data Stucture

Linked list Data Structure

• Stack Data Structure
• Queue Data Structure

Tree Traversal - inorder, preorder and postorder

• What are Data Structures?

Data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

Depending on your requirement and project, it is important to choose the right data structure for your project. For example, if you want to store data sequentially in the memory, then you can go for the Array data structure.

Note : Data structure and data types are slightly different. Data structure is the collection of data types arranged in a specific order.

• Types of Data Structure

Basically, data structures are divided into two categories:

• Linear data structure
• Non-linear data structure

Let's learn about each type in detail.

• Linear data structures

In linear data structures, the elements are arranged in sequence one after the other. Since elements are arranged in particular order, they are easy to implement.

However, when the complexity of the program increases, the linear data structures might not be the best choice because of operational complexities.

Popular linear data structures are:

1. Array Data Structure

In an array, elements in memory are arranged in continuous memory. All the elements of an array are of the same type. And, the type of elements that can be stored in the form of arrays is determined by the programming language.

To learn more, visit Java Array .

2. Stack Data Structure

In stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a stack will be removed first.

It works just like a pile of plates where the last plate kept on the pile will be removed first. To learn more, visit Stack Data Structure .

3. Queue Data Structure

Unlike stack, the queue data structure works in the FIFO principle where first element stored in the queue will be removed first.

It works just like a queue of people in the ticket counter where first person on the queue will get the ticket first. To learn more, visit Queue Data Structure .  

4. Linked List Data Structure

In linked list data structure, data elements are connected through a series of nodes. And, each node contains the data items and address to the next node.

To learn more, visit Linked List Data Structure .  

• Non linear data structures

Unlike linear data structures, elements in non-linear data structures are not in any sequence. Instead they are arranged in a hierarchical manner where one element will be connected to one or more elements.

Non-linear data structures are further divided into graph and tree based data structures.

1. Graph Data Structure

In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges.

To learn more, visit Graph Data Structure .

Popular Graph Based Data Structures:

• Spanning Tree and Minimum Spanning Tree

2. Trees Data Structure

Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure, there can only be one edge between two vertices.

To learn more, visit Tree Data Structure .

Popular Tree based Data Structure

• Linear Vs Non-linear Data Structures

Now that we know about linear and non-linear data structures, let's see the major differences between them.

• Why Data Structure?

Knowledge about data structures help you understand the working of each data structure. And, based on that you can select the right data structures for your project.

This helps you write memory and time efficient code.

To learn more about the importance of data structure, visit Why Learn Data Structure?

Table of Contents

Sorry about that.

Related Tutorials

DS & Algorithms

Tutorial Playlist

Data structure tutorial, arrays in data structures: a guide with examples, all you need to know about two-dimensional arrays, all you need to know about a linked list in a data structure, the complete guide to implement a singly linked list, the ultimate guide to implement a doubly linked list, the fundamentals for understanding circular linked list, the ultimate guide to understand the differences between stack and queue.

Implementing Stacks in Data Structures

Your One-Stop Solution for Stack Implementation Using Array

Your one-stop solution for queue implementation using array, your one-stop solution to learn depth-first search(dfs) algorithm from scratch, your one-stop solution for stack implementation using linked-list, the definitive guide to understand stack vs heap memory allocation, all you need to know about linear search algorithm, all you need to know about breadth-first search algorithm, a one-stop solution for using binary search trees in data structure.

The Best Tutorial to Understand Trees in Data Structure

A Complete Guide to Implement Binary Tree in Data Structure

A holistic look at using avl trees in data structures, all you need to know about tree traversal in data structure, the best and easiest way to understand an algorithm, the best guide you’ll ever need to understand b-tree in data structure, the best guide you'll ever need to understand spanning tree in data structure, a one-stop solution guide to understand data structure and algorithm complexity, your one-stop solution to understand shell sort algorithm, your one-stop solution to quick sort algorithm, the most useful guide to learn selection sort algorithm, everything you need to know about radix sort algorithm, everything you need to know about the counting sort algorithm, everything you need to know about the merge sort algorithm, insertion sort algorithm: one-stop solution that will help you understand insertion sort, everything you need to know about the bubble sort algorithm, the best guide you’ll ever need to understand bucket sort algorithm, your one-stop solution to understand recursive algorithm in programming, the definitive guide to understanding greedy algorithm, your one-stop solution to understand backtracking algorithm, the fundamentals of the bellman-ford algorithm, your one-stop solution for graphs in data structures, the best guide to understand and implement solutions for tower of hanoi puzzle, a simplified and complete guide to learn space and time complexity, all you need to know about the knapsack problem : your complete guide, the fibonacci series: mathematical and programming interpretation, the holistic look at longest common subsequence problem, the best article to understand what is dynamic programming, a guide to implement longest increasing subsequence using dynamic programming, a holistic guide to learn stop solution using dynamic programming, one stop solution to all the dynamic programming problems, understanding the fundamentals of binomial distribution, here’s all you need to know about minimum spanning tree in data structures, understanding the difference between array and linked list, the best article out there to understand the b+ tree in data structure.

A Comprehensive Look at Queue in Data Structure

Your One-Stop Solution to Understand Coin Change Problem

The best way to understand the matrix chain multiplication problem, your one-stop solution to learn floyd-warshall algorithm for using dynamic programming, the best tutorial you'll ever need for queue implementation using linked list, how to create a fake news detection system, all you need to know about how to create a react js portfolio project, a complete guide on the role of ai in healthcare, the best guide to learn how to make a wireframe: what is a wireframe, the best dsa projects for your resume, the best guide to understanding the working and implementation of selective repeat arq, one stop guide to understanding network layer in the osi model, the working and implementation of data-link layer in the osi model, top 5 best coding books you must read, the working and implementation of physical layer in the osi model, how to create an instagram clone using react, reactjs vs vuejs, what is graph in data structure & types of graph.

Lesson 38 of 68 By Ravikiran A S

Table of Contents

Graphs in data structures are non-linear data structures made up of a finite number of nodes or vertices and the edges that connect them. Graphs in data structures are used to address real-world problems in which it represents the problem area as a network like telephone networks, circuit networks, and social networks. For example, it can represent a single user as nodes or vertices in a telephone network, while the link between them via telephone represents edges.

Want a Top Software Development Job? Start Here!

What Are Graphs in Data Structure?

A graph is a non-linear kind of data structure made up of nodes or vertices and edges. The edges connect any two nodes in the graph, and the nodes are also known as vertices.

This graph has a set of vertices V= { 1,2,3,4,5} and a set of edges E= { (1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,50 }.

Now that you’ve learned about the definition of graphs in data structures, you will learn about their various types.

Types of Graphs in Data Structures

There are different types of graphs in data structures, each of which is detailed below.

1. Finite Graph

The graph G=(V, E) is called a finite graph if the number of vertices and edges in the graph is limited in number

2. Infinite Graph

The graph G=(V, E) is called a finite graph if the number of vertices and edges in the graph is interminable.

3. Trivial Graph

A graph G= (V, E) is trivial if it contains only a single vertex and no edges.

4. Simple Graph

If each pair of nodes or vertices in a graph G=(V, E) has only one edge, it is a simple graph. As a result, there is just one edge linking two vertices, depicting one-to-one interactions between two elements.

5. Multi Graph

If there are numerous edges between a pair of vertices in a graph G= (V, E), the graph is referred to as a multigraph. There are no self-loops in a Multigraph.

6. Null Graph

It's a reworked version of a trivial graph. If several vertices but no edges connect them, a graph G= (V, E) is a null graph. 

7. Complete Graph

If a graph G= (V, E) is also a simple graph, it is complete. Using the edges, with n number of vertices must be connected. It's also known as a full graph because each vertex's degree must be n-1.

8. Pseudo Graph

If a graph G= (V, E) contains a self-loop besides other edges, it is a pseudograph.

9. Regular Graph

If a graph G= (V, E) is a simple graph with the same degree at each vertex, it is a regular graph. As a result, every whole graph is a regular graph.

10. Weighted Graph

A graph G= (V, E) is called a labeled or weighted graph because each edge has a value or weight representing the cost of traversing that edge.

11. Directed Graph

A directed graph also referred to as a digraph, is a set of nodes connected by edges, each with a direction.

12. Undirected Graph

An undirected graph comprises a set of nodes and links connecting them. The order of the two connected vertices is irrelevant and has no direction. You can form an undirected graph with a finite number of vertices and edges.

13. Connected Graph

If there is a path between one vertex of a graph data structure and any other vertex, the graph is connected.

14. Disconnected Graph

When there is no edge linking the vertices, you refer to the null graph as a disconnected graph.

15. Cyclic Graph

If a graph contains at least one graph cycle, it is considered to be cyclic.

16. Acyclic Graph

When there are no cycles in a graph, it is called an acyclic graph.

17. Directed Acyclic Graph

It's also known as a directed acyclic graph (DAG), and it's a graph with directed edges but no cycle. It represents the edges using an ordered pair of vertices since it directs the vertices and stores some data.

18. Subgraph

The vertices and edges of a graph that are subsets of another graph are known as a subgraph.

After you learn about the many types of graphs in graphs in data structures, you will move on to graph terminologies.

Terminologies of Graphs in Data Structures

Following are the basic terminologies of graphs in data structures:

• An edge is one of the two primary units used to form graphs. Each edge has two ends, which are vertices to which it is attached.
• If two vertices are endpoints of the same edge, they are adjacent.
• A vertex's outgoing edges are directed edges that point to the origin.
• A vertex's incoming edges are directed edges that point to the vertex's destination.
• The total number of edges occurring to a vertex in a graph is its degree.
• The out-degree of a vertex in a directed graph is the total number of outgoing edges, whereas the in-degree is the total number of incoming edges.
• A vertex with an in-degree of zero is referred to as a source vertex, while one with an out-degree of zero is known as sink vertex.
• An isolated vertex is a zero-degree vertex that is not an edge's endpoint.
• A path is a set of alternating vertices and edges, with each vertex connected by an edge.
• The path that starts and finishes at the same vertex is known as a cycle.
• A path with unique vertices is called a simple path.
• For each pair of vertices x, y, a graph is strongly connected if it contains a directed path from x to y and a directed path from y to x.
•  A directed graph is weakly connected if all of its directed edges are replaced with undirected edges, resulting in a connected graph. A weakly linked graph's vertices have at least one out-degree or in-degree.
• A tree is a connected forest. The primary form of the tree is called a rooted tree, which is a free tree.
• A spanning subgraph that is also a tree is known as a spanning tree.
• A connected component is the unconnected graph's most connected subgraph.
• A bridge, which is an edge of removal, would sever the graph.
• Forest is a graph without a cycle.

Following that, you will look at the graph representation in this data structures tutorial.

Representation of Graphs in Data Structures

Graphs in data structures are used to represent the relationships between objects. Every graph consists of a set of points known as vertices or nodes connected by lines known as edges. The vertices in a network represent entities.

The most frequent graph representations are the two that follow:

• Adjacency matrix
• Adjacency list

You’ll look at these two representations of graphs in data structures in more detail:

Adjacency Matrix

• A sequential representation is an adjacency matrix.
• It's used to show which nodes are next to one another. I.e., is there any connection between nodes in a graph?
• You create an MXM matrix G for this representation. If an edge exists between vertex a and vertex b, the corresponding element of G, gi,j = 1, otherwise gi,j = 0.
• If there is a weighted graph, you can record the edge's weight instead of 1s and 0s.

Undirected Graph Representation

Directed Graph Representation

Weighted Undirected Graph Representation 

Weight or cost is indicated at the graph's edge, a weighted graph representing these values in the matrix.

Adjacency List

• A linked representation is an adjacency list.
• You keep a list of neighbors for each vertex in the graph in this representation. It means that each vertex in the graph has a list of its neighboring vertices.
• You have an arra of vertices indexed by the vertex number, and the corresponding array member for each vertex x points to a singly linked list of x's neighbors.

Weighted Undirected Graph Representation Using Linked-List

Weighted Undirected Graph Representation Using an Array

You will now see which all operations are conducted in graphs data structure after understanding the representation of graphs in the data structure.

Also Read: Linked List in A Data Structure

Operations on Graphs in Data Structures

The operations you perform on the graphs in data structures are listed below:

• Creating graphs
• Insert vertex
• Delete vertex
• Insert edge 
• Delete edge

You will go over each operation in detail one by one:

Creating Graphs

There are two techniques to make a graph:

1. Adjacency Matrix

The adjacency matrix of a simple labeled graph, also known as the connection matrix, is a matrix with rows and columns labeled by graph vertices and a 1 or 0 in position depending on whether they are adjacent or not.

2. Adjacency List

A finite graph is represented by an adjacency list, which is a collection of unordered lists. Each unordered list describes the set of neighbors of a particular vertex in the graph within an adjacency list.

Insert Vertex

When you add a vertex that after introducing one or more vertices or nodes, the graph's size grows by one, increasing the matrix's size by one at the row and column levels.

Delete Vertex

• Deleting a vertex refers to removing a specific node or vertex from a graph that has been saved.
• If a removed node appears in the graph, the matrix returns that node. If a deleted node does not appear in the graph, the matrix returns the node not available.

Insert Edge

Connecting two provided vertices can be used to add an edge to a graph.

Delete Edge

The connection between the vertices or nodes can be removed to delete an edge.

The types of graph traversal algorithms will be discussed next in the graphs in this data structures tutorial.

Graph Traversal Algorithm 

The process of visiting or updating each vertex in a graph is known as graph traversal. The sequence in which they visit the vertices is used to classify such traversals. Graph traversal is a subset of tree traversal.

There are two techniques to implement a graph traversal algorithm:

• Breadth-first search
• Depth-first search

Breadth-First Search or BFS

BFS is a search technique for finding a node in a graph data structure that meets a set of criteria. 

• It begins at the root of the graph and investigates all nodes at the current depth level before moving on to nodes at the next depth level.
• To maintain track of the child nodes that have been encountered but not yet inspected, more memory, generally you require a queue.

Algorithm of breadth-first search

Step 1: Consider the graph you want to navigate.

Step 2: Select any vertex in your graph, say v1, from which you want to traverse the graph.

Step 3: Examine any two data structures for traversing the graph.

• Visited array (size of the graph)
• Queue data structure

Step 4: Starting from the vertex, you will add to the visited array, and afterward, you will v1's adjacent vertices to the queue data structure.

Step 5: Now, using the FIFO concept, you must remove the element from the queue, put it into the visited array, and then return to the queue to add the adjacent vertices of the removed element.

Step 6: Repeat step 5 until the queue is not empty and no vertex is left to be visited.

Depth-First Search or DFS

DFS is a search technique for finding a node in a graph data structure that meets a set of criteria. 

• The depth-first search (DFS) algorithm traverses or explores data structures such as trees and graphs. The DFS algorithm begins at the root node and examines each branch as far as feasible before backtracking.
• To maintain track of the child nodes that have been encountered but not yet inspected, more memory, generally a stack , is required.

Algorithm of depth-first search

Step 2: Select any vertex in our graph, say v1, from which you want to begin traversing the graph.

• Stack data structure

Step 4: Insert v1 into the array's first block and push all the adjacent nodes or vertices of vertex v1 into the stack.

Step 5: Now, using the FIFO principle, pop the topmost element and put it into the visited array, pushing all of the popped element's nearby nodes into it.

Step 6: If the topmost element of the stack is already present in the array, discard it instead of inserting it into the visited array.

Step 7: Repeat step 6 until the stack data structure isn't empty.                       

You will now look at applications of graph data structures after understanding the graph traversal algorithm in this tutorial.

Application of Graphs in Data Structures

Following  are some applications of graphs in data structures:

• Graphs are used in computer science to depict the flow of computation.
• Users on Facebook are referred to as vertices, and if they are friends, there is an edge connecting them. The Friend Suggestion system on Facebook is based on graph theory.
• You come across the Resource Allocation Graph in the Operating System, where each process and resource are regarded vertically. Edges are drawn from resources to assigned functions or from the requesting process to the desired resource. A stalemate will develop if this results in the establishment of a cycle.
• Web pages are referred to as vertices on the World Wide Web. Suppose there is a link from page A to page B that can represent an edge. This application is an illustration of a directed graph.
• Graph transformation systems manipulate graphs in memory using rules. Graph databases store and query graph-structured data in a transaction-safe, permanent manner.

Finally, in this tutorial, you’ll look at the code for the graphs in data structures       

Code Implementation of Graphs in Data Structures

You learned what a graph data structure is and the many types of graph data structures in this “graphs in data structures” tutorial. Following that, you learned about the graph traversal method, which includes the breadth-first and depth-first search algorithms, as well as several graph data structure applications.

"Breadth-first search or BFS "will be your next topic, where you will learn about the breadth-first search algorithm and how to traverse tree and graph data structure using BFS. If you want to learn more about data structures and programming languages , check out simplilearn's Post Graduate Program in Full Stack Web Development Automation Testing Masters might just be what you need. The bootcamp is offered in collaboration with Caltech CTME and will provide you with the work-ready software development skills , industry credentials and global recognition you need to succeed now.

If you have any doubts regarding the "graphs in data structures "article, please feel free to ask in the comment section below. We will be happy to resolve your problems as soon as possible. Until then, stay tuned with Simplilearn’s channel and keep learning.

1. Where are graph data structures used in real life?

You most likely utilise social networking platforms such as Facebook, LinkedIn, Instagram, and others. A wonderful example of a graph in usage is social media. Graphs are used in social media to hold information about each user. Every user is a node in this case, just like in Graph. Similarly, Google Maps is another application that makes use of graphs. In the case of Google Maps, each place is referred to as a node, and the roads that connect them are referred to as edges.

2. What are the different types of graphs in data structure?

A graph is a non-linear data structure composed of nodes and edges. They come in a variety of forms. Namely, they are Finite Graphs, Infinite Graphs, Trivial Graphs, Simple Graphs, Multi Graphs, Null Graphs, Complete Graphs, Pseudo Graphs, Regular Graphs, Labeled Graphs, Digraph Graphs, Subgraphs, Connected or Disconnected Graphs, and Cyclic Graphs.

3. How many types of graphs are there in data structure?

They are of 14 to 15 types. However, the most commonly used graph is the finite graph.

4. What is a complete graph in data structure?

A graph is considered to be complete if there is an edge between every pair of vertices in the graph. In other words, all of the graph's vertices are connected to the remainder of the graph's vertices. A full graph of 'n' vertices has precisely nC2 edges and is written as Kn.

5. What is a directed acyclic graph?

A directed acyclic graph (DAG) is a graph that is directed and has no cycles linking the other edges in computer science and mathematics. This indicates that traversing the complete graph from one edge is impossible. The edges of the directed graph can only move in one direction. The graph is a topological sorting in which each node has a specific order.

6. What is graph in data structure?

A graph is a type of non-linear data structure made up of vertices and edges. Vertices are also known as nodes, while edges are lines or arcs that link any two nodes in the network. In more technical terms, a graph comprises vertices (V) and edges (E). The graph is represented as G(E, V).

7. What is graph in data structure and its application?

A graph is a non-linear data structure made up of vertices (or nodes) linked by edges (or arcs), which can be directed or undirected. Graphs are used in computer science to depict the flow of computation.

8. How are graphs useful when interpreting data?

Graphs are a popular way to visually depict data connections. A graph's objective is to convey too many or intricate facts to be fully expressed in words and in less space. However, do not use graphs for little quantities of data that may be expressed in a phrase.

Find our Full Stack Java Developer Online Bootcamp in top cities:

About the author.

Ravikiran A S works with Simplilearn as a Research Analyst. He an enthusiastic geek always in the hunt to learn the latest technologies. He is proficient with Java Programming Language, Big Data, and powerful Big Data Frameworks like Apache Hadoop and Apache Spark.

Recommended Programs

Full Stack Java Developer

Full Stack Web Developer - MEAN Stack

Automation Testing Masters Program

*Lifetime access to high-quality, self-paced e-learning content.

Recommended Resources

Big Data Career Guide: A Comprehensive Playbook to Becoming a Big Data Engineer

What is Data Structure : Types, Classifications, and Applications

Data Science Career Guide: A Comprehensive Playbook To Becoming A Data Scientist

• PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.

Data Structure Visualizations

• Known Bugs /     Feature Requests
• Java Version
• Flash Version
• Create Your Own /     Source Code
• Stack: Array Implementation
• Stack: Linked List Implementation
• Queues: Array Implementation
• Queues: Linked List Implementation
• Lists: Array Implementation (available in java version)
• Lists: Linked List Implementation (available in java version)
• Reversing a String
• N-Queens Problem
• Binary and Linear Search (of sorted list)
• Binary Search Trees
• AVL Trees (Balanced binary search trees)
• Red-Black Trees
• Splay Trees
• Open Hash Tables (Closed Addressing)
• Closed Hash Tables (Open Addressing)
• Closed Hash Tables, using buckets
• Trie (Prefix Tree, 26-ary Tree)
• Radix Tree (Compact Trie)
• Ternary Search Tree (Trie with BST of children)
• Bubble Sort
• Selection Sort
• Insertion Sort
• Bucket Sort
• Counting Sort
• Heap-like Data Structures
• Binomial Queues
• Fibonacci Heaps
• Leftist Heaps
• Graph Algorithms
• Breadth-First Search
• Depth-First Search
• Connected Components
• Dijkstra's Shortest Path
• Prim's Minimum Cost Spanning Tree
• Topological Sort (Using Indegree array)
• Topological Sort (Using DFS)
• Floyd-Warshall (all pairs shortest paths)
• Kruskal Minimum Cost Spanning Tree Algorithm
• Dynamic Programming
• Calculating nth Fibonacci number
• Making Change
• Longest Common Subsequence
• Geometric Algorithms
• 2D Rotation and Scale Matrices
• 2D Rotation and Translation Matrices
• 2D Changing Coordinate Systems
• 3D Rotation and Scale Matrices
• 3D Changing Coordinate Systems
• Disjoint Sets
• Huffman Coding (available in java version)

• Data Structure
• Design Pattern

DS Tutorial

Ds linked list, ds searching, differences.

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

What Are Data Structures & Its Types?

Data structures are the foundational elements in computer science that are critical for the efficient organization, storage, and management of data within software applications. They provide a systematic approach to data handling, facilitating various tasks like data retrieval and complex algorithmic operations. By understanding the different types of data structures, you can enhance the performance, scalability, and reliability of programs.

In this article, you will learn about data structures, types of data structures, their key features, and operations.

What Is a Data Structure?

A data structure is a specific way of storing, organizing, and managing data in a computer to enable efficient access and modification of data. It not only organizes data but also defines the relationships between data elements and the operations that can be performed on them.

Data structures are crucial for implementing efficient algorithms and helping manage and process data in different programming languages. They are comprised of basic and advanced types tailored to various applications.

Key Features of Data Structures

Here are some key features of data structures:

• Organized Data: Data structure provides a systematic way to arrange data, helping define the relationships and interactions between different data elements. This feature also enables efficient data storage, retrieval, and manipulation.
• ‍ Memory Management: Data structures efficiently handle memory allocation and deallocation, ensuring optimal use of memory resources. Effective memory management minimizes memory fragmentation and prevents memory leaks, enhancing overall system stability.
• ‍ Scalability: Data structures are designed to scale effectively for growing data volumes. This scalability helps maintain the overall performance and functionality as the size of the data increases.
• ‍ Complexity Analysis: Complexity analysis involves evaluating the time and space requirements of operations performed on data structures to understand how they scale with varying sizes of input data.

What Is the Importance of Data Structures?

Data structures aren’t just about storing data but are also essential for optimizing the speed and performance of software applications. Here are some of the benefits highlighting the significance of using data structures effectively:

• Data structures can store diverse data types, from simple text and numbers to complex data such as images, database records, and software programs.
• A data structure object can represent and access all data, and one single object can hold different types of data.
• Data structures provide reusability of existing structures, reducing time and effort in designing and implementing software applications solutions.
• Data structure abstraction allows developers to focus on the high-level functionality of their applications without having to stress the complexities of the underlying data operations.
• Using data structures can help developers save time while performing data storage, retrieval, and processing operations. This is particularly essential when dealing with large data volumes.

What Are the Operations on Data Structures?

Data structures support various operations for efficiently storing, accessing, and manipulating data. Here are some common operations associated with data structures:

• Search: It helps to find the location of a particular element within the data structure. You can perform search operations on data structures such as linked lists, arrays, trees, graphs, etc.
• Insertion: The insertion operation allows you to add one or more elements to a data structure. You can insert the elements at the beginning, end, or any specific index.
• Deletion: It involves removing or deleting an existing element from the data structure. You can delete an element based on a particular index or value.
• Traversal: Traversal lets you visit and process all elements in a data structure in a specific order. You can also examine or modify each element sequentially.
• Sorting: Sorting allows you to rearrange the elements in a data structure, making it easier for search and retrieval. By sorting the data structure, the time to search for a particular item is reduced.
• Update: This includes modifying or updating the value of an existing element within the data structure. It could be changing the value of a data element stored at a specific location or more complex modifications.

What Are the Types of Data Structures?

Data structures are broadly divided into different types as follows:

Primitive Data Structures

Primitive data structures are pre-defined, basic types directly interacting with the system architecture. Some primitive data structures are:

• Integer : An integer stores whole numbers that can be positive, negative, or zero. Depending on the programming language, they may have varying sizes. You can perform all the arithmetic operations using integer data types. ‍
• Float : Float represents decimal numbers and fractional values. It can store real numbers and may have single-precision or double-precision, depending on the programming language. ‍
• Character : A character data structure stores single characters like letters, digits, punctuation marks, and special characters.
• ‍ Boolean : Boolean stores logical values that are either true or false.

Non-Primitive Data Structures

Non-primitive data structures are more complex forms derived from primitive types. They facilitate complex operations like searching, sorting, traversal, etc., and are further classified into two types:

Linear Data Structures

Linear data structures store elements sequentially; each element has a unique predecessor and successor (except for the first and last elements).

An array is a collection of data items of the same type stored together in adjacent memory locations. The data items are termed “element” and each element is accessed using the index value. The size of the array corresponds to the total number of elements in the array.

Indexing in an array starts at 0 for the first element and sequentially increments up to the array size minus one. For example, in an array of 5 elements, the indices range from 0 to 4, as shown in the figure below.

Arrays are used in algorithms that try to access elements randomly. They effectively store the lists of elements so that you can perform mathematical operations and image processing.

A stack works on the Last In, First Out (LIFO) principle, exclusively allowing data insertion and retrieval from one end. The stack's most recently added element is the first to be removed. The primary operations of a stack are push and pop. The push operation adds a new element to the top of the stack. Conversely, the pop operation deletes the topmost element of the stack.

Here are some other basic stack operations :

• Peek : View the top element without removing it from the stack. ‍
• IsEmpty : Verifying whether the stack is empty. ‍
• IsFull : Verifying whether the stack has reached the maximum capacity.

Stacks are highly advantageous in data management scenarios where the sequence of operations is more significant.

A queue works on the first-in-first-out (FIFO) principle. Unlike in a stack, elements in a queue can be inserted from the rear end and removed from the front end.

The queue processes the data in the order they were received. An example of queues is job scheduling in operating systems. Queues are used to schedule and prioritize jobs waiting to be executed by the system. Then, jobs are processed in the order specified at the time of arrival.

Here are some basic operations performed on a queue:

• Enqueue : Used to insert an element at the rear end of the queue. ‍
• Dequeue : Used to delete an element from the front end of the queue. ‍
• Peek : Returns the element, which is pointed by the front pointer in the queue. ‍
• Queue Overflow : The overflow condition is shown when the queue is full. ‍
• Queue Underflow : The underflow condition is shown when the queue is empty.

Linked List

A linked list is type of linear data structure in which elements are linked using pointers instead of being stored in adjacent memory locations, as shown below.

Linked lists can grow dynamically, making them suitable in scenarios where the data size is unknown.

Non-Linear Data Structures

In non-linear data structures, the data elements are not stored sequentially but in a hierarchical manner. This makes it difficult to traverse all elements in a single run. Non-linear data structures are memory efficient, sharing nodes among multiple elements. A non-linear data structure is divided into two types:

A tree data structure represents a hierarchical model that does not store data sequentially. Instead, it organizes elements in a tree-like structure with multiple levels.

In the above tree structure, each node is labeled with a name.

• Root Node : It is the topmost node in the tree data structure with no parent. In the above example, node A is the root.
• Parent Node : The parent node is any node with child nodes directly under it.
• Child Node : If the node descends from a parent node, it is termed a child node.
• Siblings : The sibling nodes are those with the same parent.
• Leaf or External Node : Leaf nodes have no child nodes. In the above example, F is a leaf node.
• Internal Node : A node with at least one child node is termed an internal node.
• Ancestor Nodes : A node's ancestors refer to any nodes preceding it on the path to the root. For example, nodes A and B are ancestors of node E.
• Descendants : These are nodes accessible by traversing downwards from a given node in a tree. In the above data structure, nodes D and I are the descendants of node B.
• Subtree : It refers to a portion of a tree that includes a node, also referred to as the root of the subtree, and all of its descendants. For example, if node B is the root of a subtree, then nodes D, H, and I comprise the descendants of the subtree.

A graph data structure is a collection of vertices (nodes) and edges that connect pairs of vertices. It is used to model relationships between objects and is fundamental in various computer science applications, including network analysis, social network modeling, and routing algorithms.

Graph components include:

• Vertices: Vertices, also called nodes, are a graph's basic components. Each vertex or node may be assigned a label or remain unlabeled.
• ‍ Edges: Edges serve as connections between two vertices in the graph. Edges connect any two vertices in a graph, and similar to vertices, edges may be labeled or remain unlabeled. In a directed graph, they can be represented as ordered pairs of vertices, whereas in undirected graphs, edges indicate a bidirectional relationship.

Applications of Data Structures

Data structures are a fundamental tool in computer science, designed to store, retrieve, and manipulate data in software applications. They can solve problems and be applied in various fields. Let us look at some of the practical applications of data structures:

• Dynamic Programming: Data structures like arrays are extensively used in dynamic programming to store the results and optimize the algorithms. For example, the matrix chain multiplication algorithm relies on arrays to efficiently store and retrieve data. ‍
• Job Scheduling: Data structures like queues are used in task management systems for job scheduling. The first-in-first-out (FIFO) functionality of queues enables the orderly execution of jobs.
• ‍ Bioinformatics: Data structures like graphs are used to model and analyze complex biological networks, such as gene regulatory networks and protein-protein interaction networks.

How to Decide Which Data Structure to Use?

Choosing the right data structure depends on various factors. Here are some key considerations to help you select the appropriate data structure:

Understand Your Data

The type of data you're dealing with can influence the data structure you choose. For example, a tree-based data structure may be more suitable if your data has a hierarchical structure. Conversely, an array data structure could be the better choice if you have simple data that needs to be accessed randomly.

Consider the Operations

Next, consider the operations you will perform on the data. Different data structures optimize different operations. For example, linked lists are efficient for frequent insertion and deletion, and binary trees are ideal for searching and sorting.

Analyze Time and Space Complexity

Consider the time and space complexity of the data structure. The time complexity refers to the efficiency of operations in terms of the input size, while the space complexity refers to the amount of memory required. Choose a data structure that meets your application performance requirements.

For example, an array is great for quick access to elements at random positions but not ideal for frequent insertions or deletions. Contrarily, a linked list is more efficient for insertions and deletions but less efficient for random access.

Available Libraries

Consider the accessibility of libraries for the specific data structure you choose. If your programming language provides built-in libraries for that particular data structure, it can make the execution and maintenance of your code more manageable.

libraries for that particular data structure, it can make the execution and maintenance of your code more manageable.

Unlock the Power of Data Structures with Airbyte

Now that you have an idea of data structures, operations, and types, it’s essential to consolidate data on a platform to perform any high-level transformations on the data. This is where Airbyte can help you.

Airbyte is a prominent data integration platform featuring connectors capable of ingesting any type of data structure from diverse sources. Irrespective of the format, Airbyte facilitates integration by empowering you to construct no-code data pipelines effortlessly. It offers more than 350 pre-built connectors to connect multiple sources and destinations. In addition to its pre-built connectors, Airbyte’s Connector Development Kit (CDK) empowers you to set up custom connectors. Moreover, Airbyte’s change data capture (CDC) capabilities facilitate efficient data migration by ensuring seamless synchronization of updated information with your designated target system.

Learn more about the types of data used in Airbyte here .

Data structures provide a framework for efficiently organizing, storing, and manipulating data. Different types of data structures exist, each with unique characteristics and applications. From arrays and linked lists to trees and graphs, each offers specific advantages. By selecting and implementing appropriate data structures, you can optimize the application's performance and maintenance. 

About the Author

Table of contents, get your data syncing in minutes, join our newsletter to get all the insights on the data stack., integrate with 300+ apps using airbyte, integrate and move data across 300+ apps using airbyte., related posts.

Help | Advanced Search

Computer Science > Information Retrieval

Title: learning structure and knowledge aware representation with large language models for concept recommendation.

Abstract: Concept recommendation aims to suggest the next concept for learners to study based on their knowledge states and the human knowledge system. While knowledge states can be predicted using knowledge tracing models, previous approaches have not effectively integrated the human knowledge system into the process of designing these educational models. In the era of rapidly evolving Large Language Models (LLMs), many fields have begun using LLMs to generate and encode text, introducing external knowledge. However, integrating LLMs into concept recommendation presents two urgent challenges: 1) How to construct text for concepts that effectively incorporate the human knowledge system? 2) How to adapt non-smooth, anisotropic text encodings effectively for concept recommendation? In this paper, we propose a novel Structure and Knowledge Aware Representation learning framework for concept Recommendation (SKarREC). We leverage factual knowledge from LLMs as well as the precedence and succession relationships between concepts obtained from the knowledge graph to construct textual representations of concepts. Furthermore, we propose a graph-based adapter to adapt anisotropic text embeddings to the concept recommendation task. This adapter is pre-trained through contrastive learning on the knowledge graph to get a smooth and structure-aware concept representation. Then, it's fine-tuned through the recommendation task, forming a text-to-knowledge-to-recommendation adaptation pipeline, which effectively constructs a structure and knowledge-aware concept representation. Our method does a better job than previous adapters in transforming text encodings for application in concept recommendation. Extensive experiments on real-world datasets demonstrate the effectiveness of the proposed approach.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Not all data are created equal; some are structured, but most of them are unstructured. Structured and unstructured data are sourced, collected and scaled in different ways and each one resides in a different type of database.

In this article, we will take a deep dive into both types so that you can get the most out of your data.

Structured data—typically categorized as quantitative data—is highly organized and easily decipherable by  machine learning algorithms .  Developed by IBM® in 1974 , structured query language (SQL) is the programming language used to manage structured data. By using a  relational (SQL) database , business users can quickly input, search and manipulate structured data.

Examples of structured data include dates, names, addresses, credit card numbers, among others. Their benefits are tied to ease of use and access, while liabilities revolve around data inflexibility:

• Easily used by machine learning (ML) algorithms:  The specific and organized architecture of structured data eases the manipulation and querying of ML data.
• Easily used by business users:  Structured data do not require an in-depth understanding of different types of data and how they function. With a basic understanding of the topic relative to the data, users can easily access and interpret the data.
• Accessible by more tools:  Since structured data predates unstructured data, there are more tools available for using and analyzing structured data.
• Limited usage:  Data with a predefined structure can only be used for its intended purpose, which limits its flexibility and usability.
• Limited storage options:  Structured data are usually stored in data storage systems with rigid schemas (for example, “ data warehouses ”). Therefore, changes in data requirements necessitate an update of all structured data, which leads to a massive expenditure of time and resources.
• OLAP :  Performs high-speed, multidimensional data analysis from unified, centralized data stores.
• SQLite : (link resides outside ibm.com)  Implements a self-contained,  serverless , zero-configuration, transactional relational database engine.
• MySQL :  Embeds data into mass-deployed software, particularly mission-critical, heavy-load production system.
• PostgreSQL :  Supports SQL and JSON querying as well as high-tier programming languages (C/C+, Java,  Python , among others.).
• Customer relationship management (CRM):  CRM software runs structured data through analytical tools to create datasets that reveal customer behavior patterns and trends.
• Online booking:  Hotel and ticket reservation data (for example, dates, prices, destinations, among others.) fits the “rows and columns” format indicative of the pre-defined data model.
• Accounting:  Accounting firms or departments use structured data to process and record financial transactions.

Unstructured data, typically categorized as qualitative data, cannot be processed and analyzed through conventional data tools and methods. Since unstructured data does not have a predefined data model, it is best managed in  non-relational (NoSQL) databases . Another way to manage unstructured data is to use  data lakes  to preserve it in raw form.

The importance of unstructured data is rapidly increasing.  Recent projections  (link resides outside ibm.com) indicate that unstructured data is over 80% of all enterprise data, while 95% of businesses prioritize unstructured data management.

Examples of unstructured data include text, mobile activity, social media posts, Internet of Things (IoT) sensor data, among others. Their benefits involve advantages in format, speed and storage, while liabilities revolve around expertise and available resources:

• Native format:  Unstructured data, stored in its native format, remains undefined until needed. Its adaptability increases file formats in the database, which widens the data pool and enables data scientists to prepare and analyze only the data they need.
• Fast accumulation rates:  Since there is no need to predefine the data, it can be collected quickly and easily.
• Data lake storage:  Allows for massive storage and pay-as-you-use pricing, which cuts costs and eases scalability.
• Requires expertise:  Due to its undefined or non-formatted nature, data science expertise is required to prepare and analyze unstructured data. This is beneficial to data analysts but alienates unspecialized business users who might not fully understand specialized data topics or how to utilize their data.
• Specialized tools:  Specialized tools are required to manipulate unstructured data, which limits product choices for data managers.
• MongoDB :  Uses flexible documents to process data for cross-platform applications and services.
• DynamoDB :  (link resides outside ibm.com) Delivers single-digit millisecond performance at any scale through built-in security, in-memory caching and backup and restore.
• Hadoop :  Provides distributed processing of large data sets using simple programming models and no formatting requirements.
• Azure :  Enables agile cloud computing for creating and managing apps through Microsoft’s data centers.
• Data mining :  Enables businesses to use unstructured data to identify consumer behavior, product sentiment and purchasing patterns to better accommodate their customer base.
• Predictive data analytics :  Alert businesses of important activity ahead of time so they can properly plan and accordingly adjust to significant market shifts.
• Chatbots :  Perform text analysis to route customer questions to the appropriate answer sources.

While structured (quantitative) data gives a “birds-eye view” of customers, unstructured (qualitative) data provides a deeper understanding of customer behavior and intent. Let’s explore some of the key areas of difference and their implications:

• Sources:  Structured data is sourced from GPS sensors, online forms, network logs, web server logs,  OLTP systems , among others; whereas unstructured data sources include email messages, word-processing documents, PDF files, and others.
• Forms:  Structured data consists of numbers and values, whereas unstructured data consists of sensors, text files, audio and video files, among others.
• Models:  Structured data has a predefined data model and is formatted to a set data structure before being placed in data storage (for example, schema-on-write), whereas unstructured data is stored in its native format and not processed until it is used (for example, schema-on-read).
• Storage:  Structured data is stored in tabular formats (for example, excel sheets or SQL databases) that require less storage space. It can be stored in data warehouses, which makes it highly scalable. Unstructured data, on the other hand, is stored as media files or NoSQL databases, which require more space. It can be stored in data lakes, which makes it difficult to scale.
• Uses:  Structured data is used in machine learning (ML) and drives its algorithms, whereas unstructured data is used in  natural language processing  (NLP) and text mining.

Semi-structured data (for example, JSON, CSV, XML) is the “bridge” between structured and unstructured data. It does not have a predefined data model and is more complex than structured data, yet easier to store than unstructured data.

Semi-structured data uses “metadata” (for example, tags and semantic markers) to identify specific data characteristics and scale data into records and preset fields. Metadata ultimately enables semi-structured data to be better cataloged, searched and analyzed than unstructured data.

• Example of metadata usage:  An online article displays a headline, a snippet, a featured image, image alt-text, slug, among others, which helps differentiate one piece of web content from similar pieces.
• Example of semi-structured data vs. structured data:  A tab-delimited file containing customer data versus a database containing CRM tables.
• Example of semi-structured data vs. unstructured data:  A tab-delimited file versus a list of comments from a customer’s Instagram.

Recent developments in  artificial intelligence  (AI) and machine learning (ML) are driving the future wave of data, which is enhancing business intelligence and advancing industrial innovation. In particular, the data formats and models that are covered in this article are helping business users to do the following:

• Analyze digital communications for compliance:  Pattern recognition and email threading analysis software that can search email and chat data for potential noncompliance.
• Track high-volume customer conversations in social media:  Text analytics and sentiment analysis that enables monitoring of marketing campaign results and identifying online threats.
• Gain new marketing intelligence:  ML analytics tools that can quickly cover massive amounts of data to help businesses analyze customer behavior.

Furthermore, smart and efficient usage of data formats and models can help you with the following:

• Understand customer needs at a deeper level to better serve them
• Create more focused and targeted marketing campaigns
• Track current metrics and create new ones
• Create better product opportunities and offerings
• Reduce operational costs

Whether you are a seasoned data expert or a novice business owner, being able to handle all forms of data is conducive to your success. By using structured, semi-structured and unstructured data options, you can perform optimal data management that will ultimately benefit your mission.

Get the latest tech insights and expert thought leadership in your inbox.

To better understand data storage options for whatever kind of data best serves you, check out IBM Cloud Databases

Get our newsletters and topic updates that deliver the latest thought leadership and insights on emerging trends.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Stack Data Structure

• What is Stack? A Complete Tutorial
• Applications, Advantages and Disadvantages of Stack
• Implement a stack using singly linked list
• Introduction to Monotonic Stack - Data Structure and Algorithm Tutorials
• Difference Between Stack and Queue Data Structures

Stack implementation in different language

• Stack in C++ STL
• Stack Class in Java
• Stack in Python
• C# Stack with Examples
• Implementation of Stack in JavaScript
• Stack in Scala

Some questions related to Stack implementation

• Design and Implement Special Stack Data Structure | Added Space Optimized Version
• Implement two Stacks in an Array
• Implement Stack using Queues
• How to efficiently implement k stacks in a single array?
• Design a stack that supports getMin() in O(1) time and O(1) extra space
• Implement a stack using single queue
• How to implement stack using priority queue or heap?
• Create a customized data structure which evaluates functions in O(1)
• Implement Stack and Queue using Deque

Easy problems on Stack

• Convert Infix expression to Postfix expression
• Prefix to Infix Conversion
• Prefix to Postfix Conversion
• Postfix to Prefix Conversion
• Postfix to Infix
• Convert Infix To Prefix Notation
• Check for Balanced Brackets in an expression (well-formedness)
• Arithmetic Expression Evaluation
• Evaluation of Postfix Expression
• How to Reverse a Stack using Recursion
• Reverse individual words
• How to Reverse a String using Stack
• Reversing a Queue

Intermediate problems on Stack

• How to create mergeable stack?
• The Stock Span Problem
• Next Greater Element (NGE) for every element in given Array
• Next Greater Frequency Element
• Maximum product of indexes of next greater on left and right
• Iterative Tower of Hanoi
• Sort a stack using a temporary stack
• Reverse a stack without using extra space in O(n)
• Delete middle element of a stack
• Check if a queue can be sorted into another queue using a stack
• Check if an array is stack sortable
• Largest Rectangular Area in a Histogram using Stack
• Find maximum of minimum for every window size in a given array
• Find index of closing bracket for a given opening bracket in an expression
• Find maximum difference between nearest left and right smaller elements
• Delete consecutive same words in a sequence
• Check mirror in n-ary tree
• Reverse a number using stack
• Reversing the first K elements of a Queue

Hard problems on Stack

• The Celebrity Problem
• Print next greater number of Q queries
• Iterative Postorder Traversal | Set 2 (Using One Stack)
• Print ancestors of a given binary tree node without recursion
• Length of the longest valid substring
• Expression contains redundant bracket or not
• Find if an expression has duplicate parenthesis or not
• Find next Smaller of next Greater in an array
• Iterative method to find ancestors of a given binary tree
• Stack Permutations (Check if an array is stack permutation of other)
• Remove brackets from an algebraic string containing + and - operators
• Range Queries for Longest Correct Bracket Subsequence Set | 2

A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out) . LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.

Table of Content

What is Stack Data Structure?

• Basic Operations of Stack Data Structures

Applications of Stack Data Structures

Basics of stack data structure, implementations of stack in different languages, other implementations of stack data structures, easy problems on stack data structures, medium problems on stack data structures, hard problems on stack data structures.

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It behaves like a stack of plates, where the last plate added is the first one to be removed.

Think of it this way:

• Pushing an element onto the stack is like adding a new plate on top.
• Popping an element removes the top plate from the stack.

Key Operations on Stack Data Structures

• Push : Adds an element to the top of the stack.
• Pop : Removes the top element from the stack.
• Peek : Returns the top element without removing it.
• IsEmpty : Checks if the stack is empty.
• IsFull : Checks if the stack is full (in case of fixed-size arrays).
• Expression Evaluation and Parsing
• Depth-First Search (DFS)
• Undo/Redo Operations
• Browser History
• Function Calls
• Introduction to Stack – Data Structure and Algorithm Tutorials
• Basic Operations in Stack Data Structure
• Introduction to Monotonic Stack
• Stack in C#
• Implement Queue using Stacks
• Implement two stacks in an array
• Infix to Postfix Conversion using Stack
• Check for balanced parentheses in an expression
• Arithmetic Expression Evalution
• Reverse a stack using recursion
• Reverse a string using stack
• How to create mergable stack?
• Next Greater Element
• Iterative Postorder Traversal | Set 1 (Using Two Stacks)
• Largest Rectangular Area in a Histogram | Set 2
• Spaghetti Stack
• Remove brackets from an algebraic string containing + and – operators
• Range Queries for Longest Correct Bracket Subsequence

Quick Links :

• ‘Practice Problems’ on Stack
• ‘Videos’ on Stack
• ‘Quizzes’ on Stack

Recommended:

• Learn Data Structure and Algorithms | DSA Tutorial

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?