graph representation in adjacency list

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.

Graph Representations - Adjacency Matrix and List

There are two ways in which we represent graphs, these are:

Adjacency Matrix

Adjacency list.

Both these have their advantages and disadvantages. In this tutorial, we will cover both of these graph representation along with how to implement them.

Adjacency matrix representation makes use of a matrix (table) where the first row and first column of the matrix denote the nodes (vertices) of the graph. The rest of the cells contains either 0 or 1 (can contain an associated weight w if it is a weighted graph).

Each row X column intersection points to a cell and the value of that cell will help us in determining that whether the vertex denoted by the row and the vertex denoted by the column are connected or not. If the value of the cell for v1 X v2 is equal to 1, then we can conclude that these two vertices v1 and v2 are connected by an edge, else they aren't connected at all.

Consider the given graph below:

The graph shown above is an undirected one and the adjacency matrix for the same looks as:

The above matrix is the adjacency matrix representation of the graph shown above. If we look closely, we can see that the matrix is symmetric. Now let's see how the adjacency matrix changes for a directed graph.

For the directed graph shown above the adjacency matrix will look something like this:

Implementation of Adjacency Matrix

The structure ( constructor in Java ) for the adjacency matrix will look something like this:

It should also be noted that we have two class-level variables, like:

We have a constructor above named AdjacencyMatrix which takes the count of the number of the vertices that are present in the graph and then assigns our global vertex variable that value and also creates a 2D matrix of the same size. Now since our structure part is complete, we are simply left with adding the edges together, and the way we do that is:

In the above addEdge function we also assigned 1 for the direction from the destination to the start node, as in this code we looked at the example of the undirected graph, in which the relationship is a two-way process. If it had been a directed graph, then we can simply make this value equal to 0, and we would have a valid adjacency matrix.

Now the only thing left is to print the graph.

The entire code looks something like this:

The output of the above looks like:

Adjacency Matrix : 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0

In the adjacency list representation, we have an array of linked-list where the size of the array is the number of the vertex (nodes) present in the graph. Each vertex has its own linked-list that contains the nodes that it is connected to.

Consider the graph shown below:

The above graph is an undirected one and the Adjacency list for it looks like:

The first column contains all the vertices we have in the graph above and then each of these vertices contains a linked list that in turn contains the nodes that each vertex is connected to. For a directed graph the only change would be that the linked list will only contain the node on which the incident edge is present.

The above graph is a directed one and the Adjacency list for this looks like:

Implementation of Adjacency List

The structure (constructor in Java) for the adjacency list will look something like this:

The above constructor takes the number of vertices as an argument and then assigns the class level variable this value, and then we create an array of LinkedList of the size of the vertices present in the graph. Finally, we create an empty LinkedList for each item of this array of LinkedList.

Now we have laid the foundations and the only thing left is to add the edges together, we do that like this:

We are taking the vertices from which an edge starts and ends, and we are simply inserting the destination vertex in the LinkedList of the start vertex and vice-versa (as it is for the undirected graph).

Node 0 is connected to: 1 Node 1 is connected to: 2 0 Node 2 is connected to: 3 1 Node 3 is connected to: 2

We learned how to represent the graphs in programming, via adjacency matrix and adjacency lists.
← Introduction to Graphs ← PREV
Hash Table → NEXT →

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

Computer science theory

Course: computer science theory > unit 1.

Describing graphs

Representing graphs

Challenge: Store a graph

Adjacency matrices

Adjacency lists, want to join the conversation.

Upvote Button navigates to signup page
Downvote Button navigates to signup page
Flag Button navigates to signup page

Learn Python
Python Lists
Python Dictionaries
Python Strings
Python Functions
Learn Pandas & NumPy
Pandas Tutorials
Numpy Tutorials
Learn Data Visualization
Python Seaborn
Python Matplotlib

Representing Graphs in Python (Adjacency List and Matrix)

January 15, 2024 December 31, 2023

In this tutorial, you’ll learn how to represent graphs in Python using edge lists, an adjacency matrix, and adjacency lists . While graphs can often be an intimidating data structure to learn about, they are crucial for modeling information. Graphs allow you to understand and model complex relationships, such as those in LinkedIn and Twitter (X) social networks.

By the end of this tutorial, you’ll have learned the following:

What graphs are and what their components, nodes, and edges, are
What undirected, directed, and weighted graphs are
How to represent graphs in Python using edge lists, adjacency lists, and adjacency matrices
How to convert between graph representations in Python

Table of Contents

What are Graphs, Nodes, and Edges?

In its simplest explanation, a graph is a group of dots connected by lines. Each of these dots represents things, such as people or places. The lines are used to represent the connections between things. From a technical perspective, these circles are referred to as nodes . Similarly, the lines connecting them are called edges .

For example, we could create a graph of some Facebook relationships. Let’s imagine that we have three friends: Evan, Nik, and Katie. Each of them are friends with one another. We can represent this as a graph as shown below:

This is an example of an undirected graph . This means that the relationship between two nodes occurs in both directions. Because of this, a sample edge may connect Evan and Katie. This edge would be represented by {'Evan', 'Katie'} . Note that we used a set to represent this. In this case, the relationship goes both ways.

Now let’s take a look at another example. Imagine that we’re modeling relationships in X (formerly Twitter). Because someone can follow someone without the other person following them back, we can end up with a relationship like the one shown below.

This is an example of a directed graph . Notice that the edges here are represented as arrows. In this case, Nik and Katie follow one another, but the same isn’t true for the others. Evan follows Katie (but not the other way around). Similarly, Nik follows Evan, but not the other way around.

In this case, while our nodes remain the same as {'Nik', 'Evan', 'Katie'} , our edge list now has a different meaning. In fact, it’s easier to use a list of tuples to represent this now, where the first value is the starting node and the second is the end node. This would look like this: [('Nik', 'Katie'), ('Katie', 'Nik'), ('Evan', 'Katie'), ('Nik', 'Evan')] .

Let’s now dive a little further into the different types of graphs and how they can be represented in Python.

Want to learn how to traverse these graphs? Check out my in-depth guides on breadth-first search in Python and depth-first search in Python .

Understanding Graph Data Structure Representations

In this tutorial, we’ll explore three of the most fundamental ways in which to represent graphs in Python. We’ll also explore the benefits and drawbacks of each of these representations. Later, we’ll dive into how to implement these for different types of graphs and how to create these in Python.

One of the ways you have already seen is called an edge list . The edge list lists our each of the node-pair relationships in a graph. The list can include additional information, such as weights, as you’ll see later on in this tutorial.

In Python, edge lists are often represented as lists of tuples . Let’s take a look at an example:

In the code block above, we can see a sample edge list. In this case, each pair represents an unweighted relationship (since no weight is given) between two nodes. In many cases, edge lists for undirected graphs omit the reverse pair (so ('A', 'B') represents both sides of the relationship, for example).

Another common graph representation is the adjacency matrix . Adjacency matrices are often represented as lists of lists, where each list represents a node. The list’s items represent whether an edge exists between the node and another node.

Let’s take a look at what this may look like:

In the example above, we can see all the node’s connections. For example, node 'A' comes first. We can see that it has an edge only with node 'B' . This is represented by 1, where all other nodes are 0.

One of the key benefits of an adjacency matrix over an edge list is that we can immediately see any node’s neighbors, without needing to iterate over the list.

However, adjacency matrices are often very sparse, especially for graphs with few edges. Because of this, the preferred method is the adjacency list.

An adjacency list is a hash map that maps each node to a list of neighbors. This combines the benefits of both the edge list and the adjacency matrix, by providing a contained structure that allows you to easily see a node’s neighbors.

In Python, adjacency lists are often represented as dictionaries . Each key is the node label and the value is either a set or a list of neighbors. Let’s take a look at an example:

Let’s quickly summarize the three main structures for different graph types:

Now that you have a good understanding of how graphs can be represented, let’s dive into some more practical examples by exploring different graph types.

Understanding Undirected Graph Data Structures

As we saw earlier, an undirected graph has edges that connect nodes without specifying direction, because the edges are bidirectional. In the edge list representation an edge connecting ('A', 'B') is the same as that connecting ('B', 'A') .

Let’s take a look at a more complete example of what this can look like. We’ll use nodes labeled A through F for this and look at different ways in which this graph can be represented.

We can see that in the image above all nodes are connected by lines without heads. This indicates that the graph is undirected and that the relationship is bidirectional. As an edge list, this graph would be represented as shown below:

In this case, it’s important to note that the graph is undirected. Without this knowledge, half the relationships would be lost. Because of this, it can sometimes be helpful to be more explicit and list out all possible relationships, as shown below:

In the code block above, we’re repeating each relationship for each node-pair relationship. While this is more explicit, it’s also redundant.

One problem with edge lists is that if we want to see any node’s neighbors, we have to iterate over the entire list. Because of this, there are different representations that we can use.

Adjacency Matrix for Undirected, Unweighted Graphs

Another common way to represent graphs is to use an adjacency matrix . In Python, these are lists of lists that store the corresponding relationship for each node. For example, our graph has seven nodes. Because of this, the adjacency matrix will have seven lists, each with seven values.

Take a look at the image below to see what our adjacency matrix for our undirected, unweighted graph looks like:

Adjacency Matrix for an undirected unweighted graph

In the image above, we can see our matrix of seven rows and seven values each. The first row shows all the relationships that node 'A' has. We can see that it only connects to the second node, 'B' . In this case, edges are labelled at 1 and non-existent edges are labelled as 0.

One unique property of an adjacency matrix for undirected graphs is that they are symmetrical! If we look along the diagonal, we can see that the values are mirrored.

Let’s take a look at how we can write a function to accept an edge list and return an adjacency matrix in Python:

In the code block above, we created a function that creates an adjacency matrix out of an edge list. The function creates a set out of our nodes and then sorts that set. We then create a matrix that creates a list of lists of 0s for each node in the graph.

The function then iterates over the edges and finds the indices for each node. It adds 1 for each edge it finds. By default, the function assumes an undirected graph; if this is the case, it also adds a 1 for each reverse pair.

When we run the function on a sample edge list, we get the following code back:

Now let’s take a look at adjacency lists for undirected, unweighted graphs.

Adjacency List for Undirected, Unweighted Graphs

For graphs that don’t have many edges, adjacency matrices can become very sparse. Because of this, we can use one of the most common graph representations, the adjacency list . The adjacency list combines the benefits of both the edge list and the adjacency matrix by creating a hash map of nodes and their neighbors.

Let’s take a look at what an adjacency list would look like for an undirected, unweighted graph:

Adjacency List for an undirected, unweighted graph

In Python, we would represent this using a dictionary. Let’s take a look at how we can create a function that accepts an edge list and returns an adjacency list:

This function is a bit simpler than our previous function. We accept both an edge list and whether our graph is directed or not. We then create a dictionary to hold our adjacency list. The iterate over each edge in our list. We check if the starting node exists in our dictionary – if it doesn’t we create it with an empty list. We then append the second node to that list.

Similarly, if the graph is not directed, we do the same thing for the inverse relationship.

Let’s take a look at what this looks like for a sample edge list:

Now that you have a strong understanding of the three representations of unweighted, undirected graphs, let’s take a look at directed graphs in Python.

Understanding Directed Graph Data Structures

Directed graphs, also known as digraphs, are networks where edges between nodes have a defined direction. Unlike undirected graphs, edges in directed graphs are unidirectional, representing a directed relationship from one node (the source) to another node (the target or destination).

Directed graphs can be helpful when modeling one-way relationships, such as one-way streets, task dependencies in project management, or social media followings.

Let’s take a look at what one of these graphs may look like:

We can see that this graph looks very similar to the one that we saw before. However, each edge has a direction on it. In this example, each edge is one-directional. However, directed graphs can also have bi-directional edges.

In this case, we can use an adjacency matrix to represent this graph as well. This is shown in the image below:

Adjacency matrix for a directed unweighted graph

The function that we developed earlier is already built around the concept of directed graphs. In order to use it, we simply need to indicate that the graph is directed. Let’s take a look at what this looks like:

The only change that we made was in calling the function: we modified the default argument of directed=False to True . This meant that the bi-directional pair was not added to our matrix.

Similarly, we can use adjacency lists to represent directed graphs. Let’s take a look at what this would look like:

Adjacency List for a directed, unweighted graph

In the image above, each dictionary key is still represented by the starting node and the list of values is represented by its neighbors.

Similarly, the function we previously created allows us to pass in that we’re working with a directed graph. Let’s see what this looks like:

Similar to our previous example, we only modified the default argument of directed= to True . This allowed us to create an adjacency list for a directed graph.

Now that we’ve covered unweighted graphs, let’s dive into weighted graphs, which add additional information to our graph.

Understanding Weighted Graph Data Structures

Weighted directed graphs expand upon directed graphs by incorporating edge weights, assigning a value or cost to each directed edge between nodes. In this graph type, edges not only depict directional relationships but also carry additional information in the form of weights, indicating the strength, distance, cost, or any other relevant metric associated with the connection from one node to another.

These weights add an extra layer of complexity and significance, allowing the representation of various scenarios where the intensity or cost of relationships matters. Weighted directed graphs find applications in diverse fields such as logistics, transportation networks, telecommunications, and biology, where the weights might represent distances between locations, communication costs, strengths of interactions, or genetic similarities.

Let’s use our previous example graph and add some weights to it:

We can represent these graphs as adjacency matrices as well. In this case, rather than using the default value of 1, we represent each node by the weight that it has. Take a look at the image below for how this representation works:

Adjacency Matrix for a directed, weighted graph

To convert an edge list to an adjacency matrix using Python, we only have to make a small adjustment to our function. Let’s take a look at what this looks like:

In this case, we added a second optional parameter that indicates whether a graph is weighted or not. We use the ternary operator to assign the weight if the graph is weighted, otherwise use the default value of 1.

In an adjacency list, the keys continue to represent the nodes of the graph. The values are now lists of tuples that contain the end node and the weight for that relationship. Take a look at the image below to see what this looks like:

Adjacency List for a directed, weighted graph

We can make small modifications to our earlier function to allow for weighted graphs. Let’s see what this looks like:

In the code block above, we modified our function to accept a third argument, indicating whether the graph is weighted or not. We then added a number of if-else statements to get the weight from our edge list if the edge list has weights in it.

We can see that the function returns a dictionary that contains lists of tuples, which represent the end node and the weight of the relationship.

Understanding how to represent graphs in Python is essential for anyone working with complex relationships and networks. In this tutorial, we explored three fundamental ways to represent graphs: edge lists, adjacency matrices, and adjacency lists. Each method has its strengths and trade-offs, catering to different scenarios and preferences.

We began by dissecting what graphs, nodes, and edges are, showcasing examples of undirected and directed graphs. From there, we delved into the details of each representation method:

Edge Lists: Simple and intuitive, representing relationships between nodes as tuples.
Adjacency Matrices: Efficient for determining connections between nodes but can become sparse in large, sparse graphs.
Adjacency Lists: Efficient for sparse graphs, offering quick access to a node’s neighbors.

We explored these representations for different graph types, including undirected, directed, and weighted graphs. For each type, we demonstrated how to convert between representations using Python functions.

Understanding these representations equips you to handle diverse scenarios, from modeling social networks to logistical networks, project management, and more. Graphs are a powerful tool for modeling relationships, and grasping their representations in Python empowers you to analyze and work with complex interconnected data effectively.

The official Python documentation also has useful information on building graphs in Python .

Nik Piepenbreier

Nik is the author of datagy.io and has over a decade of experience working with data analytics, data science, and Python. He specializes in teaching developers how to use Python for data science using hands-on tutorials. View Author posts

Graph Representation using Adjacency Lists

Performance Comparison of Adjacency Matrix vs Adjacency List
Topological Sort of a Directed Acyclic Graph
Minimum Spanning Trees
Shortest Path Algorithms - Single Source Shortest Path
Shortest Path Algorithms - All-Pairs Shortest Path
Graph Traversals - Depth First Search Algorithm
Graph Traversals - Breadth First Search Algorithm

Related Books

Priority Queue

Introduction to Recursion and Backtracking

Sorting Algorithms in Computer Science

Patterns for Beginning Programmers

Applied Functional Programming Tutorial

Books / Graph Algorithms / Chapter 3

In the previous chapter, we learned that graphs can be represented using Adjacency Matrix. In this chapter, we’ll look at another technique of representing graphs called Adjacency Lists.

By far the most common data structure for storing graphs is the adjacency list because its the most efficient. An adjacency list is an array of lists , each containing the neighbors of one of the vertices (or the out-neighbors if the graph is directed.) In other words, an adjacency list is a linear array with an entry for each vertex, such that each entry is a pointer to a list of vertices adjacent to that vertex.

Figure 1: An adjacency list for our example graph

For undirected graphs, each edge uv is stored twice, once in u’s neighbor list and once in v’s neighbor list; for directed graphs, each edge u->v is stored only once, in the neighbor list of the tail u. For both types of graphs, the overall space required for an adjacency list is O(V + E).

There are several different ways to represent these neighbor lists, but the standard implementation uses a simple singly-linked list. The resulting data structure allows us to list the (out-)neighbors of a node v in O(1 + deg(v)) time; just scan v’s neighbor list. Similarly, we can determine whether uv is an edge in O(1 + deg(u)) time by scanning the neighbor list of u. For undirected graphs, we can improve the time to O(1 + min{deg(u), deg(v)}) by simultaneously scanning the neighbor lists of both u and v, stopping either when we locate the edge or when we fall of the end of a list.

Note: Linked lists are not the only data structure we could use; any other structure that supports searching, listing, insertion, and deletion will do.

Adjacency Lists and Weighted Graphs

If the graph is a weighted graph, then the node for each edge in the list would have a member variable that stores the weight.

Adjacency List in Java

Here’s an example of Adjacency List in Java using LinkedList s. In this example, we have 4 nodes: A, B, C and D.

A has an edge to B.
B has edges to C and D.
C has an edge to D.
D has no edges.

This prints:

Licenses and Attributions

Original Content CC-BY-SA 4.0 International

This work is a derivative of "CSci 335 Software Design and Analysis" by Prof. Stewart Weiss, used under CC BY-SA 4.0.
This work is a derivative of "Algorithms" by Jeff Erickson used under Creative Commons Attribution 4.0 International license. Original copyright notice: Copyright 2019 Jeff Erickson. This work is available under a Creative Commons Attribution 4.0 International License.

Speak Your Mind Cancel reply

Graphs and graph representations

vertices and edges
directed vs undirected graphs
labeled graphs
adjacency and degree
adjacency-matrix and adjacency-list representations
paths and cycles
topological sorting
more graph problems: shortest paths, graph coloring

A graph is a highly useful mathematical abstraction. A graph consists of a set of vertices (also called nodes ) and a set of edges (also called arcs ) connecting those vertices. There are two main kinds of graphs: undirected graphs and directed graphs . In a directed graph (sometimes abbreviated as digraph ), the edges are directed: that is, they have a direction, proceeding from a source vertex to a sink (or destination ) vertex. The sink vertex is a successor of the source, and the the source is a predecessor of the sink. In undirected graphs, the edges are symmetrical.

Uses of graphs

Graphs are a highly useful abstraction in computer science because so many important problems can be expressed in terms of graphs. We have already seen a number of graph structures: for example, the objects in a running program form a directed graph in which the vertices are objects and references between objects are edges. To implement automatic garbage collection (which discards unused objects), the language implementation uses a algorithm for graph reachability .

states of games and puzzles, which are vertices connected by edges that are the legal moves in the game,
state machines, where the states are vertices and the transitions between states are edges,
road maps, where the vertices are intersections or points along the road and edges are roads connecting those points,
scheduling problems, where vertices represent events to be scheduled and edges might represent events that cannot be scheduled together, or, depending on the problem, edges that must be scheduled together,
and in fact, any binary relation ρ can be viewed as a directed graph in which the relationship x ρ y corresponds to an edge from vertex x to vertex y.

What is the value of having a common mathematical abstraction like graphs? One payoff is that we can develop algorithms that work on graphs in general. Once we realize we can express a problem in terms of graphs, we can consult a very large toolbox of efficient graph algorithms, rather than trying to invent a new algorithm for the specific domain of interest.

On the other hand, some problems over graphs are known to be intractable to solve in a reasonable amount of time (or at least strongly suspected to be so). If we can show that solving the problem we are given is at least as hard as solving one of these

Vertices and edges

The vertices V of a graph are a set; the edges E can be viewed as set of ordered pairs (v 1 , v 2 ) representing an edge with source vertex v 1 and sink vertex v 2 .

If the graph is undirected, then for each edge (v 1 , v 2 ), the edge set also includes (v 1 , v 2 ). Alternatively, we can view the edges in an undirected graph as a set of sets of edges {v 1 , v 2 }.

Adjacency and degree

Two vertices v and w are adjacent , written v ~ w, if they are connected by an edge. The degree of a vertex is the total number of adjacent vertices. In a directed graph, we can distinguish between outgoing and incoming edges. The out-degree of a vertex is the number of outgoing edges and the in-degree is the number of incoming edgs.

The real value of graphs is obtained when we can use them to organize information. Both edges and vertices of graphs can have labels that carry meaning about an entity represented by a vertex or about the relationship between two entities represented by an edge. For example, we might encode information about three cities, Syracuse, Ithaca, and Binghamton as edge and vertex labels in the following undirected graph:

Here, the vertices are labeled with a pair containing the name of the city and its population. The edges are labeled with the distance between the cities.

A graph in which the edges are labeled with numbers is called a weighted graph . Of course, the labels do not have to represent weight; they might stand for distance betweenvertices, or the probability of transitioning from one state to another, or the similarity between two vertices, etc.

Graph representations

There is more than one way to represent a graph in a computer program. Which representation is best depend on what graphs are being represented and how they are going to be used. Let us consider the following weighted directed graph and how we might represent it:

Adjacency matrix

An adjacency matrix represents a graph as a two-dimensional array. Each vertex is assigned a distinct index in [0, |V|). If the graph is represented by the 2D array m , then the edge (or lack thereof) from vertex i to vertex j is recorded at m[i][j] .

The graph structure can be represented by simplying storing a boolean value at each array index. For example, the edges in the directed graph above are represented by the true (T) values in this matrix:

More compact bit-level representations for the booleans are also possible.

Typically there is some information associated with each edge; instead of a boolean, we store that information into the corresponding array entry:

The space required by the adjacency matrix representation is O(V 2 ), so adjacency matrices can waste a lot of space if the number of edges |E| is O(V). Such graphs are said to be sparse . For example, graphs in which in-degree or out-degree are bounded by a constant are sparse. Adjacency matrices are asymptotically space-efficient, however, when the graphs they represent are dense ; that is, |E| is O(V 2 ).

The adjacency matrix representation is time -efficient for some operations. Testing whether there is an edge between two vertices can clearly be done in constant time. However, finding all incoming edges to a given vertex, or finding all outgoing edges, takes time proportional to the number of vertices, even for sparse graphs.

Undirected graphs can be represented with an adjacency matrix too, though the matrix will be symmetrical around the matrix diagonal. This symmetry invariant makes possible some space optimizations.

Adjacency list representation

Since sparse graphs are common, the adjacency list representation is often preferred. This representation keeps track of the outgoing edges from each vertex, typically as a linked list. For example, the graph above might be represented with the following data structure:

Adjacency lists are asymptotically space-efficient because they only use space proportional to the number of vertices and the number of edges. We say that they require O(V+E) space.

Finding the outgoing edges from a vertex is very efficient in the adjacency list representation too; it requires time proportional to the number of edges found. However, finding the incoming edges to a vertex is not efficient: it requires scanning the entire data structure, requiring O(V+E) time.

When it is necessary to be able to walk forward on outgoing edges and backward on incoming edges, a good approach is to maintain two adjacency lists, one representing the graph as above and one corresponding to the dual (or transposed ) graph in which all edges are reversed. That it, if there is a an edge a→b in the original graph, there is an edge b→a in the transposed graph. Of course, an invariant must be maintained between the two adjacency list representations.

Testing whether there is an edge from vertex i to vertex j requires scanning all the outgoing edges, taking O(V) time in the worse case. If this operation needs to be fast, the linked list can be replaced with a hash table. For example, we might implement the graph using this Java representation, which preserves the asympotic space efficiency of adjacency lists while also supporting queries for particular edges:

Paths and cycles

Following a series of edges from a starting vertex creates a walk through the graph, a sequence of vertices (v 0 ,...,v p ) where there is an edge from v i-1 to v i for all i between 1 and p. The length of the walk is the number of edges followed (that is, p). If no vertex appears twice in the walk, except that possibly v 0 = v n , the walk is called a path . If there are no repeating vertices, it is a simple path . If the first and last vertices are the same, the path is a cycle .

Some graphs have no cycles. For example, linked lists and trees are both examples of graphs in which there are no cycles. They are directed acyclic graphs , abbreviated as DAGs. In trees and linked lists, each vertex has at most one predecessor; in general, DAG vertices can have more than one predecessor.

Topological sorting

One use of directed graphs is to represent an ordering constraint on vertices. We use an edge from x to y to represent the idea that “x must happen before y”. A topological sort of the vertices is a total ordering of the vertices that is consistent with all edges. A graph can be topologically sorted only if it has no cycles; it must be a DAG.

Topological sorts are useful for deciding in what order to do things. For example, consider the following DAG expressing what we might call the “men's informal dressing problem”:

A valid plan for getting dressed is a topological sort of this graph, and in fact any topological sort is in principle a workable way to get dressed. For example, the ordering (pants, shirt, belt, socks, tie, jacket, shoes) is consistent with the ordering on all the graph edges. Less conventional strategies are also workable, such as (socks, pants, shoes, shirt, belt, tie, jacket).

Does every DAG have a topological sort? Yes. To see this, observe that every finite DAG must have a vertex with in-degree zero. To find such a vertex, we start from an arbitrary vertex in the graph and walk backward along edges until we reach a vertex with zero in-degree. We know that the walk must generate a simple path because there are no cycles in the graph. Therefore, the walk must terminate because we run out of vertices that haven't already been seen along the walk.

This gives us an (inefficient) way to topologically sort a DAG:

Since finding the 0 in-degree node takes O(V) time, this algorithm takes O(V 2 ) time. We can do better, as we'll see shortly.

Reachability

One vertex is reachable from another if there is a path from one to the other. Determining which vertices are reachable from a given vertex is useful and can be done efficiently, in linear time.

Shortest paths

For example, if a road map is represented as a graph with vertices representing intersections and edges representing road segments, the shortest-path problem can be used to find short routes. There are several variants of the problem, depending on whether one is interested in the distance from a given root vertex or in the distances between all pairs of vertices. If negative-weight edges exist, these problems become harder and different algorithms (e.g., Bellman–Ford) are needed.

Hamiltonian cycles and the traveling salesman problem

The problem of finding the longest path between two nodes in a graph is, in general, intractable. It is related to some other important problems. A Hamiltonian path is one that visits every vertex in a graph. The ability to determine whether a graph contains a Hamiltonian path (or a Hamiltonian cycle) would be useful, but in general this is an intractable problem for which the best exact algorithms require exponential-time searching.

A weighted version of this problem is the traveling salesman problem (TSP), which tries to find the Hamiltonian cycle with the minimum total weight. The name comes from imagining a salesman who wants to visit every one of a set of cities while traveling the least possible total distance. This problem is at least as hard as finding Hamiltonian cycles. However, finding a solution that is within a constant factor (e.g., 1.5) of optimal can be done in polynomial time with some reasonable assumptions. In practice, there exist good heuristics that allow close-to-optimal solutions to TSP to be found even for large problem instances.

Graph coloring

Imagine that we want to schedule exams into k time slots such that no student has two exams at the same time. We can represent this problem using an undirected graph in which the exams are vertices. Exam V 1 and exam V 2 are connected by an edge if there is some student who needs to take both exams. We can schedule the exams into the k slots if there is a k-coloring of the graph: a way to assign one of k colors, representing the time slots, to each of the vertices such that no two adjacent vertices are assigned the same color.

The problem of determining whether there is a k-coloring turns out to be intractable. The chromatic number of a graph is the minimum number of colors that can be used to color it; this is of course intractable too. Though the worst case is intractable, in practice, graph colorings close to optimal can be found.

Graphs and graph representations

vertices and edges
directed vs undirected graphs
labeled graphs
adjacency and degree
adjacency-matrix and adjacency-list representations
paths and cycles
topological sorting
more graph problems: shortest paths, graph coloring

Uses of graphs

states of games and puzzles, which are vertices connected by edges that are the legal moves in the game,
state machines, where the states are vertices and the transitions between states are edges,
road maps, where the vertices are intersections or points along the road and edges are roads connecting those points,
scheduling problems, where vertices represent events to be scheduled and edges might represent events that cannot be scheduled together, or, depending on the problem, edges that must be scheduled together,
and in fact, any binary relation ρ can be viewed as a directed graph in which the relationship x ρ y corresponds to an edge from vertex x to vertex y.

There are many computational problems over graphs that are not known to be solvable in any reasonable amount of time. In particular, there is a large class of problems known as the NP complete problems that are not known to be efficiently solvable, but are known to be equivalent in complexity. If we could give an efficient algorithm for solving any one of them, then we would have efficient algorithms for all of them.

Vertices and edges

A graph consists of a set of vertices V and a set of edges E. If the graph is directed, the edges E are a set of ordered pairs (u,v) representing an edge with source vertex u and sink vertex v. When drawing graphs, this is usually represented as an arrow from u to v.

If the graph is undirected, then the edges are a set of sets of unordered pairs {u,v}. Alternatively, we can model an undirected graph as a directed graph with edges in both directions; i.e., if (u,v) ∈ E, then (v,u) ∈ E also. When drawing graphs, this is usually represented as a line between u and v without an arrowhead.

In some cases, edges from a vertex to itself or multiple edges between the same pair of vertices may be permitted. But usually the default is not to allow these things unless explicly stated otherwise.

Adjacency and degree

Two vertices v and w are adjacent if they are connected by an edge. The degree of a vertex is the total number of adjacent vertices. In a directed graph, we can distinguish between outgoing and incoming edges. The out-degree of a vertex is the number of outgoing edges and the in-degree is the number of incoming edgs.

The real value of graphs is obtained when we can use them to organize information. Both edges and vertices of graphs can have labels that carry meaning about an entity represented by a vertex or about the relationship between two entities represented by an edge. For example, we might encode information about the population of cities and distances between them as an undirected labeled graph:

Here, the vertices are labeled with a pair containing the name of the city and its population, and the edges are labeled with the distance between the cities.

A graph in which the edges are labeled with numbers is called a weighted graph . Of course, the labels do not have to represent weight; they might stand for distances, or the probability of transitioning from one state to another, or the similarity between two vertices, etc.

Graph representations

There are several ways to represent graphs in a computer program. Which representation is best depends on the application. For example, consider the following weighted directed graph with vertices {0,1,2,3} and directed edges with edge weights shown:

Adjacency matrix

An adjacency matrix represents a graph as a two-dimensional array. Each vertex is assigned a distinct index in {0,1,...,|V|-1}. If the graph is represented by the 2D array m , then the edge (or lack thereof) from vertex i to vertex j is recorded at m[i][j] .

The graph structure, ignoring the weights, can be represented by storing a boolean value at each array index. A directed edge from i to j is represented by a true (T) value in location m[i][j]. If there is no edge there, the value is false. For example, the edges in the example above are represented this matrix:

More compact bit-level representations for the booleans are also possible.

If there is some information associated with each edge, say a weight, we store that information in the corresponding array entry:

The space required by the adjacency matrix representation is O(V 2 ), so adjacency matrices can waste a lot of space if the number of edges |E| is much smaller than O(V 2 ). In particular, a graph with only O(V) edges is said to be sparse . For example, graphs in which either the in-degree or out-degree is bounded by a constant are sparse. Adjacency matrices are not as wasteful when the graphs they represent are dense (i.e., not sparse).

Undirected graphs can also be represented with an adjacency matrix. The matrix will be symmetric around its main diagonal; that is, m[i][j]=m[j][i].

Adjacency list representation

Since sparse graphs are quite common, the adjacency list representation is often preferred. This representation keeps track of the outgoing edges from each vertex, typically as a linked list. For example, the graph above might be represented with the following data structure:

Adjacency lists are asymptotically space-efficient because they only use space proportional to the number of vertices and the number of edges. We say that they require O(V+E) space.

Finding the outgoing edges from a vertex is very efficient in the adjacency list representation too; it requires time proportional to the number of outgoing edges. However, finding the incoming edges to a vertex is not efficient: it requires scanning the entire data structure, requiring O(V+E) time.

When it is necessary to be able to walk forward on outgoing edges and backward on incoming edges, a good approach is to maintain two adjacency lists, one representing the graph as above and one corresponding to the dual (or transposed ) graph in which all edges are reversed. That is, there is a an edge (u,v) in the original graph if and only if there is an edge (v,u) in the transposed graph. Of course, this invariant must be maintained between the two adjacency list representations.

Paths and cycles

Following a series of edges from a starting vertex creates a path through the graph, a sequence of alternating vertices and edges beginning and ending with a vertex (v 0 ,e 0 ,v 1 ,e 1 ,...,v n ) where e i = (v i ,v i+1 ) for all 0≤i≤n-1. The length of the path is the number of edges (that is, n). Note that n=0 is possible; this would be a path of length 0 consisting of just a single vertex and no edges. If no vertex appears twice in the path, except that possibly v 0 = v n , the path is called simple . If the first and last vertices are the same, the path is a cycle .

Some graphs have no cycles. For example, linked lists and trees are both examples of graphs in which there are no cycles. They are directed acyclic graphs , abbreviated as DAGs. In trees and linked lists, each vertex has at most one predecessor. In general, vertices of DAGs can have more than one predecessor.

Topological sorting

One use of directed graphs is to represent an ordering constraint on vertices. For example, vertices might represent events, and an edge (u,v) might represent the constraint that u must happen before v.

A topological sort of the vertices is a total ordering of the vertices that is consistent with all edges. That is, if (u,v) is an edge, then u must appear before v in the total ordering. A graph can be topologically sorted if and only if it has no cycles.

Topological sorts are useful for deciding in what order to do things. For example, consider the following DAG expressing what we might call the “men's informal dressing problem”:

A valid plan for getting dressed is a topological sort of this graph. In fact, any topological sort is in principle a workable way to get dressed. For example, the ordering (pants, shirt, belt, socks, tie, jacket, shoes) is consistent with the ordering on all the graph edges. Less conventional strategies are also workable, such as (socks, pants, shoes, shirt, belt, tie, jacket).

This gives us an (inefficient) way to topologically sort a DAG:

Since finding the 0 in-degree node takes O(V) time, this algorithm takes O(V 2 ) time. We can do better, as we'll see shortly.

Reachability

One vertex is reachable from another if there is a path from one to the other. Determining which vertices are reachable from a given vertex is useful and can be done in linear time.

Shortest paths

Hamiltonian paths and the traveling salesman problem

The problem of finding the longest simple path between two nodes in a graph is, in general, intractable. It is related to some other important problems. A Hamiltonian path is one that visits every vertex in a graph exactly once. A Hamiltonian cycle is a cycle that visits every vertex exactly once. The ability to determine whether a graph contains a Hamiltonian path or a Hamiltonian cycle would be useful, but in general the best known algorithms for this problem require exponential time.

A weighted version of this problem is the traveling salesman problem (TSP), which tries to find the Hamiltonian cycle with the minimum total weight. The name comes from imagining a salesman who wants to visit every one of a set of cities while traveling the least possible total distance. This problem is at least as hard as finding Hamiltonian cycles and is not known to be solvable in any less than exponential time. However, finding a solution that is within a constant factor (e.g., 1.5) of optimal can be done in polynomial time under some reasonable assumptions. In practice, there exist good heuristics that allow close-to-optimal solutions to TSP even for large problem instances.

Graph coloring

Imagine that we want to schedule exams in k time slots such that no student has two exams at the same time. We can represent this problem using an undirected graph in which the exams are vertices, with the exams v 1 and v 2 connected by an edge if there exists at least one student who needs to take both exams. We can schedule the exams in the k slots if there is a k-coloring of the graph with k colors: a way to assign a color to each vertex with one of k colors such that no two adjacent vertices are assigned the same color. The chromatic number of a graph is the smallest number of colors needed to color it.

There is no known efficient algorithm for k coloring in general. There are some special classes of graphs for which coloring is efficient, and in practice, graph colorings close to optimal can be found, but in general the best known algorithms to solve the problem optimally take exponential time.

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.

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.

8.4: Graph Representations

Last updated
Save as PDF
Page ID 49318

Wikibooks - Data Structures

Adjacency Matrix Representation

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

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

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

Adjacency List Representation

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

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

3 - [1, 2, 4]

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

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

Search anything:

Graph Representation: Adjacency Matrix and Adjacency List

Graph algorithms graph adjacency matrix adjacency list data structures.

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Reading time: 20 minutes | Coding time: 5 minutes

A Graph is a finite collection of objects and relations existing between objects. If we represent objects as vertices(or nodes) and relations as edges then we can get following two types of graph:-

Directed Graphs: In directed graph, an edge is represented by an ordered pair of vertices (i,j) in which edge originates from vertex i and terminates on vertex j . Given below is an example of an directed graph.

Undirected Graphs: In Undireced graph, edges are represented by unordered pair of vertices.Given below is an example of an undirected graph.

Representation

Adjacency matrix.

The pseudocode for constructing Adjacency Matrix is as follows:

Adjacency List

Implementation

N denotes the number of nodes/ vertices and M denotes the number of edges

degree(V) denotes the number of edges from node V

Adjacency Matrix Complexity

Space: O(N * N)

Check if there is an edge between nodes U and V: O(1)

Find all edges from a node: O(N)

Adjacency List Complexity

Space: O(N + M)

Check if there is an edge between nodes U and V: O(degree(V))

Find all edges from a node V: O(degree(V))

Where to use?

As we have seen in complexity comparisions both representation have their pros and cons and implementation of both representation is simple. It is recommended that we should use Adjacency Matrix for representing Dense Graphs and Adjacency List for representing Sparse Graphs. Note: Dense Graph are those which has large number of edges and sparse graphs are those which has small number of edges.

Application

Adjacency Matrix: Adjacency matrix is used where information about each and every possible edge is required for the proper working of an algorithm like :- Floyd-Warshall Algorithm where shortest path from each vertex to each every other vertex is calculated (if it exists). It can also be used in DFS (Depth First Search) and BFS (Breadth First Search) but list is more efficient there. Sometimes it is also used in network flows.

Adjacency List: Adjacency List is a space efficient method for graph representation and can replace adjacency matrix almost everywhere if algorithm doesn't require it explicitly. It is used in places like: BFS, DFS, Dijkstra's Algorithm etc.

Lets Code Them Up!

Graph representation: adjacency list.

In the last post , we used a 2D matrix to represent the graph. But found it inefficient when our graph consists of a huge number of vertices.

Another way to represent graph is using adjacency list . Here we store the adjacent vertices of a given vertex as a list.

Unweighted Undirected Graph

In the case of the adjacency matrix, we store 1 when there is an edge between two vertices else we store infinity. If you notice, we are storing those infinity values unnecessarily, as they have no use for us. So what we can do is just store the edges from a given vertex as an array or list. To store all the vertices and their adjacent lists we can either use a hashmap or an array or a list or a set.

A better option is to store the 1’s and skip the 0’s, which will reduce the space. We can do that by storing the adjacent nodes in a list/array of the given node.

We can either use a hashmap or an array or a list or a set to implement graph using adjacency list.

Consider the undirected unweighted graph in figure 1. For the vertex 1, we only store 2, 4, 5 in our adjacency list, and skip 1,3,6 (no edges to them from 1). Similarly, for vertex 2, we store 1,3,5,6 and skip 2,4. And do the same for the remaining vertices.

For our example, we will use a hashmap with vertices id (1, 2, 3, etc) as keys and an object node storing the vertex id and its adjacency list . The adjacency list is implemented using ArrayList.

The class Node is like this:

Add an edge

In an undirected graph if we have an edge from a to b then we also have an edge b to a. Hence for an edge {a, b} we add b to the adjacency list of a , and a to the adjacency list of b .

Note, we have an integer value for our source and destination as input but our adjacency list is of type Node . Therefore, first, we access the node corresponding to that integer using getNode () function and then add destination node to the adjacency list by calling the Node’s addAdjacent () method.

The getNode () method first checks whether that integer is present in our graph’s keys . If it is present it returns the node object associated with that key inside the graph. But if it isn’t present , then it creates a new node using the integer and adds it to the graph with the integer as key . Every time, a new vertex comes, it’s id is first added to the graph along with its node and then we add the adjacent vertices to the node’s adjacent list.

Consider an example : Our graph is currently empty . We call the method add(1, 2) . First, we create Node s, by calling the getNode(1) method. The getNode(1) method checks whether 1 is present in our graph(hashmap). Since it is not present , it creates a new node with id 1 and puts the pair (1, Node(1)) inside the hashmap and returns Node(1) . A similar process is followed by 2 to get Node d . Now we have both our nodes s and d as Node(1) and Node(2) . We add Node(2) to the adjacent list of Node(1) and vice versa.

Find Adjacent Vertices

Finding adjacent vertices inside a graph using HashMap is easy. First, we get the node corresponding to the given index using the getNode method and then return that node’s adjacent list . The whole operation takes O(1) time, as accessing an object using the key in HashMap is constant time operation.

For example : When we call findAdjacent(1). We will get an output of [2 4 5] as an ArrayList of type nodes.

Find whether two nodes are connected

To find whether two nodes source and destination are connected or not, we just need to check whether source’s adjacent list contains destination or destination’s adjacent list contains source. If either of the conditions is true, source and destination are connected.

The time complexity of this operation is O(k) , k being the number of adjacent vertices of a given vertex. The time complexity of accessing a node in HashMap is O(1) but the complexity of searching an object in ArrayList is O(n) (where n is the size of the ArrayList. In the worst case, a vertex is connected to all vertices in the graph, then the complexity of this operation becomes O(V) .

For example: When we call isConnected(1,2) , first we get the Nodes(1) and Node(2) using the getNode() method. Node(1) contains its adjacent as [2, 4, 5] and Node(2) contains its adjacent as [1, 3, 5, 6]. We check whether 2 is present in Node(1)’s adjacent. We see that it is present and return true.

The entire code for a unweighted undirected graph is available here .

Weighted Undirected Graph

Graph Representation Edges and Vertices List 1

The edges have a weight in the above graph. We notice it is a bit difficult to store weight of an edge as an instance of Node’s object in the present implementation of the node. Node object just stores all the adjacent nodes and no weights. What we can do is create another class Edge which stores the endVertex along with the weight and then add that Edge object to the adjacent list of the Node.

The Node class becomes:

The implementation of the graph using the HashMap remains same. There is a little difference while adding the edge between source and destination now. As now we add the weight also. You can see the addAdjacent method of Node class. It now takes an extra parameter weight. And we create an edge object using the endVertex and weight and then add that object to our adjacent list.

The adjacent list of Node(1) is [ (2, 5), (4, 6), (5, 10)]. Here 2, 4, 5 are the adjacent vertices and 5, 6, 10 are the weights of edges to those vertices.

The logic for finding all the adjacent vertices is still the same and can be done in O(1) time. Let’s have a look on the logic of finding whether two nodes are connected or not.

Suppose we need to find whether source and destination are connected or not. Next, we access the nodes corresponding to source and destination. Then we traverse the adjacent list of edges of source node linearly and check which edge has endVertex same as the destination. If there is a match, return true, else return false.

The entire code for the weighted undirected graph is available here .

Weighted Directed Graph

Implementation for a weighted directed graph is same as that of the weighted undirected graph. The only difference is in the way we create the adjacent list for each node. Now we just add a destination to the source’s adjacent list. We do not add the source to destination’s adjacent list.

The whole code for directed weighted graph is available here .

The space complexity of using adjacency list is O(E), improves upon O(V*V) of the adjacency matrix. (E is the total number of edges, V is the total number of vertices). We store adjacent nodes of all nodes equivalent to storing all the edges. Hence the complexity is O(E).

Data Structure
Design Pattern

DS Tutorial

Ds linked list, ds searching, differences.

Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

A graph is made up of vertices /nodes and edges /lines that connect those vertices.

A graph may be undirected (meaning that there is no distinction between the two vertices associated with each bidirectional edge) or a graph may be directed (meaning that its edges are directed from one vertex to another but not necessarily in the other direction).

A graph may be weighted (by assigning a weight to each edge, which represent numerical values associated with that connection) or a graph may be unweighted (either all edges have unit weight 1 or all edges have the same constant weight).

Remarks : By default, we show e-Lecture Mode for first time (or non logged-in) visitor. If you are an NUS student and a repeat visitor, please login .

Most graph problems that we discuss in VisuAlgo involves simple graphs.

In a simple graph, there is no (self-)loop edge (an edge that connects a vertex with itself) and no multiple / parallel edges (edges between the same pair of vertices). In another word: There can only be up to one edge between a pair of distinct vertices.

The number of edges E in a simple graph can only range from 0 to O( V 2 ).

Graph algorithms on simple graphs are easier than on non-simple graphs.

Pro-tip 1: Since you are not logged-in , you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] / [PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

An undirected edge e : ( u , v ) is said to be incident with its two end-point vertices: u and v . Two vertices are called adjacent (or neighbor) if they are incident with a common edge. For example, edge (0, 2) is incident to vertices 0+2 and vertices 0+2 are adjacent.

Two edges are called adjacent if they are incident with a common vertex. For example, edge (0, 2) and (2, 4) are adjacent.

The degree of a vertex v in an undirected graph is the number of edges incident with vertex v . A vertex of degree 0 is called an isolated vertex. For example, vertex 0/2/6 has degree 2/3/1, respectively.

A subgraph G' of a graph G is a (smaller) graph that contains subset of vertices and edges of G . For example, a triangle {0, 1, 2} is a subgraph of the currently displayed graph.

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode ( F11 ) to enjoy this setup. However, you can use zoom-in ( Ctrl + ) or zoom-out ( Ctrl - ) to calibrate this.

A path (of length n ) in an (undirected) graph G is a sequence of vertices {v 0 , v 1 , ..., v n-1 , v n } such that there is an edge between v i and v i+1 ∀ i ∈ [0.. n -1] along the path.

If there is no repeated vertex along the path, we call such path as a simple path.

For example, {0, 1, 2, 4, 5} is one simple path in the currently displayed graph.

Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ← / → to step the animation backwards/forwards, respectively, and - / + to decrease/increase the animation speed, respectively.

An undirected graph G is called connected if there is a path between every pair of distinct vertices of G . For example, the currently displayed graph is not a connected graph.

An undirected graph C is called a connected component of the undirected graph G if: 1). C is a subgraph of G ; 2). C is connected; 3). no connected subgraph of G has C as a subgraph and contains vertices or edges that are not in C (i.e., C is the maximal subgraph that satisfies the other two criteria).

For example, the currently displayed graph have {0, 1, 2, 3, 4} and {5, 6} as its two connected components.

A cut vertex/bridge is a vertex/edge that increases the graph's number of connected components if deleted. For example, in the currently displayed graph, there is no cut vertex, but edge (5, 6) is a bridge.

In a directed graph, some of the terminologies mentioned earlier have small adjustments.

If we have a directed edge e : ( u → v ), we say that v is adjacent to u but not necessarily in the other direction. For example, 1 is adjacent to 0 but 0 is not adjacent to 1 in the currently displayed directed graph.

In a directed graph, we have to further differentiate the degree of a vertex v into in-degree and out-degree. The in-degree/out-degree is the number of edges coming-into/going-out-from v , respectively. For example, vertex 1 has in-degree/out-degree of 2/1, respectively.

In a directed graph, we extend the concept of Connected Component (CC) into Strongly Connected Component (SCC). A directed graph G is called strongly connected if there is a path in each direction between every pair of distinct vertices of G .

A directed graph SCC is called a strongly connected component of the directed graph G if: 1). SCC is a subgraph of G ; 2). SCC is strongly connected; 3). no connected subgraph of G has SCC as a subgraph and contains vertices or edges that are not in SCCC (i.e., SCC is the maximal subgraph that satisfies the other two criteria).

In the currently displayed directed graph, we have {0}, {1, 2, 3}, and {4, 5, 6, 7} as its three SCCs.

A cycle is a path that starts and ends with the same vertex.

An acyclic graph is a graph that contains no cycle.

In an undirected graph, each of its undirected edge causes a trivial cycle (of length 2) although we usually will not classify it as a cycle.

A directed graph that is also acyclic has a special name: Directed Acyclic Graph (DAG), as shown above.

There are interesting algorithms that we can perform on acyclic graphs that will be explored in this visualization page and in other graph visualization pages in VisuAlgo.

A graph with specific properties involving its vertices and/or edges structure can be called with its specific name, like Tree (like the one currently shown), Complete Graph, Bipartite Graph, Directed Acyclic Graph (DAG), and also the less frequently used: Planar Graph, Line Graph, Star Graph, Wheel Graph, etc.

In this visualization, we will highlight the first four special graphs later .

Graph appears very often in various form in real life. The most important part in solving graph problem is thus the graph modeling part, i.e., reducing the problem in hand into graph terminologies: vertices, edges, weights, etc.

Social Network: Vertices can represent people, Edges represent connection between people (usually undirected and unweighted).

For example, see the undirected graph that is currently shown. This graph shows 7 vertices (people) and 8 edges (connection/relationship) between them. Perhaps we can ask questions like these:

Who is/are the friend(s) of people no 0?
Who has the most friend(s)?
Is there any isolated people (those with no friend)?
Is there a common friend between two strangers: People no 3 and people no 5?

Transportation Network: Vertices can represent stations, edges represent connection between stations (usually weighted).

For example, see the directed weighted graph that is currently shown. This graph shows 5 vertices (stations/places) and 6 edges (connections/roads between stations, with positive weight travelling times as indicated). Suppose that we are driving a car. We can perhaps ask what is the path to take to go from station 0 to station 4 so that we reach station 4 using the least amount of time?

Discussion: Think of a few other real life scenarios which can be modeled as a graph.

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com ( show your University staff profile/relevant proof to Steven ) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

To toggle between the graph drawing modes, select the respective header. We have:

U/U = Undirected/Unweighted,
U/W = Undirected/Weighted,
D/U = Directed/Unweighted, and
D/W = Directed/Weighted.

We restrict the type of graphs that you can draw according to the selected mode.

You can click any one of the example graphs and see its example graph drawing, which is a two-dimensional depiction of that graph. Note that the same graph can have (infinitely) many possible graph drawings.

You can further edit (add/delete/reposition the vertices or add/change the weight of/delete the edges) the currently displayed graph by clicking "Edit Graph" (read the associated Help message in that Edit Graph window).

We limit the graphs discussed in VisuAlgo to be simple graphs. Refer to its discussion in this slide .

While now we do not really limit the number of vertices that you can draw on screen, we recommend that you draw not more than 10 vertices, ranging from vertex 0 to vertex 9 (as the Adjacency Matrix of this graph will already contain 10x10 = 100 cells). This, together with the simple graph constraint earlier, limit the number of undirected/directed edges to be 45/90, respectively.

All example graphs can be found here. We provide seven "most relevant" example graphs per category (U/U, U/W, D/U, D/W).

Remember that after loading one of these example graphs, you can further edit the currently displayed graph to suit your needs.

Tree, Complete, Bipartite, Directed Acyclic Graph (DAG) are properties of special graphs. As you edit the graph, these properties are checked and updated instantly.

There are other less frequently used special graphs: Planar Graph, Line Graph, Star Graph, Wheel Graph, etc, but they are not currently auto-detected in this visualization.

Tree is a connected graph with V vertices and E = V-1 edges, acyclic, and has one unique path between any pair of vertices. Usually a Tree is defined on undirected graph.

An undirected Tree (see above) actually contains trivial cycles (caused by its bidirectional edges) but it does not contain non-trivial cycle (of length 3 or larger). A directed Tree is clearly acyclic.

As a Tree only have V-1 edges, it is usually considered a sparse graph.

We currently show our U/U: Tree example. You can go to 'Exploration Mode' and edit/draw your own trees.

Not all Trees have the same graph drawing layout of having a special root vertex at the top and leaf vertices (vertices with degree 1) at the bottom. The (star) graph shown above is also a Tree as it satisfies the properties of a Tree.

Tree with one of its vertex designated as root vertex is called a rooted Tree.

We can always transform any Tree into a rooted Tree by designating a specific vertex (usually vertex 0) as the root, and run a DFS or BFS algorithm from the root. This process of "rooting the tree" (of a Tree that is not visually drawn as a tree yet) has a visual explanation. Imagine that each vertex is a small ball (with non-zero weight) and each edge is a rope of the same length connecting two adjacent balls. Now, if we pick the root ball/vertex and pull it up, then gravity will pull the rest of the balls downwards and that is the DFS/BFS spanning tree of the tree.

In a rooted tree, we have the concept of hierarchies (parent, children, ancestors, descendants), subtrees, levels, and height. We will illustrate these concepts via examples as their meanings are as with real-life counterparts:

The parent of 0/1/7/9/4 are none/0/1/8/3, respectively,
The children of 0/1/7 are {1,8}/{2,3,6,7}/none, respectively,
The ancestors of 4/6/8 are {3,1,0}/{1,0}/{0}, respectively,
The lowest common ancestor between 4 and 6 is 1.
The descendants of 1/8 are {2,3,4,5,6,7}/{9}, respectively,
The subtree rooted at 1 includes 1, its descendants, and all associated edges,
Level 0/1/2/3 members are {0}/{1,8}/{2,3,6,7,9}/{4,5}, respectively,
The height of this rooted tree is its maximum level = 3.

For rooted tree, we can also define additional properties:

A binary tree is a rooted tree in which a vertex has at most two children that are aptly named: left and right child. We frequently see this form during the discussion of Binary Search Tree and Binary Heap .

A full binary tree is a binary tree in which each non-leaf (also called the internal) vertex has exactly two children. The binary tree shown above fulfils this criteria.

A complete binary tree is a binary tree in which every level is completely filled, except possibly the last level may be filled as far left as possible. We frequently see this form especially during discussion of Binary Heap .

Complete graph is a graph with V vertices and E = V*(V-1)/2 edges (or E = O( V 2 )), i.e., there is an edge between any pair of vertices. We denote a Complete graph with V vertices as K V .

Complete graph is the most dense simple graph.

We currently show our U/W: K 5 (Complete) example. You can go to 'Exploration Mode' and edit/draw your own complete graphs (a bit tedious for larger V though).

Bipartite graph is an undirected graph with V vertices that can be partitioned into two disjoint set of vertices of size m and n where V = m+n . There is no edge between members of the same set. Bipartite graph is also free from odd-length cycle.

We currently show our U/U: Bipartite example. You can go to 'Exploration Mode' and draw/edit your own bipartite graphs.

A Bipartite Graph can also be complete, i.e., all m vertices from one disjoint set are connected to all n vertices from the other disjoint set. When m = n = V/2 , such Complete Bipartite Graphs also have E = O( V 2 ).

A Tree is also a Bipartite Graph, i.e., all vertices on the even levels form one set, and all vertices on the odd levels form the other set.

Directed Acyclic Graph (DAG) is a directed graph that has no cycle, which is very relevant for Dynamic Programming (DP) techniques.

Each DAG has at least one Topological Sort/Order which can be found with a simple tweak to DFS/BFS Graph Traversal algorithm. DAG will be revisited again in DP technique for SSSP on DAG .

We currently show our D/W: Four 0→4 Paths example. You can go to 'Exploration Mode' and draw your own DAGs.

There are many ways to store graph information into a graph data structure. In this visualization, we show three graph data structures: Adjacency Matrix, Adjacency List, and Edge List — each with its own strengths and weaknesses.

Adjacency Matrix (AM) is a square matrix where the entry AM[i][j] shows the edge's weight from vertex i to vertex j. For unweighted graphs, we can set a unit weight = 1 for all edge weights.

We usually set AM[i][j] = 0 to indicate that there is no edge (i, j). However, if the graph contains 0-weighted edge, we have to use another symbol to indicate "no edge" (e.g., -1, None, null, etc).

We simply use a C++/Python/Java native 2D array/list of size VxV to implement this data structure.

Space Complexity Analysis: An AM unfortunately requires a big space complexity of O( V 2 ), even when the graph is actually sparse (not many edges).

Discussion: Knowing the large space complexity of AM, when is it beneficial to use it? Or is AM always an inferior graph data structure and should not be used at all times?

Adjacency List (AL) is an array of V lists, one for each vertex (usually in increasing vertex number) where for each vertex i, AL[i] stores the list of i's neighbors. For weighted graphs, we can store pairs of (neighbor vertex number, weight of this edge) instead.

We use a Vector of Vector pairs (for weighted graphs) to implement this data structure. In C++: vector<vector<pair<int, int>>> AL; In Python: AL = [[] for _ in range(N)] In Java: Vector<Vector<IntegerPair>> AL; // class IntegerPair in Java is like pair<int, int> in C++

We use pairs as we need to store pairs of information for each edge: (neighbor vertex number, edge weight) where the weight field can be set to 1, 0, unused, or simply dropped for unweighted graph.

We use Vector of Pairs due to Vector's auto-resize feature. If we have k neighbors of a vertex, we just add k times to an initially empty Vector of Pairs of this vertex (this Vector can be replaced with Linked List).

We use Vector of Vectors of Pairs for Vector's indexing feature, i.e., if we want to enumerate neighbors of vertex u , we use AL[u] (C++/Python) or AL.get(u) (Java) to access the correct Vector of Pairs.

Space Complexity Analysis: AL has space complexity of O( V + E ), which is much more efficient than AM and usually the default graph DS inside most graph algorithms.

Discussion: AL is the most frequently used graph data structure, but discuss several scenarios when AL is actually not the best graph data structure?

Edge List (EL) is a collection of edges with both connecting vertices and their weights. Usually, these edges are sorted by increasing weight, e.g., part of Kruskal's algorithm for Minimum Spanning Tree (MST) problem. However in this visualization, we sort the edges based on increasing first vertex number and if ties, by increasing second vertex number. Note that Bidirectional edges in undirected/directed graph are listed once/twice, respectively.

We use a Vector of triples to implement this data structure. In C++: vector<tuple<int, int, int>> EL; In Python: EL = [] In Java: Vector<IntegerTriple> EL; // class IntegerTriple in Java is like tuple<int, int, int> in C++

Space Complexity Analysis: EL has space complexity of O( E ), which is much more efficient than AM and as efficient as AL.

Discussion: Elaborate the potential usage of EL other than inside Kruskal's algorithm for Minimum Spanning Tree (MST) problem!

After storing our graph information into a graph DS, we can answer a few simple queries.

Counting V ,
Counting E ,
Enumerating neighbors of a vertex u ,
Checking the existence of edge (u, v) , etc.

In an AM and AL, V is just the number of rows in the data structure that can be obtained in O( V ) or even in O( 1 ) — depending on the actual implementation.

Discussion: How to count V if the graph is stored in an EL?

PS: Sometimes this number is stored/maintained in a separate variable so that we do not have to re-compute this every time — especially if the graph never/rarely changes after it is created, hence O( 1 ) performance, e.g., we can store that there are 7 vertices (in our AM/AL/EL data structure) for the example graph shown above.

In an EL, E is just the number of its rows that can be counted in O( E ) or even in O( 1 ) — depending on the actual implementation. Note that depending on the need, we may store a bidirectional edge just once in the EL but on other case, we store both directed edges inside the EL.

In an AL, E can be found by summing the length of all V lists and divide the final answer by 2 (for undirected graph). This requires O( V + E ) computation time as each vertex and each edge is only processed once. This can also be implemented in O( V ) in some implementations.

Discussion: How to count E if the graph is stored in an AM?

PS: Sometimes this number is stored/maintained in a separate variable for efficiency, e.g., we can store that there are 8 undirected edges (in our AM/AL/EL data structure) for the example graph shown above.

In an AM, we need to loop through all columns of AM[u][j] ∀j ∈ [0.. V -1] and report pair of (j, AM[u][j]) if AM[u][j] is not zero. This is O( V ) — slow.

In an AL, we just need to scan AL[u]. If there are only k neighbors of vertex u , then we just need O( k ) to enumerate them — this is called an output-sensitive time complexity and is already the best possible.

We usually list the neighbors in increasing vertex number. For example, neighbors of vertex 1 in the example graph above are {0, 2, 3}, in that increasing vertex number order.

Discussion: How to do this if the graph is stored in an EL?

In an AM, we can simply check if AM[u][v] is non zero. This is O( 1 ) — the fastest possible.

In an AL, we have to check whether AL[u] contains vertex v or not. This is O( k ) — slower.

For example, edge (2, 4) exists in the example graph above but edge (2, 6) does not exist.

Note that if we have found edge (u, v), we can also access and/or update its weight.

Quiz: So, what is the best graph data structure?

Discussion: Why?

You have reached the end of the basic stuffs of this relatively simple Graph Data Structures and we encourage you to explore further in the Exploration Mode by editing the currently drawn graph, by drawing your own custom graphs, or by inputting Edge List/Adjacency Matrix/Adjacency List input and ask VisuAlgo to propose a "good enough" graph drawing of that input graph.

However, we still have a few more interesting Graph Data Structures challenges for you that are outlined in this section.

Note that graph data structures are usually just the necessary but not sufficient part to solve the harder graph problems like MST , SSSP , MF , Matching , MVC , ST , or TSP .

For a few more interesting questions about this data structure, please practice on Graph Data Structures training module.

Please look at the following C++/Python/Java/OCaml implementations of the three graph data structures mentioned in this e-Lecture: Adjacency Matrix, Adjacency List, and Edge List: graph_ds.cpp | py | java | ml .

UVa 10895 - Matrix Transpose and,
Kattis - flyingsafely .

Last but not least, there are some graphs that are so nicely structured that we do not have to actually store them in any graph data structure that we have discussed earlier.

For example, a complete unweighted graph can be simply stored with just one integer V , i.e., we just need to remember it's size and since a complete graph has an edge between any pair of vertices, we can re-construct all those V * (V-1) / 2 edges easily.

Discussion: Can you elaborate a few more implicit graphs?

You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Terms of use

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

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

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

List of Publications

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

Bug Reports or Request for New Features

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

Privacy Policy

Version 1.2 (Updated Fri, 18 Aug 2023).

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

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

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

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

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

Data Structures
Linked List
Binary Tree
Binary Search Tree
Segment Tree
Disjoint Set Union
Fenwick Tree
Red-Black Tree
Advanced Data Structures
Print Adjacency List for a Directed Graph
Print adjacency list of a Bidirectional Graph
Introduction to Directed Acyclic Graph
Adjacency Matrix in Python
Implementation of DFS using adjacency matrix
Detect Cycle in a Directed Graph
Shortest Path in Directed Acyclic Graph
Implementation of BFS using adjacency matrix
C program to implement Adjacency Matrix of a given Graph
Convert Directed Graph into a Tree
Longest Path in a Directed Acyclic Graph
Check if a directed graph is connected or not
Convert Adjacency Matrix to Adjacency List representation of Graph
Euler Circuit in a Directed Graph
Convert Adjacency List to Adjacency Matrix representation of a Graph
Add and Remove Edge in Adjacency Matrix representation of a Graph
Sum of dependencies in a graph
Print negative weight cycle in a Directed Graph
Clone a Directed Acyclic Graph
What is Directed Graph? | Directed Graph meaning
Count Edge reversal in a Directed Graph
Find dependencies of each Vertex in a Directed Graph
Detect Cycle in a Directed Graph using BFS
Adjacency matrix meaning and definition in DSA
Longest Path in a Directed Acyclic Graph | Set 2
Detect Cycle in a directed graph using colors
Add and Remove vertex in Adjacency Matrix representation of Graph
Comparison between Adjacency List and Adjacency Matrix representation of Graph
Java Program to Detect Cycle in a Directed Graph

Adjacency Matrix of Directed Graph

Adjacency Matrix of a Directed Graph is a square matrix that represents the graph in a matrix form. In a directed graph, the edges have a direction associated with them, meaning the adjacency matrix will not necessarily be symmetric.

In a directed graph, the edges have a direction associated with them, meaning the adjacency matrix will not necessarily be symmetric. The adjacency matrix A of a directed graph is defined as follows:

What is Adjacency matrix of Directed graph?

For a graph with N vertices, the adjacency matrix A is an N X N matrix where:

A[i][j] is 1 if there is a directed edge from vertex i to vertex j.
A[i][j] is 0 otherwise.

Adjacency Matrix for Directed and Unweighted graph:

Consider an Directed and Unweighted graph G with 4 vertices and 4 edges. For the graph G, the adjacency matrix would look like:

Here’s how to interpret the matrix:

A[0][1] = 1, there is an edge between vertex 0 and vertex 1.
A[1][2] = 1, there is an edge between vertex 1 and vertex 2.
A[2][3] = 1, there is an edge between vertex 2 and vertex 3.
A[3][1] = 1, there is an edge between vertex 3 and vertex 1.
A[i][i] = 0, as there are no self loops on the graph.
All other entries with a value of 0 indicate no edge between the corresponding vertices.

Adjacency Matrix for Directed and Weighted graph:

Consider an Directed and Weighted graph G with 5 vertices and 6 edges. For the graph G, the adjacency matrix would look like:

Properties of Adjacency Matrix of Directed Graph:

Diagonal Entries : The diagonal entries Aii are usually set to 0, assuming the graph has no self-loops.
Out-degree and In-degree : The number of 1’s in a row i (out-degree) indicates the number of outgoing edges from vertex i, while the number of 1’s in a column j (in-degree) indicates the number of incoming edges to vertex j.

Implementation of Adjacency Matrix of Directed Graph:

Below is the implementation of Adjacency Matrix of Directed Graph in different languages:

Please Login to comment...

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

IMAGES

Adjacency List in Graph Data Structure
Graph Representation: Edge list, Adjacency Matrix, and Adjacency lists
Graph Representation: Adjacency List and Matrix
Representation of graph using adjacency matrix and adjacency list
Graph Representation part 03
Data Structure Fundamentals

VIDEO

Graph Representation in Data Structure
Graph Representation
Graph Representation
7
139 Graph Representation Using Adjacency Matrix
Algo L19: Graph: representation using Adjacency Matrix and Adj List

COMMENTS

Adjacency List (With Code in C, C++, Java and Python)
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 ...
Graph and its representations
Representation of Directed Graph to Adjacency list: The below directed graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2 ...
Graph Representation using Java ArrayList
Graph Representation using Java ArrayList. Prerequisite : Graph and its representations. In this article, we will be discussing Adjacency List representation of Graph using ArrayList in Java. Following is adjacency list representation of the above graph. The idea is to use ArrayList of ArrayLists. Similar Implementation using a separate Class ...
Graph Representations
Adjacency Matrix. Adjacency matrix representation makes use of a matrix (table) where the first row and first column of the matrix denote the nodes (vertices) of the graph. The rest of the cells contains either 0 or 1 (can contain an associated weight w if it is a weighted graph). Each row X column intersection points to a cell and the value of ...
Representing graphs (article)
The adjacency list representation for an undirected graph is just an adjacency list for a directed graph, where every undirected edge connecting A to B is represented as two directed edges: -one from A->B -one from B->A e.g. if you have a graph with undirected edges connecting 0 to 1 and 1 to 2 your adjacency list would be: [ [1] //edge 0->1
Representing Graphs in Python (Adjacency List and Matrix)
Another common graph representation is the adjacency matrix. Adjacency matrices are often represented as lists of lists, where each list represents a node. The list's items represent whether an edge exists between the node and another node. Let's take a look at what this may look like:
Adjacency list
This undirected cyclic graph can be described by the three unordered lists {b, c}, {a, c}, {a, b}.. In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph.Each unordered list within an adjacency list describes the set of neighbors of a particular vertex in the graph. This is one of several commonly used representations of ...
Graph Representation using Adjacency Lists
Figure 1: An adjacency list for our example graph. For undirected graphs, each edge uv is stored twice, once in u's neighbor list and once in v's neighbor list; for directed graphs, each edge u->v is stored only once, in the neighbor list of the tail u. For both types of graphs, the overall space required for an adjacency list is O (V + E).
Graphs and graph representations
Adjacency list representation. Since sparse graphs are common, the adjacency list representation is often preferred. This representation keeps track of the outgoing edges from each vertex, typically as a linked list. For example, the graph above might be represented with the following data structure:
Graphs and graph representations
Adjacency list representation. Since sparse graphs are quite common, the adjacency list representation is often preferred. This representation keeps track of the outgoing edges from each vertex, typically as a linked list. For example, the graph above might be represented with the following data structure:
Graph Representation: Adjacency List and 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.
8.4: Graph Representations
The adjacency list is another common representation of a graph. There are many ways to implement this adjacency representation. One way is to have the graph maintain a list of lists, in which the first list is a list of indices corresponding to each node in the graph. Each of these refer to another list that stores the index of each adjacent ...
Graph Representation: Adjacency Matrix and Adjacency List
Adjacency List. Lets consider a graph in which there are N vertices numbered from 0 to N-1 and E number of edges in the form (i,j).Where (i,j) represent an edge from i th vertex to j th vertex. Now, Adjacency List is an array of seperate lists. Each element of array is a list of corresponding neighbour(or directly connected) vertices.In other words i th list of Adjacency List is a list of all ...
Graph Adjacency and Incidence
2. Graph. In computer science, a graph is a data structure that consists of a set of vertices and edges . An edge is a pair of vertices , where . For example, the following picture shows a graph with vertices and edges: 3. Adjacency. If two vertices in a graph are connected by an edge, we say the vertices are adjacent.
Dijkstra's Algorithm for Adjacency List Representation
We have discussed Dijkstra's algorithm and its implementation for adjacency matrix representation of graphs. The time complexity for the matrix representation is O (V^2). In this post, O (ELogV) algorithm for adjacency list representation is discussed. As discussed in the previous post, in Dijkstra's algorithm, two sets are maintained, one ...
Graph Representation: Adjacency List
Consider the undirected unweighted graph in figure 1. For the vertex 1, we only store 2, 4, 5 in our adjacency list, and skip 1,3,6 (no edges to them from 1). Similarly, for vertex 2, we store 1,3,5,6 and skip 2,4. And do the same for the remaining vertices. For our example, we will use a hashmap with vertices id (1, 2, 3, etc) as keys and an ...
Graph Representation
A graph is a data structure that consist a sets of vertices (called nodes) and edges. There are two ways to store Graphs into the computer's memory: Sequential representation (or, Adjacency matrix representation) Linked list representation (or, Adjacency list representation) In sequential representation, an adjacency matrix is used to store the ...
Time and Space Complexity of Adjacency Matrix and List
The two main methods to store a graph in memory are adjacency matrix and adjacency list representation. These methods have different time and space complexities. Thus, to optimize any graph algorithm, we should know which graph representation to choose. The choice depends on the particular graph problem.
What is better, adjacency lists or adjacency matrices for graph
Adjacency Matrix. Uses O (n^2) memory. It is fast to lookup and check for presence or absence of a specific edge. between any two nodes O (1) It is slow to iterate over all edges. It is slow to add/delete a node; a complex operation O (n^2) It is fast to add a new edge O (1) Adjacency List. Memory usage depends more on the number of edges (and ...
Comparison between Adjacency List and Adjacency Matrix representation
Adjacency List: An Adjacency list is an array consisting of the address of all the linked lists. The first node of the linked list represents the vertex and the remaining lists connected to this node represents the vertices to which this node is connected. This representation can also be used to represent a weighted graph.
Graph Data Structures (Adjacency Matrix, Adjacency List, Edge List
An undirected graph G is called connected if there is a path between every pair of distinct vertices of G.For example, the currently displayed graph is not a connected graph. An undirected graph C is called a connected component of the undirected graph G if: 1). C is a subgraph of G; 2). C is connected; 3). no connected subgraph of G has C as a subgraph and contains vertices or edges that are ...
Print Adjacency List for a Directed Graph
Here, for every vertex in the graph, we have a list of all the other vertices which the particular vertex has an edge to. Problem: Given the adjacency list and number of vertices and edges of a graph, the task is to represent the adjacency list for a directed graph. Examples: Input: V = 3, edges [] []= { {0, 1}, {1, 2} {2, 0}} The output ...
Test 4: Toy graph, adjacency list (0/2) Test failed!
Create a graph class using an adjacency list from scratch in Java. Can not use the util library. 7. Graph Traversal. Which graph representation is efficient for finding if a node is adjacent or not, why the other is not efficient?
Adjacency Matrix of Directed Graph
Here's how to interpret the matrix: A[0][1] = 1, there is an edge between vertex 0 and vertex 1. A[1][2] = 1, there is an edge between vertex 1 and vertex 2. A[2][3] = 1, there is an edge between vertex 2 and vertex 3. A[3][1] = 1, there is an edge between vertex 3 and vertex 1. A[i][i] = 0, as there are no self loops on the graph. All other entries with a value of 0 indicate no edge between ...

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

Graph Representations - Adjacency Matrix and List

Adjacency Matrix

Implementation of Adjacency Matrix

Implementation of Adjacency List

Computer science theory

Representing graphs

Adjacency matrices

Representing Graphs in Python (Adjacency List and Matrix)

What are Graphs, Nodes, and Edges?

Understanding Graph Data Structure Representations

Understanding Undirected Graph Data Structures

Adjacency Matrix for Undirected, Unweighted Graphs

Adjacency List for Undirected, Unweighted Graphs

Understanding Directed Graph Data Structures

Understanding Weighted Graph Data Structures

Nik Piepenbreier

Leave a Reply Cancel reply

Graph Representation using Adjacency Lists

Related Books

Books / Graph Algorithms / Chapter 3

Adjacency Lists and Weighted Graphs

Adjacency List in Java

Licenses and Attributions

Original Content CC-BY-SA 4.0 International

Other Content, as indicated:

Speak Your Mind Cancel reply

Graphs and graph representations

Uses of graphs

Vertices and edges

Adjacency and degree

Graph representations

Adjacency matrix

Adjacency list representation

Paths and cycles

Topological sorting

Other graph problems

Reachability

Shortest paths

Hamiltonian cycles and the traveling salesman problem

Graph coloring

Graphs and graph representations

Uses of graphs

Vertices and edges

Adjacency and degree

Graph representations

Adjacency matrix

Adjacency list representation

Paths and cycles

Topological sorting

Other graph problems

Reachability

Shortest paths

Hamiltonian paths and the traveling salesman problem

Graph coloring

Graph Representation: Adjacency List and Matrix

Adjacency Lists

Adjacency Matrices

Representing Weighted Graphs

Implementation

8.4: Graph Representations

Adjacency Matrix Representation

Adjacency List Representation

Graph Representation: Adjacency Matrix and Adjacency List

Representation

Adjacency List

Implementation

Adjacency Matrix Complexity