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.