Graph Representation

Adjacency Matrix

double ** matrix;
matrix = new double *[N];
for (int i=0; i<N; ++i) {
    matrix[i] = new double[N];
}

Adjacency matrix using contiguous space

double **matrix;
matrix = new double *[N];
double *tmp = new double[N*N]; 
for (int i=0; i<N; ++i) {
    matrix[i] = &( tmp[N*i] );
}

Lower traiangular adjacency matrix

  • Only for undirected graphs

double **matrix;
matrix = new double *[N];
matrix[0] = nullptr;
matrix[1] = new double[N*(N-1)/2];

for (int i=2; i<N; ++i) {
    matrix[i] = matrix[i - 1] + i - 1;
}

Adjacency List

class Pair {
    private:
        double edge_weight;
        int adjacent_vertex;
    public:
        Pair(int, double); // constructor
        double weight() const;
        int vertex() const;
};


void insert(int i, int j, double w) {
    if (i < j) {
        array[j].push_front(Pair(i,w));
    } else {
        array[i].push_front(Pair(j,w));
    }
}

/** main **/
SingleList<Pair> * array;
array = new SingleList<Pair>[N];

In [ ]: