Реализация программы Graph

Question

Я пытался реализовать граф через матрицу смежности с использованием массивов. Но я наткнулся на проблему. У моего графа есть вершины вроде 5,7,3,6 (они не для сопоставления с индексом массива). Я знаю, что реализовать, если они такие же, как индексы массива. Я подумал сделать еще один поисковый массив с вершинами и индексами массивов.

Но это сделает его более сложным по времени. Я тоже пробовал искать в Google, но все, что я нашел, было для индексов массива.

Любое предложение будет полезным списком смежности или матрицей

Answer 1

Я могу придумать два простых варианта:

---

1. Маркировка вершин

Для каждой прочитанной вершины укажите ее тегом. В вашем случае:

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

Чтобы добиться хорошей производительности, вы должны сопоставить вершины с картой unordered_map (или ha sh) в прямом и обратном порядке, так что когда вам дана вершина, вы можете получить ее тег в O (1) с помощью forward[vertex], а когда вам дан тег, вы можете найти его вершину в O (1) с помощью backwards[tag]:

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

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

Наконец, представьте свой график как список смежности, как вы знаете, с помощью тегов 0, 1, ..., n - 1.

---

2. Прямое сопоставление

Это проще. Вместо использования массива для ваших вершин используйте unordered_map, который сопоставляет значение вершины со своим списком смежности:

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
}

Если вы хотите перебрать список смежности из 5, просто выполните:

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

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