Basic Properties of a Graph | DSA in C++ - Software Development PDF Download

Introduction

In computer science and data structures, a graph is a non-linear data structure that consists of a collection of nodes (vertices) connected by edges. Graphs are widely used to represent relationships and connections between objects in various applications such as social networks, road networks, and computer networks. This article aims to provide a beginner-friendly explanation of the basic properties of a graph and how to implement them using C++.

Types of Graphs:

• Undirected Graph: In an undirected graph, edges have no direction. If there is an edge between vertices A and B, you can travel from A to B and from B to A.
• Directed Graph: In a directed graph, edges have a direction. If there is a directed edge from vertex A to vertex B, you can travel from A to B but not from B to A.
• Weighted Graph: In a weighted graph, edges have weights or costs associated with them. These weights represent the distance, cost, or any other value associated with the edge.

Graph Representation

Adjacency Matrix: An adjacency matrix is a 2D array that represents a graph. The value at the intersection of row i and column j represents whether there is an edge between vertex i and vertex j.

Example:

#include <iostream>

#define MAX_SIZE 100

using namespace std;

class Graph {

  int vertices;

  int adjacencyMatrix[MAX_SIZE][MAX_SIZE];

public:

  Graph(int V) {

    vertices = V;

    for (int i = 0; i < vertices; i++) {

      for (int j = 0; j < vertices; j++) {

        adjacencyMatrix[i][j] = 0;

      }

    }

  }

  void addEdge(int source, int destination) {

    adjacencyMatrix[source][destination] = 1;

    adjacencyMatrix[destination][source] = 1;

  }

  void display() {

    for (int i = 0; i < vertices; i++) {

      for (int j = 0; j < vertices; j++) {

        cout << adjacencyMatrix[i][j] << " ";

      }

      cout << endl;

    }

  }

};

int main() {

  Graph graph(4);

  graph.addEdge(0, 1);

  graph.addEdge(0, 2);

  graph.addEdge(1, 2);

  graph.addEdge(2, 3);

  graph.display();

  return 0;

}

Output:

0 1 1 0

1 0 1 0

1 1 0 1

0 0 1 0

Explanation:

• In the above example, we create an undirected graph with 4 vertices (0, 1, 2, 3) using an adjacency matrix.
• The 'addEdge' function is used to add edges between vertices.
• The 'display' function is used to print the adjacency matrix.

Graph Traversals

• Depth-First Search (DFS): DFS explores vertices and their edges as deeply as possible before backtracking. It uses a stack to remember the vertices.
• Breadth-First Search (BFS): BFS explores all the vertices of a particular depth level before moving on to the next level. It uses a queue to remember the vertices.

Connectivity in Graphs

Connected Graph: A connected graph is a graph in which there is a path between every pair of vertices.

Disconnected Graph: A disconnected graph consists of two or more connected components, where a connected component is a subgraph in which there is a path between every pair of vertices.

Sample Problems

• Determine if a given undirected graph is connected.
• Find the shortest path between two vertices in a weighted graph.
• Find the number of connected components in a graph.

Now that you have a basic understanding of the properties of a graph, their representation, and common algorithms, you can further explore advanced concepts such as minimum spanning trees, topological sorting, and more.

Conclusion

In conclusion, understanding the basic properties of a graph is essential in the field of data structures and algorithms. Graphs allow us to represent relationships and connections between objects in a wide range of applications. In this article, we covered the types of graphs, graph representation using adjacency matrix, and basic graph algorithms such as DFS and BFS.