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
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
}