# Graph Data Structure Patterns - Basics with Visualizations

A graph generally represents a network of nodes or a hierarchy. In real life, it could be a network of roads, people or computers, or a hierarchy of employees in a company. A social network like LinkedIn or Instagram has users as the nodes; the edges between the nodes represent the connections or links.

We can represent this network or a graph visually in the following ways:

1. Grid
    
2. Cluster of Nodes
    
3. Hierarchy
    

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137918004/147df805-6508-449f-8b61-b32b72e09cf5.png align="left")

Different Representations of Graphs - TechBum.io

Let's look at the different data structures we can use as building blocks for designing a Graph. If you have read about Graphs before, terms like adjacency matrix and adjacency lists might sound familiar. But in this tutorial, I want to try and simplify the graph data structure fundamentals by adding my spin to it.

## 1\. Grid, Mesh, or Matrix

As you might have guessed, we can use a simple matrix or a multi-dimensional structure to represent a graph. When solving coding interview questions, these commonly come up as an area or space like a room or island.

For flavors of graph problems,

1. In a room or maze of size 5 x 5, we want to make our robot find its way from a given starting point to a target point while avoiding obstacles.
    

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137919543/8c707d22-741e-4337-b60a-a047ba8895ae.png align="left")

Room or Maze as a Graph Problem - TechBum.io

Few follow-ups could be:  
  a. Count the number of unique paths from source to destination.  
  b. Determine the shortest path from source to destination.

2\. In a 10 x 10 grid, each tile is marked with 0 or 1, 0 for water, and 1 for land. Given that an island is a connected land mass surrounded by water, in this case, a cluster of 1's surrounded by 0's, find the number of islands on the map.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137921033/d6a75188-ff34-4c39-91b9-57f2f18d4ecf.png align="left")

Island type Graph Problems - TechBum.io

A follow-up question could be:  
  a. Determine the area of the smallest or biggest island.

Problems like these are good candidates to be represented as a matrix as it has a reasonable memory footprint for maintaining the N x N matrix. In general, Matrix is suitable for representing densely connected nodes. Meaning, that each Node is connected to most other Nodes in the graph, a.k.a, maximally connected.

## 2\. Sparse Network or Low-Density Network

Now let's think about when a matrix would not be a good choice of data structure to represent a Graph. Let's take an example of a Social Network that has 100 users. If we are to build a matrix, we would be representing it as a 100 x 100 matrix. This will allow us to map 10,000 edges that represent the following & follower relationships. But let's say each user is connected to approx 3 other users in the network, which can probably be represented by approx 500 edges. Maintaining a 100 x 100 matrix in memory is extremely wasteful and leads to high space complexity.

To overcome this, we have two options, either build a Linked Node data structure or use a Map, HashMap, or Dictionary to maintain our graph data structure.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137922705/d8d3a2f8-4e15-4830-ac2c-67ee03a2a30c.png align="left")

Sparse or Low-Density Network Graph - TechBum.io

### 2.1. Linked Node Structure or Graph Node

As we saw in the linked list data structure \[TODO hyperlink\], each Linked List Node connects to another linked list node. Similarly, we can build a Graph Node that can maintain pointers to multiple or any number of other Graph Nodes. Thus, giving us the linked network we often design to visualize a graph on paper.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137924234/ac86666b-a649-46f5-807f-3410cbcfdbff.png align="left")

Build a Graph using Graph Nodes - TechBum.io

```java
class GraphNode {
    // any information you want to store for current GraphNode
    Object data;
    
    // Pointers or Edges to other GraphNodes
    List<GraphNode> links;
}
```

### 2.2. Map or Dictionary

A map is yet another way to represent a network and usually works best for coding interview problems. Given that a Map is a set of key-value pairs, to maintain a graph, the key is usually a source node paired with a value that is a list of nodes that the source node connects to.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137925505/91228011-44ae-4816-9120-0e3d74159d87.png align="left")

Building Graph using a Map, HashTable or Dictionary - TechBum.io

## Directed vs. Undirected Graph

To understand this, think about how connections are made on these two social networks: Facebook and Instagram.

On Facebook, being a "friend" represents an Undirected relationship. If user A sends user B a friend request. A is a friend of B and B is a friend of A, making the relationship bidirectional.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137926944/e07754cd-603e-450a-945b-c132f2391a91.png align="left")

Undirected Graph using Map, HashTable, Dictionary representation - TechBum.io

On Instagram, the followers and following relationship is a Directed relationship. If user A follows B, user B doesn't automatically follow back A. B has to explicitly follow A. This adds the possibility of having a one-way or unidirectional edge.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137928290/f083223e-595e-4538-82f2-2d9439a0ea51.png align="left")

Directed Graph using Map, HashTable, Dictionary representation - TechBum.io

## Cyclic vs. Acyclic Graph

Let's take the example of a social network with 3 users: A, B, and C. If A follows B, B follows C and C follows A it creates a loop or a cycle in our network. This is what we call a Cyclic Graph.

💡

All Undirected Graphs are Cyclic, as seen in the above section.

Now take an example of the hierarchy of employment at a company that has a few different employee levels: CEO, Directors, Managers, Programmers. This hierarchy comes from the fact that an employee at each level reports to another employee a level above. Thus forming a Tree-like structure that is usually a unidirectional "reports to" relationship between two nodes. This makes the **Tree** data structure, which is nothing but a **Directed Acyclic Graph**.

![Graph Data Structure Patterns - Basics with Visualizations](https://cdn.hashnode.com/res/hashnode/image/upload/v1705137929659/e1e0138c-6eab-4b17-8161-ca674876b55d.png align="left")

Directed Acyclic Graph or Tree - TechBum.io

## To Conclude...

The major takeaway of this tutorial should be the understanding of how to fundamentally translate or represent any graph using either a matrix, map, or linked graph nodes. Equipped with this information, you should now be able to identify, construct and maintain a graph data structure for the most common types of coding interview questions.

Moving on to the following tutorial, we will discuss different traversal techniques like **Breadth-First Search** and **Depth-First Search** to move around and navigate our graphs.

---

As always the best form of giving back is to share what you learn. If you found this tutorial helpful or you think it can make a difference for someone else in learning & better preparing for coding interviews, show your support by sharing it with them. Thank you!