Хранение графа и динамический массив списков на C++.

[Fiamma]

Доброго времени суток.

Товарищи, поделитесь опытом, как хранить неориентированный граф в виде списка смежности? Только не в теории или алгоритмами, а на практике.
Мне же придумалось следующее. Создаем две структуры:

        struct _Rebro                                    //Структура "Ребро"
        {
                _Vershina *Sv_V;               //Указатель на связанную вершину
                _Rebro *Next_R;                //Указатель на следующее ребро
        };
        struct _Vershina                         //Структура "Вершина"
        {
                int Curr_V;                        //Номер текущей вершины
                _Vershina *Next_V;            //Номер следующей вершины
                _Rebro *List_dug;              //Указатель на список ребер, исходящих из вершины
        };

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

type 
  uk_versh = ^vershina;
  uk_duga = ^duga

vershina = record 
  spisok_dug : uk_duga
end;

duga = record 
  konec_dugi : uk_versh;
  sled_duga : uk_duga;
end;

Но как осуществить это на С++? Помогите, пожалуста.

[Son Of Pain]

Раз уж речь идет о c++,

struct vertex
{
   int id; //номер вершины, или какие там еще данные о ней нужно хранить
   std::list<vertex*> linked; //можно хранить в списке не указатели, а номера 
             //связанных вершин, но с указателями работать будет эффективнее
};
...
list<vertex> all_vertexes; //список всех вершин

[Fiamma]

Интересная мысль.
А как в таком случае объявлять переменные типа Vertex? Пишу в Borland C++ Builder 6, компилятор утверждает, что "Undefined structure Vertex":

struct Vertex;                       
        {
                int No;                     //Номер текущей вершины
                list<Vertex*> linked;   //Список вершин, с кот. она связана
        };
        list<Vertex*> all_V;            //Список всех вершин

...

Vertex *S = new Vertex;

[Son Of Pain]

Убери точку с запятой в первой строчке )

[Fiamma]

Да, действительно, все было так просто.

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

Вот мои безуспешные попытки реализовать это:

//Создание списков смежных вершин
         for (i= 0; i<N; i++)
         {
                for (j= 0; j<M; j++)
                {
                        if (Shema [i][j]==0)     //Если текущая вершина - проход
                        {
                                for (iter1= all_V.begin(); iter1!=all_V.end(); iter1++)  //Находим вершину с текущим номером
                                {
                                        if (*iter1->No== i*M+j)
                                        {
                                                if (j-1>=0 && Shema[i][j-1]==0) //И вершина слева - проход
                                                {
                                                        for (iter2= all_V.begin(); iter2!=all_V.end(); iter2++)  /Находим вершину с номером вершины слева
                                                        {
                                                                if (*iter2->No == i*M+(j-1))
                                                                {
                                                                        *iter1->linked.push_front(iter2); //Связываем вершины
                                                                        *iter2->linked.push_front(iter1);
                                                                };
                                                        };
                                                };

ps. Shema - матрица-схема лабиринта. Если Shema[i][j] == 1 - то в этой ячейке лабиринта стена, если Shema[i][j] == 0 - то, соответственно, там проход. нужно связать соседние ячейки с проходами.

pps.up

[Son Of Pain]

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

//поскольку номер вершины совпадает с индексом массива - его можно не хранить в структуре.
//тогда там останется только одно поле - массив с номерами смежных вершин (vector<int>).
//Следовательно, структуру можно и не объявлять, а просто создать двойной массив:
std::vector<std::vector<int> > data;
//выделить в нем место для всех вершин
data.resize(M*N);

//и тогда твой код будет выглядеть примерно так
         for (i= 0; i<N; i++)
         {
                for (j= 0; j<M; j++)
                {
                        if (Shema [i][j]==0)     //Если текущая вершина - проход
                        {
                                                if (j-1>=0 && Shema[i][j-1]==0) //И вершина слева - проход
                                                {
                                                                data[i*M+j].push_back(i*M+j-1);
                                                        }

[Fiamma]

Спасибо Вам большое за идею со списками. Я по опыту работы с паскалем пыталась изобрести их сама, а оказывается все уже придумано. Списки или векторы, наверное, - одно из самых часто используемых решений? Просветите начинающую программистку))

И вот еще какой вопрос. Правильно ли я понимаю, что тип итератора должен совпадать с типом хранимых в списке объектов? И как вообще работать с итератором? Я пытаюсь распечатать значения списка типа int - пришлось все-таки хранить номера вершин, ибо рекурсия в объявлении структуры сбивает с толку и меня, и компилятор - он говорит, что ошибка в модуле list 0__0. А мне выдается ошибка
[C++ Error] Unit_main.cpp(220): E2094 'operator+' not implemented in type 'list<int,allocator<int> >' for arguments of type 'int'

        for (i= 0; i<Col_V; i++) //Я сделала динамический массив структур, 
        {                            //Col_V - количество элементов в этом массив
                for (j= 0; j<all_V[i]->linked.size(); j++) //Обход элементов списка-поля структуры
                {
                        cout << all_V[i]->linked[j] << " "; \\Потоковый вывод, где и обнаруживается ошибка
                };
        };

Хотя при поиске примеров в интернете находила только такие примеры вывода числовых списков.

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

vector < vector<int> > g; // граф
int n; // число вершин
int s; // стартовая вершина (вершины везде нумеруются с нуля)
 
// чтение графа
...
//Непосредственно обход графа
queue<int> q;
q.push (s);
vector<bool> used (n);
vector<int> d (n), p (n);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
	int v = q.front();
	q.pop();
	for (size_t i=0; i<g[v].size(); ++i) 
         {
		int to = g[v][i];
		if (!used[to]) 
                {
			used[to] = true;
			q.push (to);
			d[to] = d[v] + 1;
			p[to] = v;
		};
	};
};

Теперь его нужно адаптировать под мою задачу. Но тут опять проблема возникает с несоответствием типов, а также с обращением к элементам вектора. Помогите, пожалуйста. До сдачи курсовой осталось 2е суток, а по сути работы еще не пахано(( Обратиться больше не к кому - знакомых программистов нет, а однокурсники сами те еще нубы))

[_Ч_]

cout << all_V[i]->linked[j] << " "; \\Потоковый вывод, где и обнаруживается ошибка

тип переменной linked - std::list<Vertex*> (или std::list<int>?). у списка нет операции обращения по индексу (operator []), поэтому компилятор и ругается. вашем случае надо

for (i= 0; i<Col_V; i++) //Я сделала динамический массив структур, 
{                            //Col_V - количество элементов в этом массив
  const std::list<int>& linked = all_V[i];
  for (std::list<int>::const_iterator it = linked.begin(); it != linked.end(); ++it) //Обход элементов списка-поля структуры
  {
    cout << *it << " "; \\Потоковый вывод, где и обнаруживается ошибка
  };
};

в std контейнерах типы итераторов получаются из типов контейнеров:
std::vector<int>::iterator
std::list<bool>::iterator
std:eque<char>::iterator

итерируются по контейнерам примерно так:
list<int> lst;
// fill list here
for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it)
{
*it = 0; // обнуляем значение в списке или делаем что-то другое.
}

для других контейнеров код такой же
vector<char> vec;
for (vector<char>::iterator it = vec.begin(); it != vec.end(); ++it) ...

deque<bool> deq;
for (deque<bool>::iterator it = deq.begin(); it != deq.end(); ++it) ...

к итераторам можно применять операции, которые похожи на операции с указателями:
*iterator - разыменование итератора.
iterator->member - итератор указывает на класс/структуру, у которой есть мембер. такая запись - обращение к этому мемберу.
всякие инкременты/декременты, в зависимости от свойств итератора.
если нужен указатель на то, на что указывает итератор, то нужно его сперва разыменовать и потом взять адрес у полученной ссылки.
std::list<int> lst;
std::list<int>::iterator it = lst.begin();
int* p = &*it;

[Son Of Pain]

Сообщение от Fiamma

Списки или векторы, наверное, - одно из самых часто используемых решений?

Да, это наиболее распространенные структуры данных

Правильно ли я понимаю, что тип итератора должен совпадать с типом хранимых в списке объектов?

Ну обычно если контейнер vector<int>, то тип итератора должен быть vector<int>::iterator (или const_iterator, или reverse_iterator, или const_reverse_iterator). Для других контейнеров так же.
А начиная с 2010 студии (и в последних версиях gcc) реализовали очень полезную штуку из нового стандарта, и теперь можно писать просто

auto iter=data.begin();

Но борландовский компилятор этого не умеет, конечно.

ибо рекурсия в объявлении структуры сбивает с толку и меня, и компилятор

Компилятор она точно не должна сбивать с толку ) Единственное - не все компиляторы нормально воспринимают объявление vector<vector<int>>, тогда между знаками > нужно оставить пробел.

Я пытаюсь распечатать значения списка типа int

Каноничный для c++ способ -

        for (i= 0; i<Col_V; i++) //Я сделала динамический массив структур, 
        {                            //Col_V - количество элементов в этом массив
                copy(all_V[i]->linked.begin(), all_V[i]->linked.end(), ostream_iterator<int>(cout, " "));
        };

Можно и первый цикл убрать в for_each, в принципе, но это уже слишком 'функционально' для c++ )

Хотя при поиске примеров в интернете находила только такие примеры вывода числовых списков.

Не совсем такие ) Одно из отличий списка от вектора состоит в том, что у него внутри bidirectional iterators, а у вектора - random access iterators. Если не вдаваться в детали, то для нас главный видимый эффект - к

элементам списка нельзя обращаться через квадратные скобки, как к элементам массива. Было бы поле linked типа vector<int> - пример бы работал.
Компилятор разворачивает обращение linked[i] в *(linked+i*element_size) (если у linked не перегружен operator[], конечно). Отсюда и появляется странное упоминание оператор+ в сообщении об ошибке.
А код с copy будет работать совсем без изменений для всех контейнеров, кстати. В этом и прелесть стандартных алгоритмов .