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

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;

}