Graphs

Well, to understand graph, we need to know the following:

Linear Data Structure - A data structure is said to be linear if the elements are arranged in a sequential manner. Array, Linked List, Stack, Queue are linear data structures.

Non-Linear Data Structure - A data structure is said to be non-linear if the elements are not arranged in a sequential manner. Graph is a non-linear data structure. For example, consider a tree. A real life natural tree. It is a "non-linear" structure. The branches of the tree are not arranged in a sequential manner, but they are connected to each other.

Basically, a Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. It is a popular way to model networks.

An example of a graph is a social network, where people are nodes and friendships are edges connecting them.

Here is a simple visualization of the following data as graph:

• There are 5 people in a social network. (say A, B, C, D, E)
• A is friends with B, C, D
• B is friends with A, C, D
• C is friends with A, B, D, E
• D is friends with A, B, C
• E is friends with C

It would look like this: (On mobile devices, you might need to scroll right to see the complete graph)

In the above graph, the nodes represent the people and the edges (connectors) represent the friendships between them.

Types of Graphs

There are different types of graphs based on the presence of edges and the direction of edges. Here are some common types:

1. Undirected Graph
2. Directed Graph
3. Weighted Graph
4. Unweighted Graph
5. Cyclic Graph
6. Acyclic Graph
7. Connected Graph
8. Disconnected Graph
9. Complete Graph

Undirected Graph

Undirected graph basically is what we have seen in the above example. The edges do not have any direction. It means, if A is friends with B, then B is also friends with A. The edges are bi-directional.

Directed Graph

You know shin-chan, right? Do you know the character Ai-Suotomi-Chan? She likes Shin-chan, but Shin-chan doesn't like her. This is an example of a directed graph. The edges have a direction. Basically, if A is in love with B, it doesn't mean B is in love with A.

Here's a simple visualization of the Shin-chan's situation as a directed graph:

In the above graph, we can see that Ai-Suotomi-Chan likes Shin-chan, but Shin-chan doesn't like her back. And also, Masao likes Ai-Chan but she doesn't like him back.

Weighted Graph

In a weighted graph, each edge has a weight associated with it. The weight can represent the cost, distance, time, etc. In our case, the weight can represent the distance between their houses. (They: Shin-chan, Ai-Chan, Masao & Kazama)

We will add one more condition that, Masao's home and Ai's home are at the opposite ends of the city: Meaning, they dont have straight road to reach each other's home. They either need to go through Shin-chan's home or Kazama's home.

Here's a simple visualization of the weighted graph:

Unweighted Graph

In an unweighted graph, the edges do not have any weight associated with them. The edges are just connections between the nodes.

Cyclic Graph

A graph is cyclic if there is a cycle in the graph. A cycle is a path that starts and ends at the same node.

To understand this, add the following condition to Shin-chan's situation:

• A new road built connecting Masao's home and Ai's home directly.

Here's a simple visualization of the cyclic graph:

In the above graph, there are cycles. Identify and comment them below!

Acyclic Graph

A graph is acyclic if there are no cycles in the graph. It means, there is no path that starts and ends at the same node.

Connected Graph

A graph is connected if there is a path between every pair of nodes. It means, every node is reachable from every other node.

In all the previous graphs, we can see that there is a path between every pair of nodes. Hence, they are connected graphs.

Disconnected Graph

A graph is disconnected if there is no path between at least one pair of nodes. It means, there are some nodes that are not reachable from some other nodes.

Here is a simple visualization of a disconnected graph:

In the above graph, we can see that "Doraemon" is not connected to any other character, since he is from the future and no one knows him yet.

Complete Graph

A graph is complete if there is an edge between every pair of nodes. It means, every node is connected to every other node.

Well, it sounds like connected graph, right? But, there is a difference. The main difference between a connected graph and a complete graph is that in a connected graph, there is a path between every pair of nodes, whereas in a complete graph, there is an edge between every pair of nodes.

Representing Graphs

There are different ways to represent a graph. Some of the common ways are:

1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph.

Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

Here is the adjacency matrix for the friendship graph of the 5 people:

Here, 1 indicates that there is a friendship between the characters and 0 indicates there is no friendship.

For instance, the value at adj[Ai][Shin-chan] is 1, which means Ai is friends with Shin-chan.

The time complexity of adjacency matrix is O(1), as we can access any element just by using the indices.

The space complexity of adjacency matrix is O(V^2), where V is the number of vertices, as the matrix is of size V x V.

Adjacency List

An adjacency list is a collection of linked lists or array that lists all the other vertices that are connected.

Here is the adjacency list for the friendship graph of the 5 people:

In the above adjacency list, we can see that Shin-chan is friends with Ai, Masao, and Kazama.

The time complexity of adjacency list is O(V+E), where V is the number of vertices and E is the number of edges. This is because to get the adjacent vertices of a vertex, we need to traverse the linked list.

The space complexity of adjacency list is O(V+E), where V is the number of vertices and E is the number of edges. This is because we need to store the adjacency list for each vertex.

Conclusion

In this post, we discussed about graphs, the types of graphs, and the ways to represent graphs. Graphs are a powerful way to model relationships between entities and are widely used in various applications. Understanding graphs is essential for solving complex problems in computer science and related fields.

Soon we will discuss about graph traversal algorithms like Depth First Search (DFS) and Breadth First Search (BFS).

Hope you enjoyed this post! Feel free to ask any questions or share your thoughts in the comments below.

Happy Learning! 📚✨