graph representation in data structure

Data Structures
Linked List
Binary Tree
Binary Search Tree
Segment Tree
Disjoint Set Union
Fenwick Tree
Red-Black Tree
Advanced Data Structures
Graph Data Structure And Algorithms
Introduction to Graphs - Data Structure and Algorithm Tutorials
Graph and its representations
Types of Graphs with Examples
Basic Properties of a Graph
Applications, Advantages and Disadvantages of Graph
Transpose graph
Difference Between Graph and Tree

BFS and DFS on Graph

Breadth First Search or BFS for a Graph
Depth First Search or DFS for a Graph
Applications, Advantages and Disadvantages of Depth First Search (DFS)
Applications, Advantages and Disadvantages of Breadth First Search (BFS)
Iterative Depth First Traversal of Graph
BFS for Disconnected Graph
Transitive Closure of a Graph using DFS
Difference between BFS and DFS

Cycle in a Graph

Detect Cycle in a Directed Graph
Detect cycle in an undirected graph
Detect Cycle in a directed graph using colors
Detect a negative cycle in a Graph | (Bellman Ford)
Cycles of length n in an undirected and connected graph
Detecting negative cycle using Floyd Warshall
Clone a Directed Acyclic Graph

Shortest Paths in Graph

How to find Shortest Paths from Source to all Vertices using Dijkstra's Algorithm
Bellman–Ford Algorithm
Floyd Warshall Algorithm
Johnson's algorithm for All-pairs shortest paths
Shortest Path in Directed Acyclic Graph
Multistage Graph (Shortest Path)
Shortest path in an unweighted graph
Karp's minimum mean (or average) weight cycle algorithm
0-1 BFS (Shortest Path in a Binary Weight Graph)
Find minimum weight cycle in an undirected graph

Minimum Spanning Tree in Graph

Kruskal’s Minimum Spanning Tree (MST) Algorithm
Difference between Prim's and Kruskal's algorithm for MST
Applications of Minimum Spanning Tree
Total number of Spanning Trees in a Graph
Minimum Product Spanning Tree
Reverse Delete Algorithm for Minimum Spanning Tree

Topological Sorting in Graph

Topological Sorting
All Topological Sorts of a Directed Acyclic Graph
Kahn's algorithm for Topological Sorting
Maximum edges that can be added to DAG so that it remains DAG
Longest Path in a Directed Acyclic Graph
Topological Sort of a graph using departure time of vertex

Connectivity of Graph

Articulation Points (or Cut Vertices) in a Graph
Biconnected Components
Bridges in a graph
Eulerian path and circuit for undirected graph
Fleury's Algorithm for printing Eulerian Path or Circuit
Strongly Connected Components
Count all possible walks from a source to a destination with exactly k edges
Euler Circuit in a Directed Graph
Word Ladder (Length of shortest chain to reach a target word)
Find if an array of strings can be chained to form a circle | Set 1
Tarjan's Algorithm to find Strongly Connected Components
Paths to travel each nodes using each edge (Seven Bridges of Königsberg)
Dynamic Connectivity | Set 1 (Incremental)

Maximum flow in a Graph

Max Flow Problem Introduction
Ford-Fulkerson Algorithm for Maximum Flow Problem
Find maximum number of edge disjoint paths between two vertices
Find minimum s-t cut in a flow network
Maximum Bipartite Matching
Channel Assignment Problem
Introduction to Push Relabel Algorithm
Introduction and implementation of Karger's algorithm for Minimum Cut
Dinic's algorithm for Maximum Flow

Some must do problems on Graph

Find size of the largest region in Boolean Matrix
Count number of trees in a forest
A Peterson Graph Problem
Clone an Undirected Graph
Introduction to Graph Coloring
Traveling Salesman Problem (TSP) Implementation
Introduction and Approximate Solution for Vertex Cover Problem
Erdos Renyl Model (for generating Random Graphs)
Chinese Postman or Route Inspection | Set 1 (introduction)
Hierholzer's Algorithm for directed graph
Boggle (Find all possible words in a board of characters) | Set 1
Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction)
Construct a graph from given degrees of all vertices
Determine whether a universal sink exists in a directed graph
Number of sink nodes in a graph
Two Clique Problem (Check if Graph can be divided in two Cliques)

Introduction to Graphs – Data Structure and Algorithm Tutorials

Introduction:.

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More 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).

Graph data structures are a powerful tool for representing and analyzing complex relationships between objects or entities. They are particularly useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structures can be used to analyze and understand the dynamics of team performance and player interactions on the field.

Imagine a game of football as a web of connections, where players are the nodes and their interactions on the field are the edges. This web of connections is exactly what a graph data structure represents, and it’s the key to unlocking insights into team performance and player dynamics in sports.

Components of a Graph

Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labelled/unlabelled.

Types Of Graph

1. null graph.

A graph is known as a null graph if there are no edges in the graph.

2. Trivial Graph

Graph having only a single vertex, it is also the smallest graph possible.

3. Undirected Graph

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge.

4. Directed Graph

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

5. Connected Graph

The graph in which from one node we can visit any other node in the graph is known as a connected graph.

6. Disconnected Graph

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

7. Regular Graph

The graph in which the degree of every vertex is equal to K is called K regular graph.

8. Complete Graph

The graph in which from each node there is an edge to each other node.

9. Cycle Graph

The graph in which the graph is a cycle in itself, the degree of each vertex is 2.

10. Cyclic Graph

A graph containing at least one cycle is known as a Cyclic graph.

11. Directed Acyclic Graph

A Directed Graph that does not contain any cycle.

12. Bipartite Graph

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

13. Weighted Graph

A graph in which the edges are already specified with suitable weight is known as a weighted graph.
Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs.

Tree v/s Graph

Trees are the restricted types of graphs, just with some more rules. Every tree will always be a graph but not all graphs will be trees. Linked List , Trees , and Heaps all are special cases of graphs.

Representation of Graphs

There are two ways to store a graph:

Adjacency Matrix

Adjacency list.

In this method, the graph is stored in the form of the 2D matrix where rows and columns denote vertices. Each entry in the matrix represents the weight of the edge between those vertices.

This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges connected to that vertex.

Comparison between Adjacency Matrix and Adjacency List

When the graph contains a large number of edges then it is good to store it as a matrix because only some entries in the matrix will be empty. An algorithm such as Prim’s and Dijkstra adjacency matrix is used to have less complexity.

Basic Operations on Graphs

Below are the basic operations on the graph:

Insertion of Nodes/Edges in the graph – Insert a node into the graph.
Deletion of Nodes/Edges in the graph – Delete a node from the graph.
Searching on Graphs – Search an entity in the graph.
Traversal of Graphs – Traversing all the nodes in the graph.

Usage of graphs

Maps can be represented using graphs and then can be used by computers to provide various services like the shortest path between two cities.
When various tasks depend on each other then this situation 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. In-game of tic tac toe this can be used.

Real-Life Applications of Graph

Following are the real-life applications:

Graph data structures can be used to represent the interactions between players on a team, such as passes, shots, and tackles. Analyzing these interactions can provide insights into team dynamics and areas for improvement.
Commonly used to represent social networks, such as networks of friends on social media.
Graphs can be used to represent the topology of computer networks, such as the connections between routers and switches.
Graphs are used to represent the connections between different places in a transportation network, such as roads and airports.
Neural Networks: Vertices represent neurons and edges represent the synapses between them. Neural networks are used to understand how our brain works and how connections change when we learn. The human brain has about 10^11 neurons and close to 10^15 synapses.
Compilers: Graphs are used extensively in compilers. They can be used for type inference, for so-called data flow analysis, register allocation, and many other purposes. They are also used in specialized compilers, such as query optimization in database languages.
Robot planning: Vertices represent states the robot can be in and the edges the possible transitions between the states. Such graph plans are used, for example, in planning paths for autonomous vehicles.

When to use Graphs:

When you need to represent and analyze the relationships between different objects or entities.
When you need to perform network analysis.
When you need to identify key players, influencers or bottlenecks in a system.
When you need to make predictions or recommendations.
Modeling networks: Graphs are commonly used to model various types of networks, such as social networks, transportation networks, and computer networks. In these cases, vertices represent nodes in the network, and edges represent the connections between them.
Finding paths: Graphs are often used in algorithms for finding paths between two vertices in a graph, such as shortest path algorithms. For example, graphs can be used to find the fastest route between two cities on a map or the most efficient way to travel between multiple destinations.
Representing data relationships: Graphs can be used to represent relationships between data objects, such as in a database or data structure. In these cases, vertices represent data objects, and edges represent the relationships between them.
Analyzing data: Graphs can be used to analyze and visualize complex data, such as in data clustering algorithms or machine learning models. In these cases, vertices represent data points, and edges represent the similarities or differences between them.

However, there are also some scenarios where using a graph may not be the best approach. For example, if the data being represented is very simple or structured, a graph may be overkill and a simpler data structure may suffice. Additionally, if the graph is very large or complex, it may be difficult or computationally expensive to analyze or traverse, which could make using a graph less desirable.

Advantages and Disadvantages:

Advantages:.

Graphs are a versatile data structure that 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.
Graphs can be used to represent complex data structures in a simple and intuitive way, making them easier to understand and analyze.

Disadvantages:

Graphs can be complex and difficult to understand, especially for people who are not familiar with graph theory or related algorithms.
Creating and manipulating graphs can be computationally expensive, especially for 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.
Graph data structures are a powerful tool for representing and analyzing relationships between objects or entities.
Graphs can be used to represent the interactions between different objects or entities, and then analyze these interactions to identify patterns, clusters, communities, key players, influencers, bottlenecks and anomalies.
In sports data science, graph data structures can be used to analyze and understand the dynamics of team performance and player interactions on the field.
They can be used in a variety of fields such as Sports, Social media, transportation, cybersecurity and many more.

More Resources of Graph

Recent Articles on Graph
Practice problems on Graph
Algorithms on Graphs

Please Login to comment...

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

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 »

A Gentle Introduction to Data Structures: How Graphs Work

by Michael Olorunnisola

So who wants to work at Google, Facebook, or maybe LinkedIn? Beyond their grueling interview process, one thing all these companies have in common is their heavy reliance on the graph data structure.

After learning a bit about graphs, you’ll understand why. By the end of this post, you’ll feel more comfortable jumping into Cracking the Coding Interview — or a similar interview prep book — and knocking out some network traversal algorithms practice problems.

How Graphs Work

Graphs are a powerful and versatile data structure that easily allow you to represent real life relationships between different types of data (nodes). There are two main parts of a graph:

The vertices (nodes) where the data is stored i.e. the numbers in the image on the left
The edges (connections) which connect the nodes i.e. the lines between the numbers in the image

Graphs can be undirected or directed . Using the graph above as an example — and treating the edges as every day relationships — here’s the difference:

Undirected graph: If 6 was a friend of 4, 4 would likewise be a friend of 6. The relationship exists in both directions.

Directed graph: if 6 had a crush on 4, that doesn’t necessarily mean 4 has to have a crush on 6. Love’s tough ?. The relationships are based on the direction of the edges. It can b e a one way relationship o r a two-way relationship, but it must be explicitly stated.

Here are some common operations you can perform on graphs:

addNode : adds vertices to your graph
addEdge : creates edges between two given vertices in your graph
removeNode : removes vertices from your graph
removeEdge : removes edges between two given vertices in your graph
contains : checks if your graph contains a given value
hasEdge : checks if a connection exists between two given nodes in your graph

In addition to this, graphs can be weighted or unweighted. All this means is that there is some value or cost associated with the edges between the vertices. The best example of this would be google maps.

As you can see, there are two suggested routes between Mumbai and Delhi. But how would a Google graph algorithm know that one in blue is the best option? Simple. You give the different routes (edges) weights equivalent to their distances. Knowing that, the algorithm can deduce that one path is 50km shorter than the other, and probably faster.

Of course, there are other factors given weight like delays and speed limits. But the concept remains the same. Weighted graphs allow you to choose the quickest path, or the path of least resistance (see Dijkstra’s Algorithm ).

As you can see from these examples, graphs can show almost any type of relationship with just data and edges. This is why graphs have become so widely used by companies like LinkedIn, Google, and Facebook. Just read this post by Facebook about why they made the transition back in 2007 from relational databases to graph databases.

Now that you have a basic understanding of what graphs are, let’s explore some examples.

Example Use Cases:

Representing a social network
Representing maps
Killing interview questions

The last one there is up to you. If you’re getting ready for a coding interview, I’ve included some helpful additional resources at the end of this post.

In the mean time, let’s take a stab at social networks.

Building a social network using graphs

Since Facebook kind of has a monopoly on this whole social network thing, how about we create a private social network for developers? DevBook! Of course, we could keep things simple and just create a Facebook group instead… But being grade A developers who love a good challenge, let’s take a prideful moment to throw “KISS” out the window.

First you create the storage for your graph. You realize there are probably multiple ways you can represent a graph data structure, but for now you decide upon a list that will store each unique developer as a key and all their connections as their associated values. Upon running a quick Google search, you realize that you’re making an adjacency list.

You prefer following a functional pattern, so you decide to go the route below:

Now that you have the graph representation, you need to create a way to add developers to the graph when they sign up, and to store any future connections they might have.

You decide to make the users keys on the object, and use an object with an edges property to keep a list of their connections.

Note that in practice, you would want to store records with unique user id’s instead of names that couldn’t be overwritten by other users with the same name, but I’ve used the names of famous programmers (plus myself) for flavor.

Now you can build a contains method to check whether a user has already been stored on your graph, and prevent the overwriting of any of the relationships that are created as the site grows.

Great! Now that you have a good set of unique users, you want to let them connect with each other by creating friendships with each other (edges). These edges won’t be directed, as you realize friendships don’t really work that way.

This is absolutely fantastic, but at some point Linus reaches out to you and says, “I have no idea who the Michael guy is. I assumed he was Michael Tiemann, but I finally bothered trying to read his last name.”

Right now you don’t have a way to remove a relationship, so you hop right into the code to whip together a removeEdge method to allow Linus to keep his friends list accurate.

Great! Unfortunately Linus says that he just wanted to try the site out, but that he’s way to0 hermitic to be on a site like this. He really wants to delete his account, but is currently unable to because you haven’t added a node removal method yet.

Great job! Although you lost a potentially valuable user, you’ve been able to implement a basic graph system to keep track of all of your users and their friendships.

If you notice, we didn’t implement the hasEdge method, but I think you have enough information to give it a shot! Feel free to include your implementation in the comments below ?.

A time complexity analysis on the graph methods as an adjacency list

Here’s our code again:

addNode is O(1): You’re just creating a property on an object so it’s constant time

addEdge is O(1): Since you’re using an object to represent your graph, it’s a constant time operation since your nodes and edges are represented as properties.

removeNode is O(n): If a node has edges, you’re going to have to iterate over all it’s existing edges to remove it’s existence as an edge on it’s connected nodes.

removeEdge is O(1): Since your nodes are properties on your graph, you can access them in constant time and just delete the edges which are also accessible in constant time.

contains is O(1): As a property on your graph, it’s a constant time lookup for a node.

hasEdge is O(1): Both nodes would be properties on your graph, so it would be a constant time lookup.

Time for a quick recap

are just a combination of vertices and edges representing data and relationships
have addNode , addEdge , removeNode , and removeEdge methods to manage their contents
have a contains and a hasEdge method to help you track the state of their state

12.1: Representing a Graph by a Matrix

Last updated
Save as PDF
Page ID 8485

Carleton University via Athabasca University Press

An adjacency matrix is a way of representing an $\mathtt{n}$ vertex graph $G=(V,E)$ by an $\mathtt{n}\times\mathtt{n}$ matrix, $\mathtt{a}$, whose entries are boolean values.

The matrix entry $\mathtt{a[i][j]}$ is defined as

\[\mathtt{a[i][j]}= \begin{cases} \mathtt{true} & \text{if } \mathtt{(i,j)}\in E \\ \mathtt{false} & \text{otherwise} \end{cases}\nonumber\]

The adjacency matrix for the graph in Figure 12.1 is shown in Figure $\PageIndex{1}$.

In this representation, the operations $\mathtt{addEdge(i,j)}$, $\mathtt{removeEdge(i,j)}$, and $\mathtt{hasEdge(i,j)}$ just involve setting or reading the matrix entry $\mathtt{a[i][j]}$:

These operations clearly take constant time per operation.

Where the adjacency matrix performs poorly is with the $\mathtt{outEdges(i)}$ and $\mathtt{inEdges(i)}$ operations. To implement these, we must scan all $\mathtt{n}$ entries in the corresponding row or column of $\mathtt{a}$ and gather up all the indices, $\mathtt{j}$, where $\mathtt{a[i][j]}$, respectively $\mathtt{a[j][i]}$, is true.

These operations clearly take $O(\mathtt{n})$ time per operation.

Another drawback of the adjacency matrix representation is that it is large. It stores an $\mathtt{n}\times \mathtt{n}$ boolean matrix, so it requires at least $\mathtt{n}^2$ bits of memory. The implementation here uses a matrix of $\mathtt{boolean}$ values so it actually uses on the order of $\mathtt{n}^2$ bytes of memory. A more careful implementation, which packs $\mathtt{w}$ boolean values into each word of memory, could reduce this space usage to $O(\mathtt{n}^2/\mathtt{w})$ words of memory.

Theorem $\PageIndex{1}$

The AdjacencyMatrix data structure implements the Graph interface. An AdjacencyMatrix supports the operations

$\mathtt{addEdge(i,j)}$, $\mathtt{removeEdge(i,j)}$, and $\mathtt{hasEdge(i,j)}$ in constant time per operation; and
$\mathtt{inEdges(i)}$, and $\mathtt{outEdges(i)}$ in $O(\mathtt{n})$ time per operation.

The space used by an AdjacencyMatrix is $O(\mathtt{n}^2)$.

Despite its high memory requirements and poor performance of the $\mathtt{inEdges(i)}$ and $\mathtt{outEdges(i)}$ operations, an AdjacencyMatrix can still be useful for some applications. In particular, when the graph $G$ is dense , i.e., it has close to $\mathtt{n}^2$ edges, then a memory usage of $\mathtt{n}^2$ may be acceptable.

The AdjacencyMatrix data structure is also commonly used because algebraic operations on the matrix $\mathtt{a}$ can be used to efficiently compute properties of the graph $G$. This is a topic for a course on algorithms, but we point out one such property here: If we treat the entries of $\mathtt{a}$ as integers (1 for $\mathtt{true}$ and 0 for $\mathtt{false}$) and multiply $\mathtt{a}$ by itself using matrix multiplication then we get the matrix $\mathtt{a}^2$. Recall, from the definition of matrix multiplication, that

\[\mathtt{a^2[i][j]} = \sum_{k=0}^{\mathtt{n}-1} \mathtt{a[i][k]}\cdot \mathtt{a[k][j]} \enspace .\nonumber\]

Interpreting this sum in terms of the graph $G$, this formula counts the number of vertices, $\mathtt{k}$, such that $G$ contains both edges $\mathtt{(i,k)}$ and $\mathtt{(k,j)}$. That is, it counts the number of paths from $\mathtt{i}$ to $\mathtt{j}$ (through intermediate vertices, $\mathtt{k}$) whose length is exactly two. This observation is the foundation of an algorithm that computes the shortest paths between all pairs of vertices in $G$ using only $O(\log \mathtt{n})$ matrix multiplications.

school Campus Bookshelves
menu_book Bookshelves
perm_media Learning Objects
login Login
how_to_reg Request Instructor Account
hub Instructor Commons
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.

9.2: Data Structures for Graphs

Last updated
Save as PDF
Page ID 80535

Al Doerr & Ken Levasseur
University of Massachusetts Lowell

In this section, we will describe data structures that are commonly used to represent graphs. In addition we will introduce the basic syntax for graphs in Sage.

Basic Data Structures

List $\PageIndex{1}$: Data Structures for Graphs

Assume that we have a graph with $n$ vertices that can be indexed by the integers $1, 2, \dots, n\text{.}$ Here are three different data structures that can be employed to represent graphs.

Adjacency Matrix: As we saw in Chapter 6, the information about edges in a graph can be summarized with an adjacency matrix, $G\text{,}$ where $G_{ij}=1$ if and only if vertex $i$ is connected to vertex $j$ in the graph. Note that this is the same as the adjacency matrix for a relation.
Edge Dictionary: For each vertex in our graph, we maintain a list of edges that initiate at that vertex. If $G$ represents the graph's edge information, then we denote by $G_i$ the list of vertices that are terminal vertices of edges initiating at vertex $i\text{.}$ The exact syntax that would be used can vary. We will use Sage/Python syntax in our examples.
Edge List: Note that in creating either of the first two data structures, we would presume that a list of edges for the graph exists. A simple way to represent the edges is to maintain this list of ordered pairs, or two element sets, depending on whether the graph is intended to be directed or undirected. We will not work with this data structure here, other than in the first example.

Example $\PageIndex{1}$: A Very Small Example

We consider the representation of the following graph:

$clipboard_e443c66cb08e7538cf6187ed2ba30a9ba.png$

The adjacency matrix that represents the graph would be

\begin{equation*} G=\left( \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array} \right)\text{.} \end{equation*}

The same graph could be represented with the edge dictionary

{1:[2,4],2:[3,4],3:[3],4:[1]} .

Notice the general form of each item in the dictionary: vertex:[list of vertices] .

Finally, a list of edges [(1,2),(1,4),(2,3),(2,4),(3,3),(4,1)] also describes the same graph.

A natural question to ask is: Which data structure should be used in a given situation? For small graphs, it really doesn't make much difference. For larger matrices the edge count would be a consideration. If $n$ is large and the number of edges is relatively small, it might use less memory to maintain an edge dictionary or list of edges instead of building an $n \times n$ matrix. Some software for working with graphs will make the decision for you.

Example $\PageIndex{2}$: NCAA Basketball

Consider the tournament graph representing a NCAA Division 1 men's (or women's) college basketball season in the United States. There are approximately 350 teams in Division 1. Suppose we constructed the graph with an edge from team A to team B if A beat B at least once in the season; and we label the edge with the number of wins. Since the average team plays around 30 games in a season, most of which will be against other Division I teams, we could expect around $\frac{30 \cdot 350}{2}=5,250$ edges in the graph. This would be somewhat reduced by games with lower division teams and cases where two or more wins over the same team produces one edge. Since 5,250 is much smaller than $350^2=122,500$ entries in an adjacency matrix, an edge dictionary or edge list would be more compact than an adjacency matrix. Even if we were to use software to create an adjacency matrix, many programs will identify the fact that a matrix such as the one in this example would be “sparse” and would leave data in list form and use sparse array methods to work with it.

The most common way to define a graph in Sage is to use an edge dictionary. Here is how the graph in Example $\PageIndex{1}$ is generated and then displayed. Notice that we simply wrap the function DiGraph() around the same dictionary expression we identified earlier.

You can get the adjacency matrix of a graph with the adjacency_matrix method.

You can also define a graph based on its adjacency matrix.

The edge list of any directed graph can be easily retrieved. If you replace edges with edge_iterator , you can iterate through the edge list. The third coordinate of the items in the edge is the label of the edge, which is None in this case.

Replacing the wrapper DiGraph() with Graph() creates an undirected graph.

There are many special graphs and graph families that are available in Sage through the graphs module. They are referenced with the prefix graphs. followed by the name and zero or more parameters inside parentheses. Here are a couple of them, first a complete graph with five vertices.

Here is a wheel graph, named for an obvious pattern of vertices and edges. We assign a name to it first and then show the graph without labeling the vertices.

There are dozens of graph methods, one of which determines the degree sequence of a graph. In this case, it's the wheel graph above.

The degree sequence method is defined within the graphs module, but the prefix graphs. is not needed because the value of w inherits the graphs methods.

Exercise $\PageIndex{1}$

Estimate the number of vertices and edges in each of the following graphs. Would the graph be considered sparse, so that an adjacency matrix would be inefficient?

Vertices: Cities of the world that are served by at least one airline. Edges: Pairs of cities that are connected by a regular direct flight.
Vertices: ASCII characters. Edges: connect characters that differ in their binary code by exactly two bits.
Vertices: All English words. Edges: An edge connects word $x$ to word $y$ if $x$ is a prefix of $y\text{.}$
A rough estimate of the number of vertices in the “world airline graph” would be the number of cities with population greater than or equal to 100,000. This is estimated to be around 4,100. There are many smaller cities that have airports, but some of the metropolitan areas with clusters of large cities are served by only a few airports. 4,000-5,000 is probably a good guess. As for edges, that's a bit more difficult to estimate. It's certainly not a complete graph. Looking at some medium sized airports such as Manchester, NH, the average number of cities that you can go to directly is in the 50-100 range. So a very rough estimate would be $\frac{75 \cdot 4500}{2}=168,750\text{.}$ This is far less than $4,500^2\text{,}$ so an edge list or dictionary of some kind would be more efficient.
The number of ASCII characters is 128. Each character would be connected to $\binom{8}{2}=28$ others and so there are $\frac{128 \cdot 28}{2}=3,584$ edges. Comparing this to the $128^2=16,384\text{,}$ an array is probably the best choice.
The Oxford English Dictionary as approximately a half-million words, although many are obsolete. The number of edges is probably of the same order of magnitude as the number of words, so an edge list or dictionary is probably the best choice.

Exercise $\PageIndex{2}$

Each edge of a graph is colored with one of the four colors red, blue, yellow, or green. How could you represent the edges in this graph using a variation of the adjacency matrix structure?

Exercise $\PageIndex{3}$

Directed graphs $G_1, \dots, G_6$ , each with vertex set $\{1,2,3,4,5\}$ are represented by the matrices below. Which graphs are isomorphic to one another?

$G_1: \left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$G_2: \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$G_3: \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} \right)$ $G_4: \left( \begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$\quad G_5: \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} \right)$$\quad \quad$$G_6: \left( \begin{array}{ccccc} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{array} \right)$

Each graph is isomorphic to itself. In addition, $G_2 \text{ and } G_4$ are isomorphic; and $G_3, G_5, \text{ and } G_6$ are isomorphic to one another.

Exercise $\PageIndex{4}$

The following Sage command verifies that the wheel graph with four vertices is isomorphic to the complete graph with four vertices.

A list of all graphs in this the graphs database is available via tab completion. Type "graphs." and then hit the tab key to see which graphs are available. This can be done using the Sage application or SageMathCloud, but not sage cells. Find some other pairs of isomorphic graphs in the database.

Learn Python practically and Get Certified .

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

Depth First Search (DFS)

Breadth first search

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.

For example, we have a graph below.

We can represent this graph in the form of a linked list on a computer as shown below.

Here, 0 , 1 , 2 , 3 are the vertices and each of them forms a linked list with all of its adjacent vertices. For instance, vertex 1 has two adjacent vertices 0 and 2. Therefore, 1 is linked with 0 and 2 in the figure above.

Pros of Adjacency List
An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.
It also helps to find all the vertices adjacent to a vertex easily.
Cons of Adjacency List
Finding the adjacent list is not quicker than the adjacency matrix because all the connected nodes must be first explored to find them.
Adjacency List Structure

The simplest adjacency list needs a node data structure to store a vertex and a graph data structure to organize the nodes.

We stay close to the basic definition of a graph - a collection of vertices and edges {V, E} . For simplicity, we use an unlabeled graph as opposed to a labeled one i.e. the vertices are identified by their indices 0,1,2,3.

Let's dig into the data structures at play here.

Don't let the struct node** adjLists overwhelm you.

All we are saying is we want to store a pointer to struct node* . This is because we don't know how many vertices the graph will have and so we cannot create an array of Linked Lists at compile time.

Adjacency List C++

It is the same structure but by using the in-built list STL data structures of C++, we make the structure a bit cleaner. We are also able to abstract the details of the implementation.

Adjacency List Java

We use Java Collections to store the Array of Linked Lists.

The type of LinkedList is determined by what data you want to store in it. For a labeled graph, you could store a dictionary instead of an Integer

Adjacency List Python

There is a reason Python gets so much love. A simple dictionary of vertices and its edges is a sufficient representation of a graph. You can make the vertex itself as complex as you want.

Adjacency List Code in Python, Java, and C/C++
Applications of Adjacency List
It is faster to use adjacency lists for graphs having less number of edges.

Introduction

Sorry about that.

Graphs Data Structures

This chapter is also already explained in this chapter . So if you already have prior knowledge, you can skip this chapter.

In simplest terms, a graph is a combination of vertices (or nodes) and edges.

In the above picture, we have 4 nodes and 4 edges and it is a graph.

Graph is a very important data structure to store data which are connected to each other. The simplest example is the network of roads connecting different cities.

We can see how different cities and roads are mapped into different nodes and edges to form a graph.

There are many other relationships which are stored using graphs efficiently. For example, electrical circuits, people network on social media like Facebook, etc.

We represent a graph as G=(V, E), where V is the set of all of its vertices and E is the set of all of its edges.

We are going to use |V| and |E| to represent the number of vertices and number of edges respectively.

Let's have a look at different types of graphs which are generally used.

Types of Graphs

Undirected graph and directed graph.

A graph in which if there is an edge connecting two vertices A and B, implies that B is also connected back to A is an undirected graph .

In the above graph, 1 is connected to 2 and 2 is connected back to 1 and this is true for every edge of the graph. So, the graph is an undirected graph.

In other words, we can say that a graph G=(V,E) is undirected if an edge (i, j) (edge from i to j) $\in$ E implies that the edge (j, i) $\in$ E also.

Two lane roads on which vehicles can go in either direction are the example of undirected graphs.

In a directed graph , the edges are directed i.e., they have a direction. So, if the edge is an edge from i to j i.e., (i, j) $\in$ E, then this doesn't necessarily mean that there will be also an edge from j to i.

This is a directed graph as there is a path from 1 to 2 but there isn't any path from 2 to 1.

Suppose a person is following someone on Twitter but may or may not be followed back. This can be represented by directed graphs.

Cyclic and Acyclic Graph

In a cyclic graph, there are cycles or loops formed by the edges but this doesn't happen with an acyclic graph.

Weighted and Unweighted Graph

Sometimes weights are given to the edges of a graph and these are called weighted graphs. For example, in a graph representing roads and cities, giving the length of the road as weight is a logical choice.

Dense and Sparse Graph

When the number of edges (|E|) is close to the square of the number of vertices (|V| 2 ), then the graph is a dense graph. To visualize, you can imagine a graph with few vertices and lots of edges between them.

If |E| is much less than |V| 2 , then it is a sparse graph.

Simple and Non-simple Graph

The graph which has self-loops or an edge (i, j) occurs more than once (also called multiedge and graph is called multigraph) is a non-simple graph.

Connected and Disconnected Graph

If every node of a graph is connected to some other nodes is a connected graph. However, if there is at least one node which is not connected to any other node, then it is a disconnected graph.

Complete Graph

When each node of a graph is connected to every other node, then it is called a complete graph.

Now, we have an idea of what basically is a graph. Now, we need to know how to use a graph in our program and for that we need to learn how to represent a graph.

Representation of Graphs

Adjacency-list representation
Adjacency-matrix representation

According to their names, we use lists in the case of adjacency-list representation and a matrix (2D array) in the case of adjacency matrix representation.

The way in which we are going to represent our graph depends on the task we have to perform. This will be clear after studying these representations in detail.

Adjacency-matrix Representation

In the adjacency-matrix representation, we use a |V|x|V| matrix to represent a graph.

Here, we are assuming that the vertices of the graph are numbered from 1 to |V|. Now for the cell (i, j) of this matrix, we set its value 1 if we have an edge from i to j (or (i, j) $\in$ E), otherwise 0.

In the above picture, we have an edge from 1 to 2, so the cell (1, 2) is 1, but there is no edge connecting 2 back to 1, so the cell (2, 1) is 0.

Similarly, there is no edge from the vertex 4 to any other vertices, so (4, 1), (4, 2), ... , (4, 5) all are 0.

It is quite clear that we are using a |V|x|V| matrix to represent a graph G=(V, E), so the space required to store this would be $\Theta(|V|^2)$.

Now imagine a social media site like Facebook, where there are billions of users. Using a matrix will take quite a large amount of space but the real problem is that even among these billions of people, a person is not connected most of the other person i.e., if each person on average has 1000 friends, then most of the cells are going to be empty (or 0). In this case (and most of the cases), we use adjaceny-list representation.

However, there is also one advantage of this representation - we can tell if one node is connected to another node in no time ($\Theta(1)$ to be appropriate).

We can say that using an adjacency-list for a sparse graph and adjacency-matrix for a dense graph is a general choice.

In most of the applications, the number of nodes which are connected from a node is much less than the total number of nodes. So, we move to adjacency-list representation.

Adjacency-list Representation

In adjacency-list representation, we have a list of all the nodes and for each node, we have a list of nodes for which the node has an edge.

For example, for the above graph, we will have a list of all the nodes.

Now, for each of these nodes, we will store a list (array, hash or linked list) of other nodes which have an edge from these nodes (or adjacent nodes). So, node 1 will have a list containing nodes 2 and 3, node 2 will have a list containing node 4, etc.

adjacency-list representation of a graph

Thus, in an adjacency-list representation, we have an array (Adj) of |V| lists and each element of this array Adj i.e., Adj[i] consists all the vertices adjacent to it.

The total number of items in all these lists is the number of edges in the graph i.e., |E|, if the graph is directed. But if the graph is undirected, then the total number of items in these adjacency lists will be 2|E| because for any edge (i, j), i will appear in adjacency list j and vice-versa.

number of nodes in directed and undirected adjacency-list representation of a graph

Now, the total space taken to store this graph will be space needed to store all adjacency list + space needed to store the lists of vertices i.e., |V|.

So, it requires $\Theta(|V| + |E|)$ space.

We can also add a new vertex in an adjacency -list in $O(1)$ time but doing the same will require $O(|V|^2)$ time in the case of an adjacency-matrix representation because a |V+1|x|V+1| matrix is needed to be reconstructed.

You can study about the algorithms using the graph data structure like BFS , DFS , etc. in the Algorithm Course .

Master the essential DSA & get better at coding interviews

🎯 Objective: Learn the fundamental concept of a Graph data structure and implement it in Java.

📝 Table of Contents

Introduction to Graphs
Types of Graphs
Graph Representation
Java Implementation

1️⃣ Introduction to Graphs

Graphs are one of the most versatile data structures used in computer science. A graph consists of nodes, often called vertices, and edges that connect pairs of vertices. Unlike arrays or linked lists, graphs can represent complex relationships between elements.

Why use Graphs?

Model Network Topologies
Solve Routing Problems
Social Network Analysis
Represent Hierarchies
… and much more!

2️⃣ Types of Graphs

Undirected Graph: Edges do not have a direction.
Directed Graph: Edges have a direction.
Weighted Graph: Edges have weights or costs associated with them.

3️⃣ Graph Representation

There are two popular ways to represent a graph:

Adjacency Matrix: A 2D array where the cell [i][j] is true if there is an edge from vertex i to vertex j .
Adjacency List: An array of lists. The index represents the vertex, and each element in the list represents the vertices that the index vertex is connected to.

4️⃣ Java Implementation

Adjacency list implementation:, 5️⃣ summary.

Graphs are incredibly flexible and widely used in various fields of computer science. In this post, we’ve covered the basics and provided a simple Java implementation. Happy learning!

Sign in to your account

Forgot your password?

Login via OTP

We will send you an one time password on your mobile number

An OTP has been sent to your mobile number please verify it below

Register with PrepBytes

Graph representation in data structure.

Last Updated on May 5, 2023 by Prepbytes

A graph is a type of data structure that represents a collection of objects called vertices or nodes that are connected by an edge network. A graph’s nodes typically represent entities, and its edges represent relationships or connections between two nodes. Social networks, road networks, and computer networks are all examples of graphs used to represent real-world relationships between objects or entities. In this article, we will discuss graph representation in Data structure.

Overview of Graph Data Structure

G = (V, E) denotes a graph G with a set of V vertices and an edge set of E. A graph is composed of the following two components:

A node is another name for a finite set of vertices.
An edge is defined as a finite set of ordered pairs of the form (u, v).

Because (u, v) is not the same as (v, u) in a directed graph, the pair is ordered. The (u, v) pair indicates that an edge exists between vertex u and vertex v. Weight, value, or cost may be assigned to the edges.

Type of Graphs in Data Structure

Mainly, there are two types of graphs:

Directed Graph

Un-directed Graph

A directed graph, also known as a digraph, is a type of graph in which the edges have a direction assigned to them. This means that the edges between nodes are unidirectional, with each having a distinct "start" and "end" point. In other words, an edge between two nodes in a directed graph represents a one-way relationship from the beginning node to the ending node.

An example of a directed graph is shown:

Directed graphs are frequently used to model asymmetric or directional relationships between objects, such as flow networks or one-way road networks. The in-degree of a node in a directed graph is the number of edges that point to the node, whereas the out-degree of a node is the number of edges that originate from the node.

Some standard algorithms that work on directed graphs :

Depth-first search
Topological sorting
Dijkstra’s algorithm for finding the shortest path,
Bellman-Ford algorithm for finding the shortest path with negative weights.

Undirected Graph

An undirected graph has edges that do not have a direction assigned to them. This means that node edges are bidirectional, and there is no concept of a "start" or "end" point. In other words, an edge between two nodes in an undirected graph represents a two-way relationship between the nodes, and information can flow freely in either direction along the edge.

Here’s an example of an undirected graph:

Undirected graphs are commonly used to represent symmetric or bidirectional relationships between objects, such as friendship networks or road networks with traffic flowing in either direction. In an undirected graph, the degree of a node is simply the number of edges that are incident on the node, regardless of their direction.

Breadth-first search
Kruskal’s algorithm for finding minimum spanning trees.

Graph Representation in Data Structures

A graph can be represented using three data structures-

Adjacency matrix
Adjacency list
Incidence matrix

Adjacency Matrix Representation

An adjacency matrix is a type of sequential representation.

It is used to indicate which nodes are adjacent to one another. I.e., do any edges connect nodes in a graph?
In this representation, an NxN matrix A must be created. If an edge connects vertex i and vertex j, the corresponding element of A is ai,j = 1, otherwise, it is ai,j = 0.
If there is a weighted graph, we can store the edge weight instead of 1s and 0s.

Directed Graph Representation

Undirected Graph Representation

Pros and Cons of the Adjacency Matrix

Pros: Representation is simpler to implement and adhere to.
Cons: It takes a lot of space and time to visit all of a vertex’s neighbors; we have to traverse all of the vertices in the graph, which takes a long time.

Adjacency List Representation

A linked representation is an adjacency list.

In this representation, we keep a list of neighbors for each vertex in the graph.
It means that each vertex in the graph has a list of its neighbors.
Each array element points to a singly linked list of v’s neighbors, and the array is indexed by the vertex number.

Pros and Cons of the Adjacency List

A list of adjacencies saves a lot of space.
We can easily insert and delete items because we are using a linked list.
Such a representation is simple to understand and clearly shows the adjacent nodes.

Cons: While the adjacency list allows you to test whether two vertices are adjacent, it is slower to perform this operation.

Incidence Matrix Representation

The following matrix can be used to represent a graph in incidence matrix form:

The total number of vertices is divided by the total number of edges.
That is, a 4X6 matrix can represent a graph with four vertices and six edges. Within this matrix, the columns represent edges and the rows represent vertices.
The row edge that is not connected to the column vertex is represented by 0.
The row edge is represented by 1 and is an outgoing edge from the column vertex.
-1 represents the row edge that connects to the column vertex as an incoming edge.

Conclusion In this article, we have discussed how we represent a graph in a data structure. So we can represent a graph in mainly three ways: the Adjacency list, Incidence matrix and Adjacency matrix and we have also discussed in detail how these work in addition to the advantages and disadvantages of each representation.

Frequently Asked Questions (FAQs)

Q1. What are the three types of graph data structures? Ans. An adjacency matrix, an adjacency list, or an adjacency set can all be used to represent a graph.

Q2. What is graph representation? Ans. A graph representation is a technique used in graph theory to store graphs in a computer’s memory.

Q3. What are BFS and DFS? Ans. BFS is an acronym that stands for Breadth First Search. DFS is an abbreviation for Depth First Search. Data structure. BFS employs a Queue to determine the shortest path. DFS uses a stack to find the shortest path.

Q4. Why do we use graph representation? Ans. Graphs in data structures are used to represent the relationships between objects.

Q5. Which one is better, BFS or DFS? Ans. When a user searches for vertices that remain close to any given source, BFS performs better. DFS works better when a user can find solutions away from any given source.

Representing Graphs in Data Structures

Contributed by: Ruchi Nayyar

A graph can be thought of as a data structure that is used to describe relationships between entities. An entity can be any item that has a distinctive and independent existence. It could either be an actual physical object or an abstract idea. For example, an entity can be a person, place or an organization about which data can be stored.

In the computing world, graphs have become ubiquitous owing to their ability to not only provide abstractions to real life but also demonstrate complicated relationships with ease. As such, a variety of practical problems can be represented as graphs. For example, a linked structure of websites can be viewed as a graph.

Every graph is a set of points referred to as vertices or nodes which are connected using lines called edges . The vertices represent entities in a graph. Edges, on the other hand, express relationships between entities. Hence, while nodes model entities, edges model relationships in a network graph. A graph G with a set of V vertices together with a set of E edges is represented as G= (V, E) . Both vertices and edges can have additional attributes that are used to describe the entities and relationships. Figure 1 depicts a simple graph with five nodes and six edges.

In real-world applications of graphs, an edge might represent professional relationships that exist between people in LinkedIn or a personal relationship on a social media platform such as Facebook or Instagram.

Graphs can broadly be categorized into Undirected (Fig 2a) or Directed (Fig 2b). An undirected graph is directionless. This means that the edges have no directions. In other words, the relationship is mutual. For example, a Facebook or a LinkedIn connection. Contrarily, edges of directed graphs have directions associated with them. An asymmetric relationship between a boss and an employee or a teacher and a student can be represented as a directed graph in data structure. Graphs can also be weighted (Fig 2c) indicating real values associated with the edges. Depending upon the specific use of the graph, edge weights may represent quantities such as distance, cost, similarity etc.

A graph can be represented using 3 data structures- adjacency matrix, adjacency list and adjacency set.

An adjacency matrix can be thought of as a table with rows and columns. The row labels and column labels represent the nodes of a graph. An adjacency matrix is a square matrix where the number of rows, columns and nodes are the same. Each cell of the matrix represents an edge or the relationship between two given nodes. For example, adjacency matrix Aij represents the number of links from i to j, given two nodes i and j.

The adjacency matrix for a directed graph is shown in Fig 3. Observe that it is a square matrix in which the number of rows, columns and nodes remain the same (5 in this case). Each row and column correspond to a node or a vertex of a graph. The cells within the matrix represent the connection that exists between nodes. Since, in the given directed graph, no node is connected to itself, all cells lying on the diagonal of the matrix are marked zero. For the rest of the cells, if there exists a directed edge from a given node to another, then the corresponding cell will be marked one else zero.

To understand how an undirected graph can be represented using an adjacency matrix, consider a small undirected graph with five vertices (Fig 4). Here, A is connected to B, but B is connected to A as well. Hence, both the cells i.e., the one with source A destination B and the other one with source B destination A are marked one. This suffices the requirement of an undirected edge. Observe that the second entry is at a mirrored location across the main diagonal.

In case of a weighted graph, the cells are marked with edge weights instead of ones. In Fig 5, the weight assigned to the edge connecting nodes B and D is 3. Hence, the corresponding cells in the adjacency matrix i.e. row B column D and row D column B are marked 3.

NetworkX library provides an easy method to create adjacency matrices. The following example shows how we can create a basic adjacency matrix using NetworkX.

In adjacency list representation of a graph, every vertex is represented as a node object. The node may either contain data or a reference to a linked list. This linked list provides a list of all nodes that are adjacent to the current node. Consider a graph containing an edge connecting node A and node B. Then, the node A will be available in node B’s linked list. Fig 6 shows a sample graph of 5 nodes and its corresponding adjacency list.

Note that the list corresponding to node E is empty while lists corresponding to nodes B and D have 2 entries each.

Similarly, adjacency lists for an undirected graph can also be constructed. Fig 7 provides an example of an undirected graph along with its adjacency list for better understanding.

Adjacency list enables faster search process in comparison to adjacency matrix. However, it is not the best representation of graphs especially when it comes to adding or removing nodes. For example, deleting a node would involve looking through all the adjacency lists to remove a particular node from all lists. NetworkX library provides a function adjacency_list () to generate the adjacency list of a given graph. The following code demonstrates its use.

The adjacency set mitigates a few of the challenges posed by adjacency list. Adjacency set is quite similar to adjacency list except for the difference that instead of a linked list; a set of adjacent vertices is provided. Adjacency list and set are often used for sparse graphs with few connections between nodes. Contrarily, adjacency matrix works well for well-connected graphs comprising many nodes.

This brings us to the end of the blog on graph in data structure. We hope you found this helpful. If you wish to learn more such concepts, you can check out Great Learning Academy’s free online courses .

Top Free Courses

Top 30 Python Libraries To Know

Python Dictionary Append: How To Add Key/Value Pair?

¿Qué es la Ciencia de Datos? – Una Guía Completa [2024]

What is Data Science? – The Complete Guide

What is Time Complexity And Why Is It Essential?

Python NumPy Tutorial – 2024

Terminology and Representations of Graphs

This post discusses the basic definitions in terminologies associated with graphs and covers the adjacency list and adjacency matrix representations of the graph data structure.

What is a Graph?

A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes and a collection of pairs of vertices from V , known as edges of a graph. For example, for the graph below.

V = { 1, 2, 3, 4, 5, 6 } E = { (1, 4), (1, 6), (2, 6), (4, 5), (5, 6) }

Types of Graph

1. undirected graph.

An undirected graph (graph) is a graph in which edges have no orientation. The edge (x, y) is identical to edge (y, x) , i.e., they are not ordered pairs. The maximum number of edges possible in an undirected graph without a loop is n×(n-1)/2 .

2. Directed graph

A Directed graph (digraph) is a graph in which edges have orientations, i.e., The edge (x, y) is not identical to edge (y, x) .

3. Directed Acyclic Graph (DAG)

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.

4. Multi graph

A multigraph is an undirected graph in which multiple edges (and sometimes loops) are allowed. Multiple edges are two or more edges that connect the same two vertices. A loop is an edge (directed or undirected) that connects a vertex to itself; it may be permitted or not.

5. Simple graph

A simple graph is an undirected graph in which both multiple edges and loops are disallowed as opposed to a multigraph. In a simple graph with n vertices, every vertex’s degree is at most n-1 .

6. Weighted and Unweighted graph

A weighted graph associates a value (weight) with every edge in the graph. We can also use words cost or length instead of weight.

An unweighted graph does not have any value (weight) associated with every edge in the graph. In other words, an unweighted graph is a weighted graph with all edge weight as 1. Unless specified otherwise, all graphs are assumed to be unweighted by default.

7. Complete graph

A complete graph is one in which every two vertices are adjacent: all edges that could exist are present.

8. Connected graph

A Connected graph has a path between every pair of vertices. In other words, there are no unreachable vertices. A disconnected graph is a graph that is not connected.

Most commonly used terms in Graphs

An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two vertices to which it is attached, called its endpoints .
Two vertices are called adjacent if they are endpoints of the same edge.
Outgoing edges of a vertex are directed edges that the vertex is the origin.
Incoming edges of a vertex are directed edges that the vertex is the destination.
The degree of a vertex in a graph is the total number of edges incident to it.
In a directed graph, the out-degree of a vertex is the total number of outgoing edges, and the in-degree is the total number of incoming edges.
A vertex with in-degree zero is called a source vertex, while a vertex with out-degree zero is called a sink vertex.
An isolated vertex is a vertex with degree zero, which is not an endpoint of an edge.
Path is a sequence of alternating vertices and edges such that the edge connects each successive vertex.
Cycle is a path that starts and ends at the same vertex.
Simple path is a path with distinct vertices.
A graph is Strongly Connected if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u , v .
A directed graph is called Weakly Connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. The vertices in a weakly connected graph have either out-degree or in-degree of at least 1.
Connected component is the maximal connected subgraph of an unconnected graph.
A bridge is an edge whose removal would disconnect the graph.
Forest is a graph without cycles.
Tree is a connected graph with no cycles. If we remove all the cycles from DAG (Directed Acyclic Graph), it becomes a tree, and if we remove any edge in a tree, it becomes a forest.
Spanning tree of an undirected graph is a subgraph that is a tree that includes all the vertices of the graph.

Relationship between number of edges and vertices

For a simple graph with m edges and n vertices, if the graph is

directed, then m = n×(n-1)
undirected, then m = n×(n-1)/2
connected, then m = n-1
a tree, then m = n-1
a forest, then m = n-1
complete, then m = n×(n-1)/2

Therefore, O(m) may vary between O(1) and O(n 2 ) , depending on how dense the graph is.

Graph Representation

1. adjacency matrix representation:.

An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Definition:

For a simple unweighted graph with vertex set V , the adjacency matrix is a square |V| × |V| matrix A such that its element:

A ij = 1 , when there is an edge from vertex i to vertex j , and A ij = 0 , when there is no edge.

Each row in the matrix represents source vertices, and each column represents destination vertices. The diagonal elements of the matrix are all zero since edges from a vertex to itself, i.e., loops are not allowed in simple graphs. If the graph is undirected, the adjacency matrix will be symmetric. Also, for a weighted graph, A ij can represent edge weights.

An adjacency matrix keeps a value (1/0/edge-weight) for every pair of vertices, whether the edge exists or not, so it requires n 2 space. They can be efficiently used only when the graph is dense.

2. Adjacency List Representation:

An adjacency list representation for the graph associates each vertex in the graph with the collection of its neighboring vertices or edges, i.e., every vertex stores a list of adjacent vertices. There are many variations of adjacency list representation depending upon the implementation. This data structure allows the storage of additional data on the vertices but is practically very efficient when the graph contains only a few edges. i.e. the graph is sparse.

Also See:

Implement Graph Data Structure in C

Graph Implementation in C++ (without using STL)

Graph Implementation in C++ using STL

Graph Implementation in Java using Collections

References:

1. http://www.csl.mtu.edu/cs2321/www/newLectures/24_Graph_Terminology.html

2. https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

Rate this post

Average rating 4.82 /5. Vote count: 128

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?

Thanks for reading.

To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and support our growth. Happy coding :)

Dynamic Arrays
Linked Lists
Singly Linked Lists
Doubly Linked Lists
Queues and Circular Queues
Tree Data Structure
Tree Representation
Binary Trees
Binary Heaps
Priority Queues
Binomial Heaps
Binary Search Trees
Self-balancing Binary Search Trees
2-3-4 Trees
Red Black Trees
Splay Trees
Randomly Built Binary Search Trees
Graphs and Graph Terminologies

Graph Representation: Adjacency List and Matrix

Introduction.

In the previous post , we introduced the concept of graphs. In this post, we discuss how to store them inside the computer. There are two popular data structures we use to represent graph: (i) Adjacency List and (ii) Adjacency Matrix. Depending upon the application, we use either adjacency list or adjacency matrix but most of the time people prefer using adjacency list over adjacency matrix.

Adjacency Lists

Adjacency lists are the right data structure for most applications of graphs.

Adjacency lists, in simple words, are the array of linked lists. We create an array of vertices and each entry in the array has a corresponding linked list containing the neighbors. In other words, if a vertex 1 has neighbors 2, 3, 4, the array position corresponding the vertex 1 has a linked list of 2, 3, and 4. We can use other data structures besides a linked list to store neighbors. I personally prefer to use a hash table and I am using the hash table in my implementation. You can also use balanced binary search trees as well. To store the adjacency list, we need $O(V + E)$ space as we need to store every vertex and their neighbors (edges).

To find if a vertex has a neighbor, we need to go through the linked list of the vertex. This requires $O(1 + deg(V))$ time. If we use balanced binary search trees, it becomes $O(1 + \log(deg(V))$ and using appropriately constructed hash tables, the running time lowers to $O(1)$.

Figure 1 shows the linked list representation of a directed graph.

In an undirected graph, to store an edge between vertices $A$ and $B$, we need to store $B$ in $A$’s linked list and vice versa. Figure 2 depicts this.

Adjacency Matrices

An adjacency matrix is a $V \times V$ array. It is obvious that it requires $O(V^2)$ space regardless of a number of edges. The entry in the matrix will be either 0 or 1. If there is an edge between vertices $A$ and $B$, we set the value of the corresponding cell to 1 otherwise we simply put 0. Adjacency matrices are a good choice when the graph is dense since we need $O(V^2)$ space anyway. We can easily find whether two vertices are neighbors by simply looking at the matrix. This can be done in $O(1)$ time. Figure 1 and 2 show the adjacency matrix representation of a directed and undirected graph.

Representing Weighted Graphs

We can modify the previous adjacency lists and adjacency matrices to store the weights. In the adjacency list, instead of storing the only vertex, we can store a pair of numbers one vertex and other the weight. Similarly, in the adjacency matrix, instead of just storing 1 we can store the actual weight. Figure 3 illustrates this.

The table below summarizes the operations and their running time in adjacency list and adjacency matrix.

Implementation

Since I will be doing all the graph related problem using adjacency list, I present here the implementation of adjacency list only. You can find the codes in C++, Java, and Python below.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.
Jeff Erickson. Algorithms (Prepublication draft). http://algorithms.wtf
Steven S. Skiena. 2008. The Algorithm Design Manual (2nd ed.). Springer Publishing Company, Incorporated.

DSA Tutorial

Linked lists, stacks & queues, hash tables, shortest path, minimum spanning tree, maximum flow, time complexity, dsa reference, dsa examples.

A Graph is a non-linear data structure that consists of vertices (nodes) and edges.

A vertex, also called a node, is a point or an object in the Graph, and an edge is used to connect two vertices with each other.

Graphs are non-linear because the data structure allows us to have different paths to get from one vertex to another, unlike with linear data structures like Arrays or Linked Lists.

Graphs are used to represent and solve problems where the data consists of objects and relationships between them, such as:

Social Networks: Each person is a vertex, and relationships (like friendships) are the edges. Algorithms can suggest potential friends.
Maps and Navigation: Locations, like a town or bus stops, are stored as vertices, and roads are stored as edges. Algorithms can find the shortest route between two locations when stored as a Graph.
Internet: Can be represented as a Graph, with web pages as vertices and hyperlinks as edges.
Biology: Graphs can model systems like neural networks or the spread of diseases.

Graph Properties

Use the animation below to get an understanding of the different Graph properties, and how these properties can be combined.

A weighted Graph is a Graph where the edges have values. The weight value of an edge can represent things like distance, capacity, time, or probability.

A connected Graph is when all the vertices are connected through edges somehow. A Graph that is not connected, is a Graph with isolated (disjoint) subgraphs, or single isolated vertices.

A connected Graph depending on if it is directed or not:

We have an undirected connected Graph is if you can go along the edges in the Graph from one node, to every other node in the Graph.
A strongly connected directed Graph is if you can start at any node and reach every other node in the Graph along the directed edges.
A weakly connected directed Graph is if you can reach all nodes from any node, when disregarding the direction of the edges.

A directed Graph, also known as a digraph, is when the edges between the vertex pairs have a direction. The direction of an edge can represent things like hierarchy or flow.

A cyclic Graph is defined differently depending on whether it is directed or not:

A directed cyclic Graph is when you can follow a path along the directed edges that goes in circles. Removing the directed edge from F to G in the animation above makes the directed Graph not cyclic anymore.
An undirected cyclic Graph is when you can come back to the same vertex you started at without using the same edge more than once. The undirected Graph above is cyclic because we can start and end up in vertes C without using the same edge twice.

A loop , also called a self-loop, is an edge that begins and ends on the same vertex. A loop is a cycle that only consists of one edge. By adding the loop on vertex A in the animation above, the Graph becomes cyclic.

Graph Representations

A Graph representation tells us how a Graph is stored in memory.

Different Graph representations can:

take up more or less space.
be faster or slower to search or manipulate.
be better suited depending on what type of Graph we have (weighted, directed, etc.), and what we want to do with the Graph.
be easier to understand and implement than others.

Below are short introductions of the different Graph representations, but Adjacency Matrix is the representation we will use for Graphs moving forward in this tutorial, as it is easy to understand and implement, and works in all cases relevant for this tutorial.

Graph representations store information about which vertices are adjacent, and how the edges between the vertices are. Graph representations are slightly different if the edges are directed or weighted.

Two vertices are adjacent, or neighbors, if there is an edge between them.

Adjacency Matrix Graph Representation

Adjacency Matrix is the Graph representation (structure) we will use for this tutorial.

How to implement an Adjacency Matrix is shown on the next page.

The Adjacency Matrix is a 2D array (matrix) where each cell on index (i,j) stores information about the edge from vertex i to vertex j .

Below is a Graph with the Adjacency Matrix representation next to it.

The adjacency matrix above represents an undirected Graph, so the values '1' only tells us where the edges are. Also, the values in the adjacency matrix is symmetrical because the edges go both ways (undirected Graph).

To create a directed Graph with an adjacency matrix, we must decide which vertices the edges go from and to, by inserting the value at the correct indexes (i,j) . To represent a weighted Graph we can put other values than '1' inside the adjacency matrix.

Below is a directed and weighted Graph with the Adjacency Matrix representation next to it.

In the adjacency matrix above, the value 3 on index (0,1) tells us there is an edge from vertex A to vertex B, and the weight for that edge is 3 .

As you can see, the weights are placed directly into the adjacency matrix for the correct edge, and for a directed Graph, the adjacency matrix does not have to be symmetric.

Adjacency List Graph Representation

In case we have a 'sparse' Graph with many vertices, we can save space by using an Adjacency List compared to using an Adjacency Matrix, because an Adjacency Matrix would reserve a lot of memory on empty Array elements for edges that don't exist.

A 'sparse' Graph is a Graph where each vertex only has edges to a small portion of the other vertices in the Graph.

An Adjacency List has an array that contains all the vertices in the Graph, and each vertex has a Linked List (or Array) with the vertex's edges.

In the adjacency list above, the vertices A to D are placed in an Array, and each vertex in the array has its index written right next to it.

Each vertex in the Array has a pointer to a Linked List that represents that vertex's edges. More specifically, the Linked List contains the indexes to the adjacent (neighbor) vertices.

So for example, vertex A has a link to a Linked List with values 3, 1, and 2. These values are the indexes to A's adjacent vertices D, B, and C.

An Adjacency List can also represent a directed and weighted Graph, like this:

In the Adjacency List above, vertices are stored in an Array. Each vertex has a pointer to a Linked List with edges stored as i,w , where i is the index of the vertex the edge goes to, and w is the weight of that edge.

Node D for example, has a pointer to a Linked List with an edge to vertex A. The values 0,4 means that vertex D has an edge to vertex on index 0 (vertex A), and the weight of that edge is 4 .

DSA Exercises

Test yourself with exercises.

How can the Graph below be described?

Start the Exercise

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]

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

Ensure that you are logged in and have the required permissions to access the test.

A server error has occurred. Please refresh the page or try after some time.

An error has occurred. Please refresh the page or try after some time.

Signup and get free access to 100+ Tutorials and Practice Problems Start Now

Linear Search
Binary Search
Ternary Search
Bubble Sort
Selection Sort
Insertion Sort
Counting Sort
Bucket Sort
Basics of Greedy Algorithms

Graph Representation

Breadth First Search
Depth First Search
Minimum Spanning Tree
Shortest Path Algorithms
Flood-fill Algorithm
Articulation Points and Bridges
Biconnected Components
Strongly Connected Components
Topological Sort
Hamiltonian Path
Maximum flow
Minimum Cost Maximum Flow
Basics of String Manipulation
String Searching
Z Algorithm
Manachar’s Algorithm
Introduction to Dynamic Programming 1
2 Dimensional
State space reduction
Dynamic Programming and Bit Masking

Graphs are mathematical structures that represent pairwise relationships between objects. A graph is a flow structure that represents the relationship between various objects. It can be visualized by using the following two basic components:

Nodes: These are the most important components in any graph. Nodes are entities whose relationships are expressed using edges. If a graph comprises 2 nodes $$A$$ and $$B$$ and an undirected edge between them, then it expresses a bi-directional relationship between the nodes and edge.

Edges: Edges are the components that are used to represent the relationships between various nodes in a graph. An edge between two nodes expresses a one-way or two-way relationship between the nodes.

Types of nodes

Root node: The root node is the ancestor of all other nodes in a graph. It does not have any ancestor. Each graph consists of exactly one root node. Generally, you must start traversing a graph from the root node.

Leaf nodes: In a graph, leaf nodes represent the nodes that do not have any successors. These nodes only have ancestor nodes. They can have any number of incoming edges but they will not have any outgoing edges.

Types of graphs

Undirected: An undirected graph is a graph in which all the edges are bi-directional i.e. the edges do not point in any specific direction.

Directed: A directed graph is a graph in which all the edges are uni-directional i.e. the edges point in a single direction.

Weighted: In a weighted graph, each edge is assigned a weight or cost. Consider a graph of 4 nodes as in the diagram below. As you can see each edge has a weight/cost assigned to it. If you want to go from vertex 1 to vertex 3, you can take one of the following 3 paths:

1 -> 2 -> 3
1 -> 4 -> 3

Therefore the total cost of each path will be as follows: - The total cost of 1 -> 2 -> 3 will be (1 + 2) i.e. 3 units - The total cost of 1 -> 3 will be 1 unit - The total cost of 1 -> 4 -> 3 will be (3 + 2) i.e. 5 units

Cyclic: A graph is cyclic if the graph comprises a path that starts from a vertex and ends at the same vertex. That path is called a cycle. An acyclic graph is a graph that has no cycle.

A tree is an undirected graph in which any two vertices are connected by only one path. A tree is an acyclic graph and has N - 1 edges where N is the number of vertices. Each node in a graph may have one or multiple parent nodes. However, in a tree, each node (except the root node) comprises exactly one parent node.

Note : A root node has no parent.

A tree cannot contain any cycles or self loops, however, the same does not apply to graphs.

Graph representation

You can represent a graph in many ways. The two most common ways of representing a graph is as follows:

Adjacency matrix

An adjacency matrix is a VxV binary matrix A . Element $$A_{i,j}$$ is 1 if there is an edge from vertex i to vertex j else $$A_{i,j}$$ is 0.

Note : A binary matrix is a matrix in which the cells can have only one of two possible values - either a 0 or 1.

The adjacency matrix can also be modified for the weighted graph in which instead of storing 0 or 1 in $$A_{i,j}$$ , the weight or cost of the edge will be stored.

In an undirected graph, if $$A_{i,j}$$ = 1, then $$A_{j,i}$$ = 1. In a directed graph, if $$A_{i,j}$$ = 1, then $$A_{j,i}$$ may or may not be 1.

Adjacency matrix provides constant time access (O(1) ) to determine if there is an edge between two nodes. Space complexity of the adjacency matrix is O($$V^2$$) .

The adjacency matrix of the following graph is: i/j : 1 2 3 4 1 : 0 1 0 1 2 : 1 0 1 0 3 : 0 1 0 1 4 : 1 0 1 0

The adjacency matrix of the following graph is:

i/j : 1 2 3 4 1 : 0 1 0 0 2 : 0 0 0 1 3 : 1 0 0 1 4 : 0 1 0 0

Consider the directed graph given above. Let's create this graph using an adjacency matrix and then show all the edges that exist in the graph.

Input file 4 $$\hspace{2cm}$$ // nodes 5 $$\hspace{2cm}$$//edges 1 2 $$\hspace{1.5cm}$$ //showing edge from node 1 to node 2 2 4 $$\hspace{1.5cm}$$ //showing edge from node 2 to node 4 3 1 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 1 3 4 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 4 4 2 $$\hspace{1.5cm}$$ //showing edge from node 4 to node 2

There is an edge between 3 and 4.

There is no edge between 2 and 3.

Adjacency list

The other way to represent a graph is by using an adjacency list. An adjacency list is an array A of separate lists. Each element of the array A i is a list, which contains all the vertices that are adjacent to vertex i.

For a weighted graph, the weight or cost of the edge is stored along with the vertex in the list using pairs. In an undirected graph, if vertex j is in list $$A_{i}$$ then vertex i will be in list $$A_{j}$$ .

The space complexity of adjacency list is O(V + E) because in an adjacency list information is stored only for those edges that actually exist in the graph. In a lot of cases, where a matrix is sparse using an adjacency matrix may not be very useful. This is because using an adjacency matrix will take up a lot of space where most of the elements will be 0, anyway. In such cases, using an adjacency list is better.

Note: A sparse matrix is a matrix in which most of the elements are zero, whereas a dense matrix is a matrix in which most of the elements are non-zero.

Consider the same undirected graph from an adjacency matrix. The adjacency list of the graph is as follows:

Consider the same directed graph from an adjacency matrix. The adjacency list of the graph is as follows:

A1 → 2 A2 → 4 A3 → 1 → 4 A4 → 2

Consider the directed graph given above. The code for this graph is as follows:

4 $$\hspace{2cm}$$ // nodes 5 $$\hspace{2cm}$$ //edges 1 2 $$\hspace{1.5cm}$$ //showing edge from node 1 to node 2 2 4 $$\hspace{1.5cm}$$ //showing edge from node 2 to node 4 3 1 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 1 3 4 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 4 4 2 $$\hspace{1.5cm}$$ //showing edge from node 4 to node 2

Adjacency list of node 1: 2
Adjacency list of node 2: 4
Adjacency list of node 3: 1 --> 4
Adjacency list of node 4: 2

An alphabet
A special character
Minimum 8 characters

A password reset link will be sent to the following email id

Ha-gnn: a novel graph neural network based on hyperbolic attention

Original Article
Published: 21 April 2024

Cite this article

Hongbo Qu 1 ,
Yu-Rong Song ORCID: orcid.org/0000-0002-5827-4413 2 ,
Minglei Zhang 1 ,
Guo-Ping Jiang 2 ,
Ruqi Li 1 &
Bo Song 3

Graph neural networks (GNNs) are powerful tools for data mining on graph-structured data in various domains, such as social science, finance, and biology. However, most existing GNNs operate in Euclidean space and may fail to preserve the intrinsic network properties, such as self-similarity and hierarchy, that characterize many real-world graphs. Hyperbolic graph neural networks (HGNNs) address this limitation by embedding graphs into hyperbolic space, which can better capture the hierarchical structures of networks. However, HGNNs often involve complex computations in hyperbolic space or its tangent space during training, which may hinder their efficiency. In this paper, we propose hyperbolic attention graph neural networks (HA-GNN), which can leverage both network structure and node features for graph representation learning in an efficient way. Specifically, we design a structural properties attention mechanism that measures the structural connection between nodes based on their hyperbolic embeddings. We also design a node features attention mechanism that quantifies the feature similarity between nodes. We then combine these two attentions to obtain a hyperbolic attention that weights the relevance between all connected nodes. We conduct extensive experiments on five real-world networks and demonstrate that our model consistently and significantly outperforms other state-of-the-art methods. For example, on the Cora network, our model achieves an accuracy of 83.1 (± 0.4) on node classification tasks, which is 1.6% higher than the best baseline method in Euclidean space.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Data availability

All data generated or analysed during this study are included in these published articles [ 32 , 45 , 46 , 47 ], and can be downloaded from https://pytorch-geometric.readthedocs.io/en/latest/modules/datasets.html.

Bandyopadhyay S, Maulik U, Holder LB et al (2005) Advanced methods for knowledge discovery from complex data. Springer, Berlin

Book Google Scholar

Hamilton W, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. In: Proceedings of advances in neural information processing systems (NIPS)

Gilmer J, Schoenholz SS, Riley PF, et al (2017) Neural message passing for quantum chemistry. In: Proceedings of international conference on machine learning (ICML), PMLR, pp 1263–1272

Gori M, Monfardini G, Scarselli F (2005) A new model for learning in graph domains. In: Proceedings of international joint conference on neural networks (IJCNN), pp 729–734. https://doi.org/10.1109/IJCNN.2005.1555942

Li Y, Ji Y, Li S, et al (2021) Relevance-aware anomalous users detection in social network via graph neural network. In: Proceedings of international joint conference on neural networks (IJCNN), IEEE, pp 1–8. https://doi.org/10.1109/IJCNN52387.2021.9534136

Guo Z, Yu K, Jolfaei A et al (2022) Mixed graph neural network-based fake news detection for sustainable vehicular social networks. IEEE Trans Intell Transp Syst. https://doi.org/10.1109/TITS.2022.3185013

Article Google Scholar

Jha K, Saha S, Singh H (2022) Prediction of protein-protein interaction using graph neural networks. Sci Rep 12(1):1–12. https://doi.org/10.1038/s41598-022-12201-9

Réau M, Renaud N, Xue LC et al (2023) Deeprank-GNN: a graph neural network framework to learn patterns in protein-protein interfaces. Bioinformatics 39(1):btac759

Gao X, Feng F, Huang H et al (2022) Food recommendation with graph convolutional network. Inf Sci 584:170–183. https://doi.org/10.1016/j.ins.2021.10.040

Chen W, Jiang M, Zhang WG et al (2021) A novel graph convolutional feature based convolutional neural network for stock trend prediction. Inf Sci 556:67–94. https://doi.org/10.1016/j.ins.2020.12.068

Article MathSciNet Google Scholar

Peng H, Du B, Liu M et al (2021) Dynamic graph convolutional network for long-term traffic flow prediction with reinforcement learning. Inf Sci 578:401–416. https://doi.org/10.1016/j.ins.2021.07.007

Zhao L, Song Y, Zhang C et al (2019) T-gcn: a temporal graph convolutional network for traffic prediction. IEEE Trans Intell Transp Syst 21(9):3848–3858. https://doi.org/10.1109/TITS.2019.2935152

Serrano MA, Krioukov D, Boguná M (2008) Self-similarity of complex networks and hidden metric spaces. Phys Rev Lett 100(7):078701. https://doi.org/10.1103/physrevlett.100.078701

Krioukov D, Papadopoulos F, Kitsak M et al (2010) Hyperbolic geometry of complex networks. Phys Rev E 82(3):036106. https://doi.org/10.1103/PhysRevE.82.036106

Boguna M, Bonamassa I, De Domenico M et al (2021) Network geometry. Nat Rev Phys 3(2):114–135. https://doi.org/10.1038/s42254-020-00264-4

Sala F, De Sa C, Gu A, et al (2018) Representation tradeoffs for hyperbolic embeddings. In: Proceedings of international conference on machine learning (ICML), PMLR, pp 4460–4469

Nickel M, Kiela D (2018) Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In: Proceedings of international conference on machine learning (ICML), PMLR, pp 3779–3788

Zheng M, García-Pérez G, Boguñá M et al (2021) Scaling up real networks by geometric branching growth. Proc Natl Acad Sci 118(21):e2018994118. https://doi.org/10.1073/pnas.2018994118

Zhou M, Yang M, Xiong B, et al (2023) Hyperbolic graph neural networks: A tutorial on methods and applications. In: Proceedings of international conference on knowledge discovery and data mining (SIGKDD), pp 5843–5844

Yang M, Zhou M, Li Z, et al (2022) Hyperbolic graph neural networks: a review of methods and applications. arXiv preprint arXiv:2202.13852

Peng W, Varanka T, Mostafa A et al (2021) Hyperbolic deep neural networks: a survey. IEEE Trans Pattern Anal Mach Intell. https://doi.org/10.1109/TPAMI.2021.3136921

Ungar AA (2001) Hyperbolic trigonometry and its application in the Poincaré ball model of hyperbolic geometry. Comput Math Appl 41(1–2):135–147. https://doi.org/10.1016/S0898-1221(01)85012-4

Ungar AA (2008) A gyrovector space approach to hyperbolic geometry. Synth Lect Math Stat 1(1):1–194. https://doi.org/10.1007/978-3-031-02396-5

Topping J, Di Giovanni F, Chamberlain BP, et al (2022) Understanding over-squashing and bottlenecks on graphs via curvature. In: International conference on learning representations (ICLR)

Yang M, Zhou M, Pan L, et al (2023) $\kappa$ hgcn: Tree-likeness modeling via continuous and discrete curvature learning. In: Proceedings of international conference on knowledge discovery and data mining (SIGKDD), pp 2965–2977

Chami I, Ying Z, Ré C, et al (2019) Hyperbolic graph convolutional neural networks. In: Proceedings of advances in neural information processing systems (NIPS)

Lou A, Katsman I, Jiang Q, et al (2020) Differentiating through the fréchet mean. In: Proceedings of international conference on machine learning (ICML), PMLR, pp 6393–6403

Papadopoulos F, Kitsak M, Serrano M et al (2012) Popularity versus similarity in growing networks. Nature 489(7417):537–540. https://doi.org/10.1038/nature11459

García-Pérez G, Allard A, Serrano MÁ et al (2019) Mercator: uncovering faithful hyperbolic embeddings of complex networks. New J Phys 21(12):123033. https://doi.org/10.1088/1367-2630/ab57d2

Jankowski R, Allard A, Boguñá M et al (2023) The d-mercator method for the multidimensional hyperbolic embedding of real networks. Nat Commun 14(1):7585

Veličković P, Cucurull G, Casanova A, et al (2018) Graph attention networks. arXiv preprint arXiv:1710.10903 . https://doi.org/10.48550/arXiv.1710.10903

Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 https://doi.org/10.48550/arXiv.1609.02907

Niepert M, Ahmed M, Kutzkov K (2016) Learning convolutional neural networks for graphs. In: Proceedings of international conference on machine learning (ICML), PMLR, pp 2014–2023

Liu Q, Nickel M, Kiela D (2019) Hyperbolic graph neural networks. In: Proceedings of advances in neural information processing systems (NIPS)

Fu X, Li J, Wu J, et al (2021) ACE-HGNN: Adaptive curvature exploration hyperbolic graph neural network. In: Proceedings of international conference on data mining (ICDM), IEEE, pp 111–120. https://doi.org/10.1109/icdm51629.2021.00021

Zhang Y, Wang X, Shi C et al (2021) Hyperbolic graph attention network. IEEE Trans Big Data. https://doi.org/10.1109/TBDATA.2021.3081431

Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512. https://doi.org/10.1126/science.286.5439.509

Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’networks. Nature 393(6684):440–442. https://doi.org/10.1038/30918

Krioukov D, Papadopoulos F, Vahdat A et al (2009) Curvature and temperature of complex networks. Phys Rev E 80(3):035101. https://doi.org/10.1103/physreve.80.035101

Muscoloni A, Cannistraci CV (2018) A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities. New J Phys 20(5):052002. https://doi.org/10.1088/1367-2630/aac06f

Zuev K, Boguná M, Bianconi G et al (2015) Emergence of soft communities from geometric preferential attachment. Sci Rep 5(1):1–9. https://doi.org/10.1038/srep09421

García-Pérez G, Serrano M, Boguñá M (2018) Soft communities in similarity space. J Stat Phys 173(3):775–782. https://doi.org/10.1007/s10955-018-2084-z

Papadopoulos F, Psomas C, Krioukov D (2014) Network mapping by replaying hyperbolic growth. IEEE/ACM Trans Netw 23(1):198–211. https://doi.org/10.1109/TNET.2013.2294052

Bläsius T, Friedrich T, Krohmer A et al (2018) Efficient embedding of scale-free graphs in the hyperbolic plane. IEEE/ACM Trans Netw 26(2):920–933. https://doi.org/10.1109/TNET.2018.2810186

Sen P, Namata G, Bilgic M et al (2008) Collective classification in network data. AI Mag 29(3):93–93. https://doi.org/10.1609/aimag.v29i3.2157

Namata G, London B, Getoor L, et al (2012) Query-driven active surveying for collective classification. In: Proceedings of international workshop on mining and learning with graphs, p 1

Shchur O, Mumme M, Bojchevski A, et al (2018) Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 . https://doi.org/10.48550/arXiv.1811.05868

Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: Online learning of social representations. In: Proceedings of international conference on knowledge discovery and data mining (SIGKDD), pp 701–710. https://doi.org/10.1145/2623330.2623732

Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks. In: Proceedings of international conference on knowledge discovery and data mining (SIGKDD), pp 855–864. https://doi.org/10.1145/2939672.2939754

Zeng H, Zhou H, Srivastava A, et al (2019) Graphsaint: graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931 https://doi.org/10.48550/arXiv.1907.04931

Li H, Cao J, Zhu J et al (2022) Curvature graph neural network. Inf Sci 592:50–66

Yang Z, Cohen W, Salakhudinov R (2016) Revisiting semi-supervised learning with graph embeddings. In: Proceedings of international conference on machine learning (ICML), PMLR, pp 40–48

Van der Maaten L, Hinton G (2008) Visualizing data using t-SNE. J Mach Learn Res 9(11)

Download references

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant Numbers: 61672298, 61873326, 62203229, and 62373197); in part by Major Project of Philosophy and Social Science Research in Colleges and Universities in Jiangsu Province (Grant Numbers: 2018SJZDI142); in part by Natural Science Foundation of Jiangsu Province (Grant Numbers: BK20200758); and in part by Postgraduate Research & Practice Innovation Program of Jiangsu Province (Grant Numbers: KYCX23_1045).

Author information

Authors and affiliations.

School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing, 210023, Jiangsu, China

Hongbo Qu, Minglei Zhang & Ruqi Li

College of Automation and College of Artificial Intelligence, Nanjing University of Posts and Telecommunications, Nanjing, 210023, Jiangsu, China

Yu-Rong Song & Guo-Ping Jiang

School of Modern Posts, Nanjing University of Posts and Telecommunications, Nanjing, 210023, Jiangsu, China

You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yu-Rong Song .

Ethics declarations

Conflict of interest.

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Qu, H., Song, YR., Zhang, M. et al. Ha-gnn: a novel graph neural network based on hyperbolic attention. Neural Comput & Applic (2024). https://doi.org/10.1007/s00521-024-09689-9

Download citation

Received : 30 March 2023

Accepted : 25 March 2024

Published : 21 April 2024

DOI : https://doi.org/10.1007/s00521-024-09689-9

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Graph neural networks
Machine learning
Hyperbolic space
Complex network
Network geometry
Find a journal
Publish with us
Track your research

IMAGES

Graphs in Data Structure: Overview, Types and More [Updated]
Graphs in Data Structure: Overview, Types and More [Updated]
Graph Data Structure
Data Structure Fundamentals
Graphs in Data Structure
An Introduction To Graph Data Structure

COMMENTS

Introduction to Graphs
A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More 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).
10.1. Chapter Introduction: Graphs
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. ... 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 ...
PDF Chapter 9 Graphs: Deﬁnition, Applications, Representation
Learn the basics of graphs, a powerful abstraction for expressing relationships between pairs of items, and how to represent them with data structures. Explore the terminology, types, and examples of graphs, such as directed and undirected graphs, vertices, edges, neighbors, and paths.
Graph (abstract data type)
Common data structures for graph representation Adjacency list Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident ...
A Gentle Introduction to Data Structures: How Graphs Work
How Graphs Work. Graphs are a powerful and versatile data structure that easily allow you to represent real life relationships between different types of data (nodes). There are two main parts of a graph: The vertices (nodes) where the data is stored i.e. the numbers in the image on the left.
Graph Data Structures
2.1. Complexities. With graph storage data structures, we usually pay attention to the following complexities: Space Complexity: the approximate amount of memory needed to store a graph in the chosen data structure. Time Complexity. Connection Checking Complexity: the approximate amount of time needed to find whether two different nodes are ...
Representing Graph Data Structures
Learn how to store and navigate graphs using three common data structures: edge list, adjacency matrix, and adjacency list. Compare their space and adjacency complexities and see examples of graphs and their representations.
12.1: Representing a Graph by a Matrix
The AdjacencyMatrix data structure is also commonly used because algebraic operations on the matrix $\mathtt{a}$ can be used to efficiently compute properties of the graph $G$. This is a topic for a course on algorithms, but we point out one such property here: If we treat the entries of $\mathtt{a}$ as integers (1 for \(\mathtt{true ...
9.2: Data Structures for Graphs
Here are three different data structures that can be employed to represent graphs. Adjacency Matrix: As we saw in Chapter 6, the information about edges in a graph can be summarized with an adjacency matrix, G, where Gij = 1 if and only if vertex i is connected to vertex j in the graph. Note that this is the same as the adjacency matrix for a ...
Adjacency List (With Code in C, C++, Java and Python)
Learn how to represent a graph as an array of linked lists using an adjacency list data structure. See the structure, pros and cons, and code examples of adjacency list in C, C++, Java and Python.
Graphs Data Structure : Array and Linked representation
Representation of Graphs. There are two ways of representing a graph: According to their names, we use lists in the case of adjacency-list representation and a matrix (2D array) in the case of adjacency matrix representation. The way in which we are going to represent our graph depends on the task we have to perform.
Graphs
🎯 Objective: Learn the fundamental concept of a Graph data structure and implement it in Java. 📝 Table of Contents Introduction to Graphs Types of Graphs Graph Representation Java Implementation Summary 1️⃣ Introduction to Graphs Graphs are one of the most versatile data structures used in computer science. A graph consists of nodes, often called
Graph Representation in Data Structure
A graph is a type of data structure that represents a collection of objects called vertices or nodes that are connected by an edge network. A graph's nodes typically represent entities, and its edges represent relationships or connections between two nodes. Social networks, road networks, and computer networks are all examples of graphs used ...
Graph in Data Structure and Algorithm
Representing Graphs. A graph can be represented using 3 data structures- adjacency matrix, adjacency list and adjacency set. An adjacency matrix can be thought of as a table with rows and columns. The row labels and column labels represent the nodes of a graph. An adjacency matrix is a square matrix where the number of rows, columns and nodes are the same.
Terminology and Representations of Graphs
This post discusses the basic definitions in terminologies associated with graphs and covers the adjacency list and adjacency matrix representations of the graph data structure. What is a Graph? A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes and a collection of pairs of vertices from V, known as edges of a graph ...
Graph Representation: Adjacency List and Matrix
Adjacency lists are the right data structure for most applications of graphs. Adjacency lists, in simple words, are the array of linked lists. We create an array of vertices and each entry in the array has a corresponding linked list containing the neighbors.
DSA Graphs
Graphs. A Graph is a non-linear data structure that consists of vertices (nodes) and edges. A vertex, also called a node, is a point or an object in the Graph, and an edge is used to connect two vertices with each other. Graphs are non-linear because the data structure allows us to have different paths to get from one vertex to another, unlike ...
Graphs Data Structures: Understanding Utility and Use Cases ...
Graphs, a fundamental data structure in computer science, have a wide range of applications across various domains. They offer a versatile way of representing relationships and connections between…
Graph Representation
Learn how to store a graph into the computer's memory using two techniques: sequential representation (adjacency matrix) and linked list representation (adjacency list). See the advantages, disadvantages, and implementations of each technique with examples and code snippets in C.
Graph Representation Tutorials & Notes
Graphs are mathematical structures that represent pairwise relationships between objects. A graph is a flow structure that represents the relationship between various objects. It can be visualized by using the following two basic components: Nodes: These are the most important components in any graph. Nodes are entities whose relationships are ...
Graphs in Data Structure: Types, Representation, Operations
Graph Representation in Data Structure. Below are the two most common ways of representing graphs in data structure: 1. Adjacency Matrix. An Adjacency Matrix is the simplest way to represent a graph. It is a 2D array of V x V vertices, with each row and column representing a vertex. The matrix consists of "0" or "1". 0 depicts that ...
Ha-gnn: a novel graph neural network based on hyperbolic ...
Graph neural networks (GNNs) are powerful tools for data mining on graph-structured data in various domains, such as social science, finance, and biology. However, most existing GNNs operate in Euclidean space and may fail to preserve the intrinsic network properties, such as self-similarity and hierarchy, that characterize many real-world graphs. Hyperbolic graph neural networks (HGNNs ...
CORE: Data Augmentation for Link Prediction via Information ...
Link prediction (LP) is a fundamental task in graph representation learning, with numerous applications in diverse domains. However, the generalizability of LP models is often compromised due to the presence of noisy or spurious information in graphs and the inherent incompleteness of graph data. To address these challenges, we draw inspiration from the Information Bottleneck principle and ...

BFS and DFS on Graph

Cycle in a Graph

Shortest Paths in Graph

Minimum Spanning Tree in Graph

Topological Sorting in Graph

Connectivity of Graph

Maximum flow in a Graph

Some must do problems on Graph

Introduction to Graphs – Data Structure and Algorithm Tutorials

Components of a Graph

Types Of Graph

2. Trivial Graph

3. Undirected Graph

4. Directed Graph

5. Connected Graph

6. Disconnected Graph

7. Regular Graph

8. Complete Graph

9. Cycle Graph

10. Cyclic Graph

11. Directed Acyclic Graph

12. Bipartite Graph

Tree v/s Graph

Representation of Graphs

Adjacency Matrix

Comparison between Adjacency Matrix and Adjacency List

Basic Operations on Graphs

Usage of graphs

Real-Life Applications of Graph

Following are the real-life applications:

When to use Graphs:

Advantages and Disadvantages:

Disadvantages:

More Resources of Graph

Please Login to comment...

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Data Structures and Algorithms

10. 1. Chapter Introduction: Graphs ¶

10. 1.1.1. Graph Representations ¶

10. 1.2. Graph Terminology Questions ¶

A Gentle Introduction to Data Structures: How Graphs Work

How Graphs Work

Building a social network using graphs

A time complexity analysis on the graph methods as an adjacency list

Time for a quick recap

Further Reading

12.1: Representing a Graph by a Matrix

9.2: Data Structures for Graphs

Basic Data Structures

Popular Tutorials

Data Structures (I)

Data Structures (II)

Tree based DSA (I)

Tree based DSA (II)

Graph based DSA

Adjacency List

Sorting and Searching Algorithms

Greedy Algorithms

Other Algorithms

DSA Tutorials

Table of Contents

Related Tutorials

Graphs Data Structures

Types of Graphs

Cyclic and Acyclic Graph

Weighted and Unweighted Graph

Dense and Sparse Graph

Simple and Non-simple Graph

Connected and Disconnected Graph

Complete Graph

Representation of Graphs

Adjacency-matrix Representation

Adjacency-list Representation

📝 Table of Contents

1️⃣ Introduction to Graphs

Why use Graphs?

2️⃣ Types of Graphs

3️⃣ Graph Representation

4️⃣ Java Implementation