Эффективное представление списка смежности и весов в ориентированном графе

Question

Я хотел бы получить отзывы о хранении списков смежности для графов.

Обычно я представляю смежный список, используя вектор векторов, например, std::vector<std::vector<int>> adj_list

Для ребра E = (u, v) он просто сохраняется с использованием adj_list[u].push_back(v).Если я хочу удалить это ребро, я просто делаю

it = std::find(adj_list[u_idx].begin(), adj_list[u_idx].end(), v);
adj_list[u_idx].erase(it);

Мне также нужна структура данных для хранения весов, соответствующих ребрам.Первоначально я думал о создании другого вектора векторов std::vector<std::vector<double>> weights, но, похоже, это не самое эффективное решение.Добавить новый элемент в веса просто, как и выше.Все, что мне нужно сделать, это weights[u].push_back(weight_to_add).Но удалить вес из весов кажется немного сложнее, чем делать то, что я делал выше, то есть найти итератор, а затем использовать этот итератор для выполнения удаления.Я мог бы найти индекс, соответствующий итератору в adj_list, а затем удалить индекс из весов, но я не знаю, является ли это лучшим способом для этого.

Так что вместо двухПеременные, представляющие список и веса смежности, я думал о создании одного трехмерного вектора, в котором будут храниться как список смежности, так и веса.Вектор вектора векторов.Последнее измерение имеет размер 2, в котором хранятся идентификатор узла, v и соответствующий вес ребра.Так что на самом деле, это может быть просто вектор вектора массивов.Так что-то вроде vector<vector<array<...>>>.Но проблема здесь в том, что v это int, а веса двойные, поэтому, очевидно, я не могу использовать здесь массивы.Я мог бы инкапсулировать два в структуре, а затем сделать что-то вроде vector<vector<my_struct>>.Или, может быть, что-то вроде vector<vector<pair<int,double>>> будет лучше?

Любой совет, как подойти к этой проблеме?

Answer 1

Да, вы можете использовать список смежности пары векторов, чтобы сделать то же самое vector< pair<int, int> > adj[V];

void printGraph(vector<pair<int,int> > adj[], int V) 
{ 
    int v, w; 
    for (int u = 0; u < V; u++) 
    { 
        cout << "Node " << u << " makes an edge with \n"; 
        for (auto it = adj[u].begin(); it!=adj[u].end(); it++) 
        { 
            v = it->first; 
            w = it->second; 
            cout << "\tNode " << v << " with edge weight ="
                 << w << "\n"; 
        } 
        cout << "\n"; 
    } 
}

Answer 2

Использовать

std::vector<std::vector<Entry>> adj_list

с Entry, являющимся

typedef struct {
    int node;
    double weight;

    bool operator == (const int e) const
    {
    return (node == e);
    }
} Entry;