AlgoDaily - Graphs

Home > 30 days c++ course > 30 days c++ course > Graphs

Introduction to Graphs

Graphs are a fundamental data structure in computer science. They are composed of a collection of vertices and edges. Vertices represent the entities, while edges represent the relationships between the entities. In simpler terms, graphs are used to model relationships between objects.

Graphs can be used to represent a wide range of real-world scenarios. For example, social networks can be represented using graphs, where individuals are vertices and their connections are edges. Similarly, maps can be represented as graphs, where locations are vertices and roads are edges.

In this lesson, we will explore different concepts related to graphs, including graph representation, graph traversal, graph algorithms, and graph applications.

Let's start by understanding how graphs can be represented in code. One common way to represent a graph is using an adjacency matrix. This is a 2-dimensional matrix where the cell (i, j) represents the presence or absence of an edge between the vertices i and j.

Here is an example of a graph represented using an adjacency matrix in C++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3int main() {
4  // Graphs are a collection of vertices and edges
5  // Let's create a simple graph with 4 vertices and 4 edges
6  int V = 4;
7  int E = 4;
8  int graph[V][E] = {
9    {0, 1, 0, 0},
10    {0, 0, 1, 0},
11    {0, 0, 0, 1},
12    {1, 0, 0, 0}
13  };
14
15  cout << "Graph Representation:" << endl;
16  for (int i = 0; i < V; i++) {
17    for (int j = 0; j < E; j++) {
18      cout << graph[i][j] << " ";
19    }
20    cout << endl;
21  }
22
23  return 0;
24}

This code creates a simple graph with 4 vertices and 4 edges. The adjacency matrix is printed to the console as the graph representation.

In the upcoming lessons, we will dive deeper into different aspects of graph theory and learn about various algorithms used for solving graph-related problems.

Let's move on to the next topic and understand how we can traverse a graph.

xxxxxxxxxx
 
#include <iostream>
using namespace std;
int main() {
  // Graphs are a collection of vertices and edges
  // Let's create a simple graph with 4 vertices and 4 edges
  int V = 4;
  int E = 4;
  int graph[V][E] = {
    {0, 1, 0, 0},
    {0, 0, 1, 0},
    {0, 0, 0, 1},
    {1, 0, 0, 0}
  };
​
  cout << "Graph Representation:" << endl;
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < E; j++) {
      cout << graph[i][j] << " ";
    }
    cout << endl;
  }
​
  return 0;
}

Are you sure you're getting this? Fill in the missing part by typing it in.

One common way to represent a graph is using an __ matrix. This is a 2-dimensional matrix where the cell (i, j) represents the presence or absence of an edge between the vertices i and j.

Write the missing line below.

Graph Representation

There are several ways to represent a graph in code, one common method is using an adjacency matrix. An adjacency matrix is a 2-dimensional matrix where the cell (i, j) represents the presence or absence of an edge between vertices i and j.

Here's an example of how you can represent a graph using an adjacency matrix in C++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4int main() {
5  // Adjacency Matrix representation of a graph
6  int V = 4; // Number of vertices
7
8  // Create a 2D array of size VxV
9  int graph[V][V];
10
11  // Initialize all elements to 0
12  for (int i = 0; i < V; i++) {
13    for (int j = 0; j < V; j++) {
14      graph[i][j] = 0;
15    }
16  }
17
18  // Add edges to the graph
19  graph[0][1] = 1;
20  graph[1][0] = 1;
21  graph[1][2] = 1;
22  graph[2][1] = 1;
23  graph[2][3] = 1;
24  graph[3][2] = 1;
25
26  // Print the adjacency matrix
27  cout << "Adjacency Matrix:" << endl;
28  for (int i = 0; i < V; i++) {
29    for (int j = 0; j < V; j++) {
30      cout << graph[i][j] << " ";
31    }
32    cout << endl;
33  }
34
35  return 0;
36}

In this example, we have a graph with 4 vertices and 4 edges. The adjacency matrix is initialized as a 2D array of size 4x4, with all elements initially set to 0. We then add edges to the graph by setting the appropriate cells of the matrix to 1. Finally, we print the adjacency matrix to visualize the graph representation.

The adjacency matrix representation works well for graphs with a small number of vertices, but it can become inefficient for large graphs. Another common method of representing graphs is using an adjacency list, which we will explore in the next lesson.

xxxxxxxxxx
}
 
#include <iostream>
using namespace std;
​
int main() {
  // Adjacency Matrix representation of a graph
  int V = 4; // Number of vertices
​
  // Create a 2D array of size VxV
  int graph[V][V];
​
  // Initialize all elements to 0
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      graph[i][j] = 0;
    }
  }
​
  // Add edges to the graph
  graph[0][1] = 1;
  graph[1][0] = 1;
  graph[1][2] = 1;
  graph[2][1] = 1;
  graph[2][3] = 1;
  graph[3][2] = 1;
​
  // Print the adjacency matrix
  cout << "Adjacency Matrix:" << endl;
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {

Are you sure you're getting this? Click the correct answer from the options.

Which of the following is a disadvantage of using an adjacency matrix to represent a graph?

A) Requires less memory B) Inefficient for sparse graphs C) Allows easy edge deletion D) Suitable for large graphs

Click the option that best answers the question.

A) Requires less memory
B) Inefficient for sparse graphs
C) Allows easy edge deletion
D) Suitable for large graphs

Graph Traversal

Graph traversal refers to the process of visiting all the vertices (nodes) of a graph in a specific order.

There are two common algorithms for graph traversal: Depth First Search (DFS) and Breadth First Search (BFS).

In Breadth First Search (BFS), we visit all the vertices of a graph in a breadthward motion, starting from a specified vertex. We first visit all the vertices at the same level (distance from the start vertex), and then move to the next level.

Here's an example of how you can perform Breadth First Search (BFS) on a graph in C++:

TEXT/X-C++SRC

1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6// Function to perform Breadth First Search (BFS) on a graph
7void bfs(vector<vector<int>>& graph, int start) {
8  // Create a queue for BFS
9  queue<int> q;
10
11  // Mark the start vertex as visited and enqueue it
12  vector<bool> visited(graph.size(), false);
13  visited[start] = true;
14  q.push(start);
15
16  while (!q.empty()) {
17    // Dequeue a vertex from the queue and print it
18    int current = q.front();
19    q.pop();
20    cout << current << " ";
21
22    // Get all adjacent vertices of the dequeued vertex
23    // If an adjacent vertex has not been visited, mark it as visited
24    // and enqueue it
25    for (int i = 0; i < graph[current].size(); i++) {
26      int adjacent = graph[current][i];
27      if (!visited[adjacent]) {
28        visited[adjacent] = true;
29        q.push(adjacent);
30      }
31    }
32  }
33}
34
35int main() {
36  // Create a graph
37  vector<vector<int>> graph = {
38    {1, 2},
39    {0, 2, 3},
40    {0, 1, 3},
41    {1, 2},
42  };
43
44  // Perform BFS starting from vertex 0
45  cout << "BFS traversal:" << endl;
46  bfs(graph, 0);
47
48  return 0;
49}

xxxxxxxxxx
}
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
​
// Function to perform Breadth First Search (BFS) on a graph
void bfs(vector<vector<int>>& graph, int start) {
  // Create a queue for BFS
  queue<int> q;
​
  // Mark the start vertex as visited and enqueue it
  vector<bool> visited(graph.size(), false);
  visited[start] = true;
  q.push(start);
​
  while (!q.empty()) {
    // Dequeue a vertex from the queue and print it
    int current = q.front();
    q.pop();
    cout << current << " ";
​
    // Get all adjacent vertices of the dequeued vertex
    // If an adjacent vertex has not been visited, mark it as visited
    // and enqueue it
    for (int i = 0; i < graph[current].size(); i++) {
      int adjacent = graph[current][i];
      if (!visited[adjacent]) {
        visited[adjacent] = true;
        q.push(adjacent);

Build your intuition. Fill in the missing part by typing it in.

Graph traversal refers to the process of visiting all the ___ of a graph in a specific order.

There are two common algorithms for graph traversal: Depth First Search (DFS) and Breadth First Search (BFS).

In Depth First Search (DFS), we visit a vertex and then recursively visit all its __ vertices before backtracking. This means that we go as deep as possible before exploring other branches.

On the other hand, in Breadth First Search (BFS), we visit all the vertices at the __ level before moving to the next level.

For example, let's consider the following graph:

SNIPPET

Starting from vertex 1, the depth-first traversal would be 1 2 4 3, while the breadth-first traversal would be 1 2 3 4.

Both DFS and BFS are widely used in various graph algorithms and applications.

Write the missing line below.

Graph Algorithms

Graph algorithms are the algorithms used to solve problems on graphs. These algorithms help in finding shortest paths, minimum spanning trees, and various other properties of graphs.

Here are some common graph algorithms:

Dijkstra's Algorithm: This algorithm finds the shortest path between two vertices in a graph. It works for both weighted and unweighted graphs.
Kruskal's Algorithm: This algorithm finds the minimum spanning tree of a graph. It selects edges in increasing order of their weights and adds them to the spanning tree without creating a cycle.

You can implement these algorithms in C++ using various data structures and algorithms. Here's an example of how you can implement Dijkstra's algorithm:

TEXT/X-C++SRC

1#include <iostream>
2#include <limits>
3#include <vector>
4using namespace std;
5
6const int INF = INT_MAX;
7
8// Function to implement Dijkstra's algorithm
9vector<int> dijkstra(vector<vector<pair<int, int>>>&graph, int start) {
10    int n = graph.size();
11    vector<int> distance(n, INF);
12    vector<bool> visited(n, false);
13
14    distance[start] = 0;
15
16    for (int i = 0; i < n; i++) {
17        int minDistance = INF;
18        int u;
19
20        // Find the vertex with the minimum distance
21        for (int j = 0; j < n; j++) {
22            if (!visited[j] && distance[j] < minDistance) {
23                minDistance = distance[j];
24                u = j;
25            }
26        }
27
28        visited[u] = true;
29
30        // Update the distance of adjacent vertices
31        for (auto edge : graph[u]) {
32            int v = edge.first;
33            int weight = edge.second;
34
35            if (!visited[v] && distance[u] + weight < distance[v]) {
36                distance[v] = distance[u] + weight;
37            }
38        }
39    }
40
41    return distance;
42}
43
44int main() {
45    // Create a graph
46    vector<vector<pair<int, int>>> graph = {
47        {{1, 4}, {2, 1}},
48        {{3, 3}},
49        {},
50        {{2, 2}},
51    };
52
53    // Find the shortest distances from vertex 0
54    vector<int> shortestDistances = dijkstra(graph, 0);
55
56    // Print the shortest distances
57    for (int i = 0; i < shortestDistances.size(); i++) {
58        cout << "Shortest distance from vertex 0 to vertex " << i << ": " << shortestDistances[i] << endl;
59    }
60
61    return 0;
62}

Are you sure you're getting this? Fill in the missing part by typing it in.

A ___ finds the shortest path between two vertices in a graph.

Write the missing line below.

Graphs have a wide range of applications in various domains. They can be used to solve real-life problems by modeling and analyzing relationships between different entities. Here are some common applications of graphs:

Social Networks: Graphs can represent social networks, where nodes represent individuals or organizations, and edges represent relationships like friendships or collaborations. They can be used to analyze the structure of social networks, identify influencers, or recommend new connections.
Transportation Networks: Graphs can model transportation networks like roads, railways, or air routes. They can be used to find the shortest path between two locations, calculate travel times, or optimize transportation routes.
Recommendation Systems: Graphs can power recommendation systems that suggest products, movies, or music based on user preferences and item similarities. They can use graph algorithms to find similar items, calculate item rankings, or personalize recommendations.
Web Search: Graphs are used in web search engines to represent the relationships between web pages. They can be used to determine the relevance and importance of web pages, rank search results, or discover new web pages using web crawling algorithms.

C++ code: To demonstrate how graphs can be used to check if there is a path between two vertices, here's an example code snippet:

TEXT/X-C++SRC

1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Function to check if there is a path between two vertices
6bool isPathExist(vector<vector<int>>& graph, int start, int end) {
7    if (start == end) {
8        return true;
9    }
10
11    int n = graph.size();
12    vector<bool> visited(n, false);
13
14    visited[start] = true;
15
16    // Create a stack for DFS
17    vector<int> stack;
18    stack.push_back(start);
19
20    while (!stack.empty()) {
21        int currVertex = stack.back();
22        stack.pop_back();
23
24        // Visit all the neighbors of the current vertex
25        for (int neighbor : graph[currVertex]) {
26            if (neighbor == end) {
27                return true;
28            }
29
30            if (!visited[neighbor]) {
31                visited[neighbor] = true;
32                stack.push_back(neighbor);
33            }
34        }
35    }
36
37    return false;
38}
39
40int main() {
41    // Create a graph
42    vector<vector<int>> graph = {
43        {1, 3},
44        {2},
45        {3},
46        {4},
47        {2},
48        {}
49    };
50
51    // Check if there is a path between vertex 0 and vertex 4
52    bool pathExists = isPathExist(graph, 0, 4);
53
54    // Print the result
55    if (pathExists) {
56        cout << "There is a path between vertex 0 and vertex 4" << endl;
57    } else {
58        cout << "There is no path between vertex 0 and vertex 4" << endl;
59    }
60
61    return 0;
62}

xxxxxxxxxx
}
 
#include <iostream>
#include <vector>
using namespace std;
​
// Function to check if there is a path between two vertices
bool isPathExist(vector<vector<int>>& graph, int start, int end) {
    if (start == end) {
        return true;
    }
​
    int n = graph.size();
    vector<bool> visited(n, false);
​
    visited[start] = true;
​
    // Create a stack for DFS
    vector<int> stack;
    stack.push_back(start);
​
    while (!stack.empty()) {
        int currVertex = stack.back();
        stack.pop_back();
​
        // Visit all the neighbors of the current vertex
        for (int neighbor : graph[currVertex]) {
            if (neighbor == end) {
                return true;
            }
​

Are you sure you're getting this? Click the correct answer from the options.

Which of the following is NOT a common application of graphs?

Click the option that best answers the question.

Social Networks
Transportation Networks
Recommendation Systems
Database Management Systems

Generating complete for this lesson!

Are you sure you're getting this? Fill in the missing part by typing it in.

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Build your intuition. Fill in the missing part by typing it in.

Are you sure you're getting this? Fill in the missing part by typing it in.

Are you sure you're getting this? Click the correct answer from the options.

Click the option that best answers the question.

Programming Categories

Popular Lessons