Составление списка смежности в C ++ для ориентированного графа

Привет всем :) Сегодня я совершенствую свои навыки в теории графов и структурах данных. Я решил сделать небольшой проект на C ++, потому что я давно работал с C ++.

Я хочу сделать список смежности для ориентированного графа. Другими словами, что-то похожее на:

0-->1-->3
1-->2
2-->4
3-->
4-->

Это был бы ориентированный граф с V0 (вершина 0), имеющим ребро к V1 и V3, V1, имеющее ребро к V2, и V2, имеющее ребро к V4, вот так:

V0----->V1---->V2---->V4
 |
 |
 v
 V3 

Я знаю, что для этого мне нужно будет создать список смежности в C ++. Список смежности в основноммассив связанных списков, Хорошо, давайте посмотрим некоторый псевдо-код C ++:

#include <stdio>
#include <iostream>
using namespace std;

struct graph{
//The graph is essentially an array of the adjList struct.  
node* List[];

};

struct adjList{
//A simple linked list which can contain an int at each node in the list.

};

struct node {
int vertex;
node* next;
};

int main() {
//insert cool graph theory sorting algorithm here
}

Как вы можете сказать, этот псевдокод в настоящее время далек от цели. И это то, что я хотел помочь - указатели и структуры в C ++ никогда не были моей сильной стороной. Прежде всего, это заботится о вершинах, на которые указывает вершина - но как насчет самой вершины? Как я могу отслеживать эту вершину? Когда я зацикливаюсь на массиве, мне бесполезно знать только то, на что указывают вершины, а не знать, на какие точкив их. Первый элемент в каждом списке, вероятно, должен быть этой вершиной, а затем элементы после него являются вершинами, на которые он указывает. Но тогда как я могу получить доступ к этому первому элементу списка в моей основной программе? (извините, если это запутанно или запутанно, я бы с удовольствием перефразировал).

Я хотел бы иметь возможность перебрать этот список смежности, чтобы сделать некоторые интересные вещи с графиками. Например, чтобы реализовать некоторые алгоритмы теории графов (сортировки, кратчайшие пути и т. Д.) С использованием представления списка смежности.

(Также у меня возник вопрос о списке смежности. Что отличается от простого использования списка массивов? Почему я не могу просто иметь список с массивом для каждого элемента в списке?)

Ответы на вопрос(5)

Ваш ответ на вопрос