Сохраните все соседи вершин, быстро найдите соседей вершин

Question

Предположим, у меня есть N вершины, помеченные от 0 до N-1. Каждая вершина имеет не более 3 соседей и не менее 1 сосед. Предположим, что информация о соседстве сначала хранится в векторе с именем pairs, где pairs[2*i] и pairs[2*i+1] представляют собой пару соседних вершин.

Теперь мне нужно быстро найти то, что соседи за vertex[i], каков наилучший способ хранения этой информации?

---

Метод, который я придумал это:

• объявить вектор называется neighbors[3*N], так что neighbors[3*i+0]neighbors[3*i+1] и neighbors[3*i+2] хранит три возможных соседей.

• почему говорят, потому что для каждой вершины не более трех соседей.

• поэтому я инициализировать все элементы вектора neighbors к N, что означает, что это не является допустимым соседом, так как вершины помечены от 0 к N-1.

Реализация кода выглядит следующим образом:

void get_neighbors(const std::vector<int>& pairs, 
     std::vector<int>& neighbors) { 
    int N = neighbors.size()/3; 
    int M = pairs.size()/2; 
    //init all the vertexes' neighbours to nothing 
    for (int i=0; i<3*N; ++i) { 
     neighbors[i] = N; 
    } 

    //loop through all the vertexes, and store their neighbors 
    for(int i=0; i<N; ++i) { 
     int j = 0; 
     //loop through pairs, and find out what neighbors vertex[i] has 
     for (int k=0; k < M; ++k) { 
      if(pairs[2*k]==i) { 
       neighbors[3*i+j]=pairs[2*k+1]; 
       ++j; 
      } 
      else if(pairs[2*k+1]==i) { 
       neighbors[3*i+j]=pairs[2*k]; 
       ++j; 
      } 
     } 
    } 
} 

Вещи, которые я чувствую себя некомфортно с моим методом:

1. объявить вектор neighbors(3*N) слишком много, так как многие из его элементов будет быть бесполезным N.

2. Если я хочу посмотреть соседей vertex[i] «s, каждый раз, когда мне нужно проверить, если neighbors[3*i]==N, neighbors[3*i+1]==N и neighbors[3*i+2]==N.

Answer 1

Структура данных, с которой вы работаете, - Graph. Но Graph - это более общая концепция, в которой узел может иметь любое количество соседей.

Поскольку ваша проблема более строгая, каждый узел имеет не более 3 соседей. Решение, которое я предложил в комментариях, является общим, которое может использоваться для всех графиков и будет работать прилично хорошо для вашего дела.

Объявляет график:

vector<vector<int> > graph (N); 

Если есть ребро из a к b сделать это:

graph[a].push_back (b); 

Для извлечения соседей узла a:

for (int i=0;i<graph[a].size();i++) 
    // Do whatever you want with the neighbour. The variable graph[a][i] holds the neighbour number 

Теперь, придя к вашей проблеме лем по крайней мере 3 соседей. Лучшее решение по мне это:

struct node 
{ 
    int data; // Some data related to the node. This is optional. 
    int neigh_1; 
    int neigh_2; 
    int neigh_3; 
} 

И сделать график в виде массива узлов:

node[N] graph; 

Это также будет принимать 3 * N памяти. Но это лучший подход к тому, что вы сделали. Поясню:

Когда вы говорите, дайте мне соседей узла x:

Ваш метод доступа к ячейкам памяти х, 3 * х, 3 * х + 4, 3 * х + 8.

Мой метод доступа к ячейкам памяти х, х + 4, х + 8, х + 16

Подождите! Почему мы обращаемся к x, когда хотим только своих соседей? Это правильный вопрос, но если вам нужно обработать некоторое значение на узле или сохранить некоторую информацию локально для узла, тогда нам нужно получить доступ к x.

Примечание: Подход, который я предлагаю, не будет работать хуже вашего подхода. Но он, безусловно, будет лучше работать в общем случае.

Почему мой подход лучше?

Мой метод приведет к меньшему cache misses, потому что у меня лучшая пространственная locality of reference.

Если вы не заботитесь о работе кеша, простыми словами мой метод будет обращаться к местоположениям, которые ближе друг к другу и, следовательно, имеют очень высокую вероятность того, что они уже находятся в более быстром кэше памяти, что будет приводят к более быстрому доступу.

Также можно утверждать, что мы должны объявить память для соседа только тогда, когда мы этого потребуем. По существу решение vector делает это. Но в этом случае это не будет работать, потому что даже объявление указателя занимает 8 байтов. Но с этим пространством вы можете хранить информацию из 2 целых чисел, то есть информацию о 2 соседях.

Таким образом, динамическое выделение памяти не будет сохранять пространство, так как максимальные соседи равны 3.

Answer 2

Вы можете просто определить структуры, которые содержат значение узла и индексы соседей, как этого

#include <vector> 
#include <iostream> 

struct vertex{ 
    int data; 
    std::vector<int> neighbours; 
}; 

примерной программу, которая добавляет 2 соседей каждый из узлов приводятся ниже. Каждый узел имеет значение своего квадрата индекса.

int main(){ 
    vertex v[5]; 

    for (int i=0;i<5;i++){ 
     v[i].data = i*i; 
    } 

    for (int i=0;i<5;i++){ 
     v[i].neighbours.push_back((i+1) % 5); 
     v[i].neighbours.push_back((i+2) % 5); 
    } 

    for (int i=0;i<5;i++){ 
     std::cout << "vector " << i << " has value " << v[i].data << std::endl; 
     for (int j=0;j<v[i].neighbours.size();j++){ 
      int nodeNum = v[i].neighbours[j]; 
      std::cout << "vector " << i << " has neighbours " << v[i].neighbours[j] << " with data " << v[nodeNum].data << std::endl; 
     } 
     std::cout << std::endl ; 
    } 
    return 0; 
} 

Этот выход будет Вам следующие

vector 0 has value 0 
vector 0 has neighbours 1 with data 1 
vector 0 has neighbours 2 with data 4 

vector 1 has value 1 
vector 1 has neighbours 2 with data 4 
vector 1 has neighbours 3 with data 9 

vector 2 has value 4 
vector 2 has neighbours 3 with data 9 
vector 2 has neighbours 4 with data 16 

vector 3 has value 9 
vector 3 has neighbours 4 with data 16 
vector 3 has neighbours 0 with data 0 

vector 4 has value 16 
vector 4 has neighbours 0 with data 0 
vector 4 has neighbours 1 with data 1 

Поскольку мы использовали вектор для соседей. Мы можем выделить любое количество соседей нашему узлу. Это общий случай. А также применимо к вашему требованию. Надеюсь, что это поможет