Implementing Graph Program

I was trying to implement graph via adjacency matrix using arrays. But I stumbled upon an issue My graph has vertices like 5,7,3,6 (they are not in order to map to array index). I know to implement then is they are same as array indices. I thought to make another lookup array, with vertices and array indices.

But that will make it have high time complexity. I tried searching on Google too, but all I found was for array indices.

Any suggestion will be helpful adjacency list or matrix

Solution

I can think of two straight-forward options:

1. Vertex Tagging

For each vertex you read, identify it with a tag. In your case:

vertex | tag
-------|-----
  5    |  0
  7    |  1
  3    |  2
  6    |  3

In order to have a good performance doing this, you should map the vertices with a unordered_map (or hash map) in direct and inverse order, so that when you are given a vertex, you can get its tag in O(1) with forward[vertex] and when you are given a tag, you can find its vertex in O(1) with backwards[tag]:

int tag = 0;
unordered_map<int, int> forward, backwards;

for(int v : vertices){
    forward[v] = tag;
    backwards[tag] = v;
    tag++;
}

Lastly, represent your graph as an adjacency list just as you know, using the tags, that are 0, 1, ..., n - 1.

2. Direct Mapping

This is easier. Instead of using an array for your vertices, use an unordered_map that maps a vertex value to its adjacency list:

unordered_map<int, vector<int>> G;

for(int v : vertices){
    G[v] = vector<int>();
    vector<int> &adj = G[v];
    //add all nodes adjacent to v in adj
}

If you want to iterate through the adjacency list of 5, just do:

vector<int> &adjList = G[5];

for(int v : adjList){
    //stuff
}