Adjacency List

A collection of lists representing a graph

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

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;
}
}

2. 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;
}
}

3. 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;
}
}

4. 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;
}

}