Правильная реализация графа через список смежности в С++ stl

Я пытаюсь представить базовый неориентированный граф через список смежности в STL C++. Вот мой код:

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
   {
       int no_vertices,no_edges;

       printf("Enter the no. of vertices and Edges : ");
       scanf("%d%d",&no_vertices,&no_edges);

       vector<pair<int,int> > graph[no_vertices];
       //Pair because we edge along with its weight!!

       printf("\nEnter the Edges along with their weight :");

       int s,d,weight;

       for(int i=0;i<no_edges;i++)
         {

           scanf("%d%d%d",&s,&d,&weight);
           graph[s].push_back(pair<int,int>(d,weight));

         }

       for(int i=0;i<no_vertices;i++)
          {
            vector<pair<int,int> >::iterator it = graph[i].begin();

            cout<<endl;

            while(it+1!= graph[i].end())
               {
                 printf("%d->",*it);
                 it++;
               }

            printf("%d",*it);

          }

     return 0;
 }

В приведенном выше коде я пытаюсь напечатать каждую вершину вместе с каждым ее ребром, компилятор что-то печатает, а затем переходит в какую-то ошибку памяти или бесконечный цикл. Например. ввод в приведенной выше программе V=4 E=4 и ребра вместе с весом

0 1 4
1 2 5
1 5 2
3 1 3

Ожидаемый результат-

0->1
1->2->5
2
3->1

но выход есть

1
2->5

а затем ошибка памяти или бесконечный цикл. Пожалуйста, предложите улучшения в моем коде ??

–

Спасибо!


c++ graph adjacency-list stl
person Sameer Agarwal    schedule 18.01.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

printf("%d->",*it)

Это утверждение неверно, поскольку it имеет тип vector<pair<int,int> >::iterator. Таким образом, *it имеет тип pair<int,int>, и вы не можете напечатать его, используя %d, который ожидает int.

Попробуйте что-то вроде этого printf("%d %d",it->first, it->second);

person Ashot    schedule 18.01.2015
comment
Я думаю, что Самир хранит пункт назначения и вес, а не источник и пункт назначения в паре. - person MikeMB; 18.01.2015

arrow_upward
0
arrow_downward

Основная проблема заключается в том, что вы не печатаете номер исходной вершины (она не входит в graph[i], но сама является i). Вторая ошибка заключается в печати *it (std::pair) вместо it->first (фактического int), как объяснил Ашот.
Одна из возможностей — написать последний цикл следующим образом:

    cout << endl;
    for (int i = 0; i<no_vertices; i++)
    {
        printf("%d", i);
        for (auto& e: graph[i]) {
            printf("->%d", e.first);
        }
        cout << endl;
    }

Явное использование итераторов:

cout << endl;
for (int i = 0; i<no_vertices; i++)
{
    printf("%d", i);
    vector<pair<int, int> >::iterator it = graph[i].begin();
    vector<pair<int, int> >::iterator it_end = graph[i].end();
    for (; it != it_end; it++) {
        printf("->%d", it->first);
    }
    cout << endl;
}

Хотя приведенный выше код решит вашу проблему, я, вероятно, не объяснил должным образом, почему ваш текущий код выдает ошибку: поскольку исходный узел не является частью векторов, graph[2] является пустым вектором. Итак, вы инициализируете итератор ìt значением graph[2].begin(), равным graph[2].end(). Как следствие,

  1. проверка while(it+1!= graph[2].end()) всегда будет возвращать истину (it+1 будет начинаться на одну позицию ЗА graph[2].end()).
  2. printf("%d->",*it); разыменовывает интератор, указывающий на недопустимую ячейку памяти.
person MikeMB    schedule 18.01.2015
comment
@Sameer: ​​диапазон на основе цикла for (en.cppreference.com/w/cpp /language/range-for) скрывает механику итератора и делает код (на мой взгляд) более читабельным, но если хотите, могу дать версию с явным итератором. - person MikeMB; 18.01.2015
comment
Также, если вы могли бы, пожалуйста, отправьте меня на хороший учебник по итератору. Я не могу понять, как именно используется итератор и как он работает. - person Sameer Agarwal; 18.01.2015
comment
Также, если я использую следующий цикл вместо вашего, то есть for (int i = 0; i‹no_vertices; i++) { printf(%d, i); if(!graph[i].empty()) { vector‹pair‹int,int› ›::iterator it = graph[i].begin(); while(it != graph[i].end()) { cout‹‹-›‹‹graph[i].first//Ошибка в этой строке говорит, что функция-член стоит первой! это++; } } cout ‹‹ endl; } - person Sameer Agarwal; 19.01.2015
comment
@Самир: Готово. К сожалению, я не могу указать вам хороший источник для итераторов. Если вы новичок в C++, я могу порекомендовать A Tour of C++ (C++ In-Depth) Бьерна Страуструпа. - person MikeMB; 19.01.2015
comment
Спасибо @MikeMB. Кроме того, почему я не могу напрямую сравнить его с graph[i].end() и явно определить iterator_end?? - person Sameer Agarwal; 19.01.2015
comment
Можно (и, наверное, нужно). - person MikeMB; 19.01.2015