Adjacency List Graph Representation

How Adjacency List Works

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.

Pros:

• Saves space O(|V|+|E|). In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space
• Adding a vertex is easier
• Iterating over all edges is efficient

Cons:

• Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V)

class Graph:
    adjList
    vertices

    function addVertex():
        adjList.append([])
        vertices++
        visualize()

    function removeVertex(v):
        if v < 0 or v >= vertices:
            return
        adjList.removeAt(v)
        for each list in adjList:
            remove v from list
            for each element in list:
                if element > v:
                    decrease element by 1
        vertices--
        visualize()

    function addEdge(v1, v2):
        if v1 < 0 or v1 >= vertices or v2 < 0 or v2 >= vertices:
            return
        adjList[v1].append(v2)
        adjList[v2].append(v1)  // for undirected graph
        visualize()

    function removeEdge(v1, v2):
        if v1 < 0 or v1 >= vertices or v2 < 0 or v2 >= vertices:
            return
        remove v2 from adjList[v1]
        remove v1 from adjList[v2]  // for undirected graph
        visualize()

    function getNeighbors(v):
        if v < 0 or v >= vertices:
            return []
        return adjList[v]