通过c stl中的邻接列表正确实现图形-Java 学习之路

我试图通过C的STL中的邻接列表来表示基本的无向图 . 这是我的代码：

#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;
 }

在上面的代码中，我试图打印每个顶点及其每个边缘，编译器打印一些东西，然后进入一些内存错误或无限循环.eg . 输入上述程序V = 4 E = 4并且边缘与重量一致

预期产量 -

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

但输出是

1
2->5

然后是内存错误或无限循环 . 请建议改进我的代码？

谢谢！

2 回答

1

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

此语句无效，因为 it 的类型为 vector<pair<int,int> >::iterator . 所以 *it 的类型为 pair<int,int> ，你不能使用 %d 打印它，它需要 int .

试试这样的东西 printf("%d %d",it->first, it->second);

回复于 2024-04-28T02:08:45+08:00
0
主要问题是您不打印原点顶点的数量（它不包含在 graph[i] 中，但它本身是 i ） . 第二个错误是打印 *it （a std::pair ）而不是 it->first （实际的 int ），正如Ashot所解释的那样 .
一种可能性就是像这样编写最后一个循环：
```
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] 是一个空向量 . 所以你用 graph[2].begin() 初始化迭代器 ìt ，它等于 graph[2].end() . 作为结果，
- 检查 while(it+1!= graph[2].end()) 将始终返回true（ it+1 将开始一个位置BEHIND graph[2].end() ） .
- printf("%d->",*it); 取消引用指向无效内存位置的指针 .
回复于 2024-04-28T02:08:45+08:00

通过c stl中的邻接列表正确实现图形

2 回答

相关问题