What are Graphs? ft. Prison Break

"He who has a why to live can bear almost any how." ~Friedrich Nietzsche

What are Graphs?

One-liner: Graphs are used to represent relationships between entities.

Micheal has the prison blueprint tattooed on his body. This Blueprint is a graph that represents the connection between various places/rooms inside the prison. Why do we need graphs? To solve the following questions

1. How to reach the top of the building from the chairman's office,

2. The fastest route from his cell to the doctor's office

3. What is the shortest path from the garden to his cell?

4. What lies next to the sewage?

5. Finding unexplored or lesser-known places in the prison.

6. How does the Cop traverse the prison cells? Does he go to the 1st room of each floor(BFS) then the 2nd room of each floor and so on.. OR does he goes deep first meaning he visits all the rooms on the 1st floor first and then move on to the 2nd floor?(DFS)

Here a room represents a Vertex and the path between any two rooms(vertices) is called an Edge. How to represent this data? There are 3 popular methods

1. Matrix: This matrix is the graph itself

2. Adjacency Matrix: This represents whether one Vertex is adjacent to another Vertex. 1 if direct path exists and 0 if path doesn't exist.

3. Adjacency List: This tells only about which vertices are directly connected to the given vertex.