# 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](http://mathcenter.oxford.emory.edu/site/cs171/graphs/)). 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](/files/1QsQeTFpmxCVCMnpaGFd)

### 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](/files/SG1EAObpwjPbZl7p7TL9)

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

```python
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

```python
    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

```python
    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

```python
    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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jinjunliu.gitbook.io/notes/data_structure_and_algorithms/3.9_graphs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.