Какова лучшая стандартная структура данных для построения графика?

Question

Сначала я начинающий в C ++, и я самообучаюсь, поэтому, пожалуйста, будьте довольно просты в ответах ...

мне нужно запрограммировать граф, который содержит узлы, каждый узел имеет идентификатор и список ребер, у каждого ребра есть идентификатор другого узла и расстояние

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

Я много искал и сейчас очень растерялся

Заранее спасибо за помощь

Answer 1

Вы можете определить структуру Edge как

struct Edge
{
    int destination;
    int weight;
};

И создать график как

vector<vector<Edge> > graph;

Затем, чтобы получить доступ ко всем ребрам из вершины u, вы пишете что-то вроде

for( int i = 0; i < graph[u].size(); ++i ) {
    Edge edge = graph[u][i];
    // here edge.destination and edge.weight give you some details.
}

Вы можете динамически добавлять новые ребра, например ребро из 3-й вершины в 7-е с весом 8:

Edge newEdge;
newEdge.destination = 7;
newEdge.weight = 8;
graph[3].push_back( newEdge );

и т.д.

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

Это должно быть хорошо.

Редактировать Выбор базовых контейнеров (std::vector, std::list, std::map) зависит от варианта использования, например, что вы делаете с графиком чаще: добавление / удаление вершин / ребер, просто обход. Как только ваш график создан, либо std::list, либо std::vector одинаково хороши для Дейкстры, std::vector - немного быстрее благодаря схеме последовательного доступа стадии релаксации.

Answer 2

график, который содержит узлы, у каждого узла есть идентификатор и список ребер, у каждого ребра есть идентификатор другого узла и расстояние

Если мы рассматриваем каждый идентификатор узла как индекс.Мы можем нарисовать матрицу nxn ребер следующим образом.

Это может помочь вам нарисовать график с ребрами.

     [0][1][2][3]

[0] | 1  0  0  0|
[1] | 0  0  1  0|
[2] | 1  0  0  1|
[3] | 0  0  1  0|

Итак, двумерный массив является хорошим представлениемматрица.

int maxtrix[4][4] = new int[4][4];

Answer 3

Я бы лично использовал std::map<Node*, std::set<Node*> >.Это чрезвычайно полезно, потому что каждый раз, когда вы находитесь на узле, вы можете быстро узнать, к каким узлам этот узел подключен.Также очень легко перебирать все узлы, если вам нужно.Если вам нужно наложить гири по краям, вы можете использовать std::map<Node*, std::set< std::pair<int, Node*> > >.Это даст намного лучшую производительность, чем использование векторов, особенно для больших графиков.