Graphs

Graph: Introduction

Graphs are a data structure that can be used to represent a network of nodes (or vertices) and edges (or connections). The edges can be directed or undirected. Each edge has a weight. A real-world example of a graph would be a social network or a digital map. (See reference). A tree is a special type of graph in which each node is connected to exactly two other nodes. A linked list is a special type of graph in which each node is connected to exactly one other node.

undirected graph

Graph: Adjacency Matrix and Adjacency List

There are two ways to represent a graph: the one is to use an adjacency matrix. The adjacency matrix is a two-dimensional array of booleans. The value at the i-th row and j-th column is true if there is an edge between the i-th and j-th nodes. The other way to represent a graph is to use an adjacency list. The adjacency list is a list of lists. The value at the i-th index of the adjacency list is a list of the nodes that are connected to the i-th node.

adjacency matrix and list

Adjacency matrix of undirected graph is symmetric because if a node A is connected to a node B, then B is also connected to A. The diagonal of the adjacency matrix is always zero because there is no edge between a node and itself.

Graph: Big O

The space complexity is O(|V|^2) for adjacency matrix and O(|V|+|E|) for adjacency list, where |V| is the number of vertices and |E| is the number of edges.

Adding a node to a graph is O(1) when using an adjacency list because we just need to add a new node to the end of the list. It is O(|V|^2) when using an adjacency matrix because we need to rewrite the whole matrix.

Adding an edge is O(1) for both adjacency list and adjacency matrix because we just need to change the value of the corresponding cell.

Removing a node is O(|V|+|E|) for adjacency list because we need to remove the node from the list and then loop through the list to remove all the edges connected to the node. It is O(|V|^2) for adjacency matrix because we need to rewrite the whole matrix.

Removing an edge is O(1) for adjacency matrix and O(|E|) for adjacency list.

Graph: Add Vertex

class Graph:
    def __init__(self):
        self.adj_list = {}

    def print_graph(self):
        for vertex in self.adj_list:
            print(vertex, ':', self.adj_list[vertex])

    def add_vertex(self, vertex):
        if vertex not in self.adj_list.keys():
            self.adj_list[vertex] = []
            return True
        return False

my_graph = Graph()
my_graph.add_vertex('A')
my_graph.print_graph()

Graph: Add Edge

    def add_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys():
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1)
            return True
        return False

my_graph = Graph()
my_graph.add_vertex(1)
my_graph.add_vertex(2)
my_graph.add_edge(1,2)
my_graph.print_graph()

Graph: Remove Edge

    def remove_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys(): 
            try:
                self.adj_list[v1].remove(v2)
                self.adj_list[v2].remove(v1)
            except ValueError:
                pass
            return True
        return False

my_graph = Graph()
my_graph.add_vertex('A')
my_graph.add_vertex('B')
my_graph.add_vertex('C')
my_graph.add_vertex('D')
my_graph.add_edge('A','B')
my_graph.add_edge('B','C')
my_graph.add_edge('C','A')
my_graph.remove_edge('A','D')
my_graph.print_graph()

Graph: Remove Vertex

    def remove_vertex(self, vertex):
        if vertex in self.adj_list.keys():
            for other_vertex in self.adj_list[vertex]:
                self.adj_list[other_vertex].remove(vertex)
            del self.adj_list[vertex]
            return True
        return False

my_graph = Graph()
my_graph.add_vertex('A')
my_graph.add_vertex('B')
my_graph.add_vertex('C')
my_graph.add_vertex('D')

my_graph.add_edge('A','B')
my_graph.add_edge('A','C')
my_graph.add_edge('A','D')
my_graph.add_edge('B','D')
my_graph.add_edge('C','D')

my_graph.remove_vertex('D')

my_graph.print_graph()

Quiz: Graph

• Adding a Vertex in a Graph with an Adjacency List is O(1): True

• Graphs are the go to data structure when you need to represent entities and the relationships between them: True

• Removing a vertex is O(1): False. Finding the vertex is O(1). However, you also have to remove all of the edges associated with the vertex you are removing.