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++:

#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;
}

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.

```c++
#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;
}
```

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.

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++:

#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++) {
      cout << graph[i][j] << " ";
    }
    cout << endl;
  }

  return 0;
}

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.

```c++
#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++) {
      cout << graph[i][j] << " ";
    }
    cout << endl;
  }

  return 0;
}
```

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

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++:

#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);
      }
    }
  }
}

int main() {
  // Create a graph
  vector<vector<int>> graph = {
    {1, 2},
    {0, 2, 3},
    {0, 1, 3},
    {1, 2},
  };

  // Perform BFS starting from vertex 0
  cout << "BFS traversal:" << endl;
  bfs(graph, 0);

  return 0;
}

```c++
#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);
      }
    }
  }
}

int main() {
  // Create a graph
  vector<vector<int>> graph = {
    {1, 2},
    {0, 2, 3},
    {0, 1, 3},
    {1, 2},
  };

  // Perform BFS starting from vertex 0
  cout << "BFS traversal:" << endl;
  bfs(graph, 0);

  return 0;
}
```

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:

   1
  / \
 2   3
  \
   4

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.

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:

1. Dijkstra's Algorithm: This algorithm finds the shortest path between two vertices in a graph. It works for both weighted and unweighted graphs.

2. 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:

#include <iostream>
#include <limits>
#include <vector>
using namespace std;

const int INF = INT_MAX;

// Function to implement Dijkstra's algorithm
vector<int> dijkstra(vector<vector<pair<int, int>>>&graph, int start) {
    int n = graph.size();
    vector<int> distance(n, INF);
    vector<bool> visited(n, false);

    distance[start] = 0;

    for (int i = 0; i < n; i++) {
        int minDistance = INF;
        int u;

        // Find the vertex with the minimum distance
        for (int j = 0; j < n; j++) {
            if (!visited[j] && distance[j] < minDistance) {
                minDistance = distance[j];
                u = j;
            }
        }

        visited[u] = true;

        // Update the distance of adjacent vertices
        for (auto edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (!visited[v] && distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
            }
        }
    }

    return distance;
}

int main() {
    // Create a graph
    vector<vector<pair<int, int>>> graph = {
        {{1, 4}, {2, 1}},
        {{3, 3}},
        {},
        {{2, 2}},
    };

    // Find the shortest distances from vertex 0
    vector<int> shortestDistances = dijkstra(graph, 0);

    // Print the shortest distances
    for (int i = 0; i < shortestDistances.size(); i++) {
        cout << "Shortest distance from vertex 0 to vertex " << i << ": " << shortestDistances[i] << endl;
    }

    return 0;
}

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

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:

1. 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.

2. 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.

3. 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.

4. 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:

#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;
            }

            if (!visited[neighbor]) {
                visited[neighbor] = true;
                stack.push_back(neighbor);
            }
        }
    }

    return false;
}

int main() {
    // Create a graph
    vector<vector<int>> graph = {
        {1, 3},
        {2},
        {3},
        {4},
        {2},
        {}
    };

    // Check if there is a path between vertex 0 and vertex 4
    bool pathExists = isPathExist(graph, 0, 4);

    // Print the result
    if (pathExists) {
        cout << "There is a path between vertex 0 and vertex 4" << endl;
    } else {
        cout << "There is no path between vertex 0 and vertex 4" << endl;
    }

    return 0;
}

```c++
#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;
            }

            if (!visited[neighbor]) {
                visited[neighbor] = true;
                stack.push_back(neighbor);
            }
        }
    }

    return false;
}

int main() {
    // Create a graph
    vector<vector<int>> graph = {
        {1, 3},
        {2},
        {3},
        {4},
        {2},
        {}
    };

    // Check if there is a path between vertex 0 and vertex 4
    bool pathExists = isPathExist(graph, 0, 4);

    // Print the result
    if (pathExists) {
        cout << "There is a path between vertex 0 and vertex 4" << endl;
    } else {
        cout << "There is no path between vertex 0 and vertex 4" << endl;
    }

    return 0;
}
```

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

Generating complete for this lesson!