我想实现竞争性编程 1 书中的邻接列表图表示。该实现使用 V 顶点的向量,并且对于每个顶点 v,另一个
包含有连接的对(相邻顶点及其边权重)的向量
v.我在获取该图的输入并显示输出时遇到问题。
在书中,他们做了这样的声明:
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
vector <vii> AdjList;
我应该如何将下图的输入作为邻接列表并输出它的邻接列表表示?假设 ,每条边的成本为 10。
如果我们想使用图邻接实现以 n 个顶点和 m 个边的形式读取图输入。
#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int main()
{
int n,m ;
cin>>n>>m;
vector<vii> adjList(n+1); //For vertex 1...n
//Reading edges for the input for graph
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
/*Here u->v is the edge and pair second term can be used to store weight in
case of weighted graph.
*/
adjList[u].push_back(make_pair(v,10));
}
//To print the edges stored in the adjacency list
for(int i=1;i<=n;i++)
{
for(int j=0;j<(int)adjList[i].size();j++)
{
cout<<"Edge is "<<i<<" -> "<<adjList[i][j].first<<endl;
cout<<"Weight is "<<adjList[i][j].second<<endl;
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)