Bookmark and Share
Graph Theory and Algorithms - 2020





Graphs
K4_Complete_Graph.png
Directed Graphs & Matrix Representation


Directed_Graph_Matrix_Representation.png



Connected Graphs & Matrix Representation

The following code will generate the matrix which represents the connections. The diagonal elements are set to 0 which means no loop. Note that the generated matrix is symmetric.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

void createGraph(int size)
{
  bool** graph;
  graph = new bool*[size];
  srand(time(0));

  for(int i = 0; i < size; ++i) {
    graph[i] = new bool[size];
  }
  for(int i = 0; i < size; ++i) {
    for(int j = i; j < size; ++j) {
      // diagonal = false
      if(i == j) {
        graph[i][j] = false;
      }
      // symmetric
      else {
        if(rand() % 2)
          graph[i][j] = graph[j][i] = true;
        else
          graph[i][j] = graph[j][i] = false;
      }
    }
  }
  for(int i = 0; i < size; ++i) {
    for(int j = 0; j < size; ++j) {
      cout << graph[i][j] << " ";
    }
    cout << endl;
  }
}

int main()
{
  createGraph(6);
  return 0;
}

Output:

0 0 1 0 0 1 
0 0 0 1 0 1 
1 0 0 1 0 1 
0 1 1 0 1 0 
0 0 0 1 0 1 
1 1 1 0 1 0