What is Graph?

A graph is a non-linear data structure that consists of a collection of nodes (vertices) connected by edges. It is used to represent relationships between different entities or elements. Graphs are widely used in various fields, including computer science, social networks, transportation networks, and more.

A graph is a pair (V, E), where V is a set of nodes, called vertices, and E is a collection of pairs of vertices called edges.

There are two common types of graphs: directed graphs (digraphs) and undirected graphs. In a directed graph, the edges have a specific direction, while in an undirected graph, the edges have no specific direction.

Here is an example of an directed graph with six vertices (V) and seven edges (E):

In this example, the vertices are represented by the letters A, B, C, D and the edges are represented by the lines connecting the vertices.

The graph can be defined using an adjacency list or an adjacency matrix. Let’s use an adjacency list representation for this example:

unordered_map<char,pair<char,char>> graph = {
    'A': {'B', 'C'},
    'B': {'A', 'C', 'D', 'E'},
    'C': {'A', 'B', 'E'},
    'D': {'B', 'E'},
    'E': {'B', 'C', 'D', 'F'},
    'F': {'E'}
}

In this representation, each vertex is a key in the dictionary, and the corresponding value is a list of vertices that are connected to it.

For example, the vertex ‘A’ is connected to ‘B’ and ‘C’, so the value for key ‘A’ is ['B', 'C']. Similarly, ‘B’ is connected to ‘A’, ‘C’, ‘D’, and ‘E’, so the value for key ‘B’ is ['A', 'C', 'D', 'E'], and so on.

Using this graph representation, you can perform various operations and algorithms on the graph, such as traversals (e.g., depth-first search, breadth-first search), shortest path algorithms (e.g., Dijkstra’s algorithm), and connectivity analysis.

Note: The diagram and example provided here are just one representation of a graph. There are multiple ways to represent a graph, and the choice of representation depends on the specific requirements and use case.

Here’s an example of how you can implement a graph data structure in C++ using an adjacency list representation:

#include <iostream>
#include <list>
#include <unordered_map>

using namespace std;

class Graph {
private:
    unordered_map<int, list<int>> adjList;

public:
    void addEdge(int source, int destination) {
        adjList[source].push_back(destination);
        adjList[destination].push_back(source);
    }

    void printGraph() {
        for (const auto& pair : adjList) {
            cout << "Vertex " << pair.first << " is connected to: ";
            for (int neighbor : pair.second) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph graph;

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    graph.printGraph();

    return 0;
}

In this example, we have a Graph class that uses an unordered_map to store the adjacency list. Each key in the map represents a vertex, and the corresponding value is a list of its neighboring vertices.

The addEdge function is used to add edges between vertices. In this case, we add bidirectional edges, so if there is an edge between vertex A and vertex B, there will also be an edge between vertex B and vertex A.

The printGraph function iterates over the adjacency list and prints each vertex along with its neighboring vertices.

When you run this code, the output will be:

Vertex 0 is connected to: 1 2 
Vertex 1 is connected to: 0 2 
Vertex 2 is connected to: 0 1 3 
Vertex 3 is connected to: 2 4 
Vertex 4 is connected to: 3

This shows the connections between the vertices in the graph.

Applications of graph:

• Representing relationships between components in electronic circuits

• Transportation networks: Highway network, Flight network
• Computer networks: Local area network, Internet, Web
• Databases: For representing ER (Entity Relationship) diagrams in databases, for
  representing dependency of tables in databases