# Graph

Graphs are used to represent series of relationships between a set of objects.

There are two main parts that make up a graph:

**Nodes (a.k.a Vertices)**are the objects of the graph. Each node usually contains a unique value.**Edges**show how two nodes relate to each other. Edges can have different characteristics:**Unweighted vs Weighted:**An

**unweighted edge**simply shows a connection exists between two nodes.*Example: Node A is connected to Node B.*A

**weighted edge**shows a connection exists, and provides extra information like distance or cost of that connection.*Example: Node A is connected to Node B with a distance of 50.*

**Undirected (bidirected) vs Directed**An

**undirected edge**represents a connection where you can travel in both directions.*Example: You can go from Node A to Node B, and from Node B to Node A.*A

**directed edge**represents a connection where you can only travel in one specified direction.*Example: You can go from Node A to Node B, but NOT from Node B to Node A directly.*

Examples of questions that we could use graphs to solve are:

- What's the shortest distance between two nodes in a given weighted graph?
- Is there a valid path to travel grom one specific node to another specific node in a given directed graph?
- Does a certain value exist in a given graph?

## Creating a graph

In Python, you can create a graph using an

#### adjacency matrix (2D array)

A matrix where each cell (

*i*,*j*) indicates whether there's an edge from*node i*to*node j*.matrix = [

[0, 1, 1],

[1, 0, 0],

[1, 0, 0],

]In this simple graph,

`matrix[0][1]`

and`matrix[1][0]`

are**1**, which means there's an edge between node 0 and node 1. Also,`matrix[0][2]`

and`matrix[2][0]`

are**1**, which means there's an edge between node 0 and node 2.#### adjacency list (dictionary of lists)

A dictionary where each key is a node, and the value is a list of nodes that the node's connected to.

graph = [

0: [1, 2],

]In this simple graph, there's an edge between node 0 and 1, and an edge between node 0 and 2.

#### Note

We recommend using adjacency lists since they're easier to understand and use. However, it's still worthwhile to familiarize yourself with adjacency matrices since some problems may provide an adjacency matrix graph to work with.

### Examples of creating graphs

**Unweighted Undirected Graph**Creating an

**unweighted undirected graph**using an

**adjacency matrix**:

**unweighted undirected graph**using an

**adjacency list**:

**Unweighted Directed Graph**Creating an

**unweighted directed graph**using an

**adjacency matrix**:

**unweighted directed graph**using an

**adjacency list**:

**Weighted Directed Graph**Creating an

**weighted directed graph**using an

**adjacency matrix**:

**weighted directed graph**using an

**adjacency list**:

## Get the neighbors of a node in an adjacency matrix

O(n)In an undirected graph, you need to traverse over either the column or row corresponding to the node.

In a directed graph, you traverse over the row (for outgoing edges) or column (for incoming edges).

## Getting neighboring nodes in an adjacency list

O(1)The adjacency list stores all the neighbors of each key node, so we can just look up the node in the dictionary and return its value.