Adjacency List

Representation of a graph where each vertex is associated with a list of its neighboring vertices

Introduction

An Adjacency list is representation of a graph, where each vertex is associated with a list of its neighboring vertices. It is more space-efficient compared to the adjacency matrix, especially for sparse graphs. In an adjacency list, each vertex points to a collection (often a list or a set) that contains the vertices it is directly connected to via edges.

1. Adjacency List for Undirected Unweighted Graph

Visualization of Adjacency List for Undirected Unweighted Graph

Coding Implementation

//adjacencylistforundirectedweighted.cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int vertex, edges;
cin >> vertex >> edges;
vector<vector<int>> adjlist(vertex);
int u, v;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v;
    adjlist[u].push_back(v);
    adjlist[v].push_back(u);
}

for (int i = 0; i < vertex; i++)
{
    cout << i << ":";
    for (int j = 0; j < adjlist[i].size(); j++)
    {
        cout << adjlist[i][j] << "->";
    }
    cout<<endl;
}
}

# adjacencylistforundirectedunweighted.py
# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency list as list of lists
adj_list = [[] for _ in range(vertex)]

# Read edges and populate adjacency list
for _ in range(edges):
u, v = map(int, input().split())
adj_list[u].append(v)
adj_list[v].append(u)  # For undirected graph

# Print the adjacency list
for i in range(vertex):
print(f"{i}:", end="")
for neighbor in adj_list[i]:
    print(f"{neighbor}->", end="")
print()

# Example usage:
# Input: 5 6
#        0 1
#        0 2
#        0 3
#        2 3
#        3 4
# Output: 0:1->2->3->
#         1:0->
#         2:0->3->
#         3:0->2->4->
#         4:3->

// adjacencylistforundirectedunweighted.js
function createUndirectedUnweightedList(vertex, edges, edgeList) {
// Initialize adjacency list as array of arrays
const adjList = Array(vertex).fill(null).map(() => []);

// Add edges to adjacency list
for (const [u, v] of edgeList) {
    adjList[u].push(v);
    adjList[v].push(u);  // For undirected graph
}

// Print the adjacency list
for (let i = 0; i < vertex; i++) {
    let output = `${i}:`;
    for (const neighbor of adjList[i]) {
        output += `${neighbor}->`;
    }
    console.log(output);
}

return adjList;
}

// Example usage:
const vertex = 5;
const edges = 6;
const edgeList = [[0,1], [0,2], [0,3], [2,3], [3,4]];
createUndirectedUnweightedList(vertex, edges, edgeList);

// Output: 0:1->2->3->
//         1:0->
//         2:0->3->
//         3:0->2->4->
//         4:3->

2. Adjacency List for Undirected Weighted Graph

Visualization of Adjacency List for Undirected Weighted Graph

Coding Implementation

//adjacencylistforundirectedweighted.cpp
#include<iostream>
#include<vector>
using namespace std;
int main(){
int vertex, edges;
cin >> vertex >> edges;
vector<vector<pair<int,int>>> adjlist(vertex);
int u, v,weight;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v>>weight;
    adjlist[u].push_back({v,weight});
    adjlist[v].push_back({u,weight});
}

for (int i = 0; i < vertex; i++)
{
    cout << i << ":";
    for (int j = 0; j < adjlist[i].size(); j++)
    {
        cout <<"{"<<adjlist[i][j].first<<","<<adjlist[i][j].second << "}";
    }
    cout<<endl;
}
}

# adjacencylistforundirectedweighted.py
# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency list as list of lists
adj_list = [[] for _ in range(vertex)]

# Read edges with weights and populate adjacency list
for _ in range(edges):
u, v, weight = map(int, input().split())
adj_list[u].append((v, weight))
adj_list[v].append((u, weight))  # For undirected graph

# Print the adjacency list
for i in range(vertex):
print(f"{i}:", end="")
for neighbor, weight in adj_list[i]:
    print(f"{{{neighbor},{weight}}}", end="")
print()

# Example usage:
# Input: 4 5
#        0 1 2
#        0 2 4
#        1 2 1
#        1 3 5
#        2 3 3
# Output: 0:{1,2}{2,4}
#         1:{0,2}{2,1}{3,5}
#         2:{0,4}{1,1}{3,3}
#         3:{1,5}{2,3}

// adjacencylistforundirectedweighted.js
function createUndirectedWeightedList(vertex, edges, edgeList) {
// Initialize adjacency list as array of arrays
const adjList = Array(vertex).fill(null).map(() => []);

// Add weighted edges to adjacency list
for (const [u, v, weight] of edgeList) {
    adjList[u].push([v, weight]);
    adjList[v].push([u, weight]);  // For undirected graph
}

// Print the adjacency list
for (let i = 0; i < vertex; i++) {
    let output = `${i}:`;
    for (const [neighbor, weight] of adjList[i]) {
        output += `{${neighbor},${weight}}`;
    }
    console.log(output);
}

return adjList;
}

// Example usage:
const vertex = 4;
const edges = 5;
const edgeList = [[0,1,2], [0,2,4], [1,2,1], [1,3,5], [2,3,3]];
createUndirectedWeightedList(vertex, edges, edgeList);

// Output: 0:{1,2}{2,4}
//         1:{0,2}{2,1}{3,5}
//         2:{0,4}{1,1}{3,3}
//         3:{1,5}{2,3}

3. Adjacency List for Directed Unweighted Graph

Visualization of Adjacency List for Directed Unweighted Graph

Coding Implementation

// adjacencylistfordirectedunweighted.cpp
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int vertex, edges;
cin >> vertex >> edges;
vector<vector<int>> adjlist(vertex);
int u, v;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v;
    adjlist[u].push_back(v);
}

for (int i = 0; i < vertex; i++)
{
    cout << i << ":";
    for (int j = 0; j < adjlist[i].size(); j++)
    {
        cout << adjlist[i][j] << "->";
    }
    cout << endl;
}
}

# adjacencylistfordirectedunweighted.py
# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency list as list of lists
adj_list = [[] for _ in range(vertex)]

# Read directed edges and populate adjacency list
for _ in range(edges):
u, v = map(int, input().split())
adj_list[u].append(v)  # Only add one direction for directed graph

# Print the adjacency list
for i in range(vertex):
print(f"{i}:", end="")
for neighbor in adj_list[i]:
    print(f"{neighbor}->", end="")
print()

# Example usage:
# Input: 4 5
#        0 1
#        0 2
#        1 3
#        2 1
#        3 2
# Output: 0:1->2->
#         1:3->
#         2:1->
#         3:2->

// adjacencylistfordirectedunweighted.js
function createDirectedUnweightedList(vertex, edges, edgeList) {
// Initialize adjacency list as array of arrays
const adjList = Array(vertex).fill(null).map(() => []);

// Add directed edges to adjacency list
for (const [u, v] of edgeList) {
    adjList[u].push(v);  // Only add one direction for directed graph
}

// Print the adjacency list
for (let i = 0; i < vertex; i++) {
    let output = `${i}:`;
    for (const neighbor of adjList[i]) {
        output += `${neighbor}->`;
    }
    console.log(output);
}

return adjList;
}

// Example usage:
const vertex = 4;
const edges = 5;
const edgeList = [[0,1], [0,2], [1,3], [2,1], [3,2]];
createDirectedUnweightedList(vertex, edges, edgeList);

// Output: 0:1->2->
//         1:3->
//         2:1->
//         3:2->

4. Adjacency List for Directed Weighted Graph

Visualization of Adjacency List for Directed Weighted Graph

Coding Implementation

//adjlistdirectedweighted.cpp
#include<iostream>
#include<vector>
using namespace std;
int main(){
int vertex, edges;
cin >> vertex >> edges;
vector<vector<pair<int,int>>> adjlist(vertex);
int u, v,weight;
for (int i = 0; i < edges; i++)
{
    cin >> u >> v >> weight;
    adjlist[u].push_back({v,weight});
}

for (int i = 0; i < vertex; i++)
{
    cout << i << ":";
    for (int j = 0; j < adjlist[i].size(); j++)
    {
        cout <<"{"<<adjlist[i][j].first<<","<<adjlist[i][j].second << "}";
    }
    cout<<endl;
}

}

# adjlistdirectedweighted.py
# Read number of vertices and edges
vertex, edges = map(int, input().split())

# Initialize adjacency list as list of lists
adj_list = [[] for _ in range(vertex)]

# Read directed edges with weights and populate adjacency list
for _ in range(edges):
u, v, weight = map(int, input().split())
adj_list[u].append((v, weight))  # Only add one direction for directed graph

# Print the adjacency list
for i in range(vertex):
print(f"{i}:", end="")
for neighbor, weight in adj_list[i]:
    print(f"{{{neighbor},{weight}}}", end="")
print()

# Example usage:
# Input: 4 5
#        0 1 2
#        0 2 4
#        1 3 5
#        2 1 1
#        3 2 3
# Output: 0:{1,2}{2,4}
#         1:{3,5}
#         2:{1,1}
#         3:{2,3}

// adjlistdirectedweighted.js
function createDirectedWeightedList(vertex, edges, edgeList) {
// Initialize adjacency list as array of arrays
const adjList = Array(vertex).fill(null).map(() => []);

// Add directed weighted edges to adjacency list
for (const [u, v, weight] of edgeList) {
    adjList[u].push([v, weight]);  // Only add one direction for directed graph
}

// Print the adjacency list
for (let i = 0; i < vertex; i++) {
    let output = `${i}:`;
    for (const [neighbor, weight] of adjList[i]) {
        output += `{${neighbor},${weight}}`;
    }
    console.log(output);
}

return adjList;
}

// Example usage:
const vertex = 4;
const edges = 5;
const edgeList = [[0,1,2], [0,2,4], [1,3,5], [2,1,1], [3,2,3]];
createDirectedWeightedList(vertex, edges, edgeList);

// Output: 0:{1,2}{2,4}
//         1:{3,5}
//         2:{1,1}
//         3:{2,3}

Adjacency List

On this page