Home | Projects | Notes > Data Structures & Algorithms > Graphs

Graphs

Different Representations of Graphs

Graphs using Adjacency Matrix

Graphs using Adjacency List

Graphs Big-O

Time Complexity

• Using an adjacency list for a graph consistently offers better time complexity compared to using an adjacency matrix.

Space Complexity

• One significant disadvantage of representing a graph using an adjacency matrix is that it requires storing information for all vertices and edges, even those that are not connected.

Graph using Adjacency List (C++)

Interface

xxxxxxxxxx
30
1
//==============================================================================
2
// File     : graph.h
3
// Brief    : Interface for Graph using adjacency list
4
// Author   : Kyungjae Lee
5
// Date     : Aug 03, 2023
6
//==============================================================================
7

8
#ifndef GRAPH_H
9
#define GRAPH_H
10

11
#include <iostream>
12
#include <unordered_map>
13
#include <unordered_set>
14

15
using namespace std;
16

17
// Class for Graph using adjacency list
18
class Graph
19
{
20
public:
21
    bool addVertex(string vertex);                  // Adds a vertex
22
    bool removeVertex(string vertex);               // Removes a vertex
23
    bool addEdge(string vertex1, string vertex2);   // Adds an edge
24
    bool removeEdge(string vertex1, string vertex2);// Removes an edge
25
    void printGraph(void);                          // Prints graph
26
private:
27
    unordered_map<string, unordered_set<string> > adjList;  // Adjacency list
28
};
29

30
#endif // GRAPH_H

Implementation

xxxxxxxxxx
90
1
//==============================================================================
2
// File     : graph.cpp
3
// Brief    : Implementation of Graph using adjacency list
4
// Author   : Kyungjae Lee
5
// Date     : Aug 03, 2023
6
//==============================================================================
7

8
#include "graph.h"
9

10
using namespace std;
11

12
//------------------------------------------------------------------------------
13
// Implementation of Graph class interface
14
//------------------------------------------------------------------------------
15

16
// Adds a vertex
17
// T = O(1)
18
bool Graph::addVertex(string vertex)
19
{
20
    // Make sure that 'vertex' does not exist 
21
    if (adjList.count(vertex) == 0)
22
    {
23
        adjList[vertex];
24
        return true;
25
    }
26

27
    return false;
28
} // End of addVertex
29

30
// Removes a vertex
31
// T = O(|V|)
32
bool Graph::removeVertex(string vertex)
33
{
34
    // Make sure that 'vertex' does exist 
35
    if (adjList.count(vertex) == 0)
36
        return false;
37

38
    // Loop throuh unordered_set and remove all edges associated with 'vertex'
39
    for (auto otherVertex : adjList.at(vertex))
40
        adjList.at(otherVertex).erase(vertex);
41

42
    // Remove 'vertex'
43
    adjList.erase(vertex);
44

45
    return true;
46
} // End of removeVertex
47

48
// Adds an edge
49
// T = O(1)
50
bool Graph::addEdge(string vertex1, string vertex2)
51
{
52
    // Make sure that 'vertex1' and 'vertex2' both exist
53
    if (adjList.count(vertex1) && adjList.count(vertex2))
54
    {
55
        adjList.at(vertex1).insert(vertex2);
56
        adjList.at(vertex2).insert(vertex1);
57
        return true;
58
    }
59

60
    return false;
61
} // End of addEdge
62

63
// Removes an edge
64
// T = O(1)
65
bool Graph::removeEdge(string vertex1, string vertex2)
66
{
67
    // Make sure that 'vertex1' and 'vertex2' both exist
68
    if (adjList.count(vertex1) && adjList.count(vertex2))
69
    {
70
        adjList.at(vertex1).erase(vertex2);
71
        adjList.at(vertex2).erase(vertex1);
72
        return true;
73
    }
74

75
    return false;
76
} // End of removeEdge
77

78
// Prints graph
79
// T = O(|V|*|E|)
80
void Graph::printGraph(void)
81
{
82
    for (auto [vertex, edges] : adjList)
83
    {
84
        cout << vertex << ": [ ";
85
        for (auto edge: edges)
86
            cout << edge << " ";
87

88
        cout << "]" << endl;
89
    }
90
} // End of printGraph

Test Driver

xxxxxxxxxx
35
1
//==============================================================================
2
// File     : main.cpp
3
// Brief    : Test driver for Graph using adjacency list
4
// Author   : Kyungjae Lee
5
// Date     : Jul 31, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "graph.h"
10

11
using namespace std;
12

13
int main(int argc, char *argv[])
14
{
15
    Graph *g = new Graph();
16

17
    g->addVertex("A");
18
    g->addVertex("B");
19
    g->addVertex("C");
20

21
    g->addEdge("A", "B");
22
    g->addEdge("B", "C");
23
    g->addEdge("A", "C");
24

25
    g->printGraph();
26

27
    cout << endl;
28

29
    //g->removeEdge("A", "C");
30
    g->removeVertex("A");
31

32
    g->printGraph();
33

34
    return 0;
35
}

xxxxxxxxxx
6
1
B: [ C A ]
2
C: [ A B ]
3
A: [ C B ]
4

5
B: [ C ]
6
C: [ B ]