Graphs are fundamental data structures that model relationship between objects. They are widely used in computer science and real-world applications to represent networks, social connections, transportation systems, and more.

Understanding Graphs

A graph is a non-linear data structure consists of nodes (vertices) and edges that connect pairs of nodes. The edges may be directed or undirected, and they can have weights to represent costs, distances, or any other relevant metric. Graphs come in various types, such as directed, undirected, weighted, and unweighted. More formally a Graph is composed of a set of vertices (V) and a set of edges (E). The graph is denoted by G(E, V).

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The network may include paths in a city or telephone network or circuit network. Graphs are also used in social-networks like Linkedin, Facebook.

For example:

   A
  / \
 B - C
 |   |
 D - E

In the above example:

• A, B, C, D, and E are nodes (vertices).
• The lines connecting the nodes represent edges.

Graph Classification

A graph can be classified into following types:

1 Directed Graphs (Digraphs):

Graphs in which edges have a direction.

Example: Social media follow relationships, website hyperlinks.

• Each edge has a specific direction.

    A --> B
   /  ↗   ↘
  ↓   C --> D
   \  ↘   ↗
    └---> E

2 Undirected Graphs:

Graphs in which edges have no direction.

Example: Friendship network, road networks.

• Edges represent symmetric relationships.

    A --- B
   /  \    \
  C -- D -- E

3 Weighted Graphs:

Graphs in which edges have weights.

Example: Road networks with distances, social networks with interaction strengths.

• Each edge has an associated weight.
• Edge weights can represents distances, costs, or any other relevant metric.

    A -4-- B
   / \     |
  2  1     6
 /   |     |
D -3-C -7- E

4 Unweighted Graphs:

Graphs in which edges have no weights.

Example: Simple Social networks, family trees.

• Edges are only present or absent, without associated weights.

    A --- B
   /  \    \
  C -- D -- E

5 Cyclic Graphs:

Definition: Graphs containing one or more cycles (closed paths).

Example: Many social networks, where friend connections can form closed loops.

Characteristics:

• There exists at least one cycle in the graph.

6. Acyclic Graphs:

Definition: Graphs without any cycles.

Example: Directed acyclic graphs (DAGs) in project management, family trees without loops.

Characteristics:

• No cycles are present in the graph.

    A --- B
   /  \    \
  C -- D -- E
   \  /    /
    └----─┘

7. Connected Graphs:

Definition: Graphs in which there is a path between every pair of vertices.

Example: A fully connected social network.

Characteristics:

• There are no isolated vertices, and every vertex is reachable from every other vertex.

    A --- B
   /  \    \
  C -- D -- E

8. Disconnected Graphs:

Definition: Graphs in which there are one or more isolated subgraphs.

Example: Social networks with separate communities.

Characteristics:

• There are one or more isolated subgraphs, and there is no path between vertices in different subgraphs.

    A --- B       G    H
   /  \    \          /
  C -- D -- E       I

9. Bipartite Graphs:

Definition: Graphs whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set.

Example: Job applicants and job openings, students and classes.

Characteristics:

• Vertices can be divided into two sets, and all edges connect vertices from different sets.

    A       B
   /  \    / |
  C    D  /  E
   \  /  /   |
    F    G   H

10. Complete Graphs:

Definition: Graphs in which every pair of distinct vertices is connected by a unique edge.

Example: A social network where every user is friends with every other user.

Characteristics:

• Each vertex is connected to every other vertex by a unique edge.

    A --- B
   /  \ / |
  C --- D  |
   \  / \ |
    E --- F

Graph Terminologies

1.  Vertex (Node):

• A fundamental unit of a graph.
• Represents an entity or a point in the graph.

2. Edge:

• Connects two vertices in a graph.
• May have a direction (directed graph) or may not have a direction (undirected graph).

Edges are three types:

1. Undirected Edge - An undirected edge is a bidirectional edge. If there is undirected edge between vertices A and B then edge (A, B) is equal to edge (B, A).
2. Directed Edge - A directed edge is a unidirectional edge. If there is directed edge between vertices A and B then edge (A, B) is not equal to edge (B, A).
3. Weighted Edge - A weighted edge is a edge with value (cost) on it.

3. Directed Graph (Digraph):

• A graph in which edges have a direction.
• The edge (u, v) indicates a directed edge from verted u to vertex v.

4. Undirected Graph:

• A graph in which edges have no direction.
• The edge {u, v} is the same as the edge {v, u}.

5. Weighted Graph:

• A graph in which each edge has an associated numerical value (weight).
• The weight may represent distances, costs, or any other relevant metric.

6. Unweighted Graph:

• A graph in which all edges are considered to have equal weight.

7. Adjacent Nodes (Neighbors):

• Nodes that are connected by an edge.
• In an undirected graph, if there is an edge between node A and node B, then A and B are adjacent.

8. Degree of a Vertex:

• For an undirected graph, the degree of a vertex is the number of edges incident to it.
• For a directed graph, the in-degree is the number of edges coming into a verted, and the out-degree is the number of edges going out of a vertex.

9. Path:

• A sequence of vertices where each adjacent pair is connected by a edge.
• The length of a path is the number of edges it contains.

10. Cycle:

• A path that starts and ends at the same vertex, forming a closed loop.

11. Connected Graph:

• A graph in which there is a path between every pair of vertices.

12. Disconnected Graph:

• A graph in which there are two or more components (subgraphs) that are not connected.

13. Subgraph:

• A graph formed by a subset of vertices and edges of an original graph.

14. Graph Traversal:

• The process of visiting all vertices and edges of a graph.
• Common traversal algorithms include Depth-First Search (DFS) and Breadth-First Search (BFS).

Graph Representation

Graphs can be represented in various ways, each suited to different requirements and scenarios. The choice of representation can impact the efficiency of certain operations, such as adding or removing edges, traversing the graph, or finding specific paths. Here are three common representations of graphs:

1 Adjacency Matrix:

An adjacency matrix is a 2D array (matrix) where each cell represents the presence or absence of an edge between two vertices. For an undirected graph, the matrix is symmetric since the relationship between vertex A and vertex B is the same as that between B and A. For a directed graph, the matrix may not be symmetric, reflecting the directionality of edges.

An adjacency matrix is a way of representing a graph as a matrix of Boolean (0's  and 1's).

Let's assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n] having dimension n x n.

• If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
• If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

Example:

   | A | B | C | D |
---------------------
A  | 0 | 1 | 0 | 1 |
B  | 1 | 0 | 1 | 0 |
C  | 0 | 1 | 0 | 1 |
D  | 1 | 0 | 1 | 0 |

In this example, a value of 1 at position (i, j) indicates an edge between vertices i and j, while 0 indicates no edge.

Code Representation:

Array Matrix:

The 0th row and column is just for padding. so that our matrix become 1 base indexing.

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    // adjacency matrix for undirected graph
    // time complexity: O(n)
    // n+1 because it add 0th row and column as padding.
    int adj[n+1][n+1];
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u][v] = 1;
        adj[v][u] = 1  // this statement will be removed in case of directed graph
    }
    return 0;
}

Vector Matrix:

#include <iostream>
#include <vector>

using namespace std;

// Function to add an edge to the graph
void addEdge(vector<vector<int>>& graph, int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1; // Uncomment this line if the graph is undirected
}

// Function to print the adjacency matrix
void printGraph(vector<vector<int>>& graph, int V) {
    cout << "Adjacency Matrix:" << endl;
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    // Number of vertices in the graph
    int V = 6; // Change this value as per your requirement

    // Create an empty adjacency matrix
    vector<vector<int>> graph(V, vector<int>(V, 0));

    // Add edges to the graph
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    // Print the adjacency matrix
    printGraph(graph, V);

    return 0;
}

Representation of Undirected Graph to Adjacency Matrix:

    A
   / \
  B---C
   \ /
    D

In this graph:

• Vertex A is connected to vertices B and C.
• Vertex B is connected to vertices A, C, and D.
• Vertex C is connected to vertices A, B, and D.
• Vertex D is connected to vertices B and C.

Now, let's represent this graph as an adjacency matrix:

    A   B   C   D
-------------------
A | 0   1   1   0
B | 1   0   1   1
C | 1   1   0   1
D | 0   1   1   0

In the adjacency matrix:

• Rows and columns represent vertices of the graph.
• Each cell (i, j) contains a 1 if there is an edge between vertices i and j, and 0 otherwise.
• Since the graph is undirected, the adjacency matrix is symmetric across the main diagonal. Therefore, if cell (i, j) is 1, then cell (j, i) must also be 1.

Representation of Directed Graph to Adjacency Matrix:

    A -------> B
    | \      / |
    |   v  v   |
    v   C----> D
    \_________/

In this directed graph:

• Vertex A has outgoing edges to vertices B and C.
• Vertex B has outgoing edges to vertices C and D.
• Vertex C has outgoing edges to vertices A and D.
• Vertex D has outgoing edges to vertices A and B.

Now, let's represent this directed graph as an adjacency matrix:

    A   B   C   D
-------------------
A | 0   1   1   0
B | 0   0   1   1
C | 1   0   0   1
D | 1   1   0   0

2 Adjacency List:

An adjacency list represents each vertex as a list of its adjacent vertices. This representation is particularly useful for sparse graphs, where the number of edges is much smaller compared to the number of vertices.

An array of Lists is used to store edges between two vertices. the size of array is equal to the number of vertices (i.e, n). Each index in this array represents a specific vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.

Example:

A -> [B, D]
B -> [A, C]
C -> [B, D]
D -> [A, C]

In this example, each vertex is associated with a list of its adjacent vertices.

Let's assume there are n vertices in the graph. So, create an array of list of size n as adjList[n].

• adjList[0] will have all the nodes which are connected (neighbour) to vertex 0.
• adjList[1] will have all the nodes which are connected (neighbour) to vertex 1 and so on.

Code Implementation of Representation:

#include <iostream>
#include <vector>

using namespace std;

// Function to add an edge to the graph
void addEdge(vector<vector<int>>& adjList, int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u); // Uncomment this line if the graph is undirected
}

// Function to print the adjacency list
void printGraph(vector<vector<int>>& adjList, int V) {
    cout << "Adjacency List:" << endl;
    for (int i = 0; i < V; ++i) {
        cout << i << " --> ";
        for (int j = 0; j < adjList[i].size(); ++j) {
            cout << adjList[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    // Number of vertices in the graph
    int V = 6; // Change this value as per your requirement

    // Create an empty adjacency list
    vector<vector<int>> adjList(V);

    // Add edges to the graph
    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 2);
    addEdge(adjList, 1, 3);
    addEdge(adjList, 1, 4);
    addEdge(adjList, 2, 3);
    addEdge(adjList, 3, 4);
    addEdge(adjList, 4, 5);

    // Print the adjacency list
    printGraph(adjList, V);

    return 0;
}

Representation of Undirected Graph to Adjacency list:

Let's consider the same example of an undirected graph with four vertices and five edges:

    A
   / \
  B---C
   \ /
    D

The adjacency list representation of this graph would be:

A: B, C
B: A, C, D
C: A, B, D
D: B, C

Here's how the adjacency list corresponds to the graph:

• Vertex A is adjacent to vertices B and C.
• Vertex B is adjacent to vertices A, C, and D.
• Vertex C is adjacent to vertices A, B, and D.
• Vertex D is adjacent to vertices B and C.

In the adjacency list representation:

• Each line represents a vertex.
• The adjacent vertices are listed next to each vertex.
• Since the graph is undirected, for each edge (u, v), there is a corresponding edge (v, u), which is why both vertices appear in each other's adjacency list.

Representation of weighted graph in Adjacency list:

Let's consider a weighted undirected graph with four vertices and five edges:

     A --4-- B
    / \     / \
   2   5   1   6
  /     \ /     \
 D --3-- C --7-- E

Here's how the weighted adjacency list representation would look like:

A: [(B, 4), (D, 2), (C, 5)]
B: [(A, 4), (C, 1), (E, 6)]
C: [(B, 1), (D, 3), (E, 7), (A, 5)]
D: [(A, 2), (C, 3)]
E: [(B, 6), (C, 7)]

In this representation:

• Each line represents a vertex.
• For each vertex, we have a list of tuples. Each tuple contains the adjacent vertex and the weight of the edge between the vertex and its adjacent vertex.

3 Edge List:

An edge list simply enumerates all the edges in the graph as pairs of vertices. Each edge is represented as a tuple (u, v), where u and v are the vertices connected by the edge.

Example:

[(A, B), (A, D), (B, C), (C, D)]

In this example, each tuple represents an edge between two vertices.