4

本の競争力のあるプログラミングから隣接リストグラフ表現を実装したい1.実装では、V頂点のベクトルを使用し、各頂点vに対して、vに接続する（隣接する頂点とそのエッジの重み）のペアを含む別のベクトルを使用します。このグラフの入力を取得して出力を表示するのに問題があります。

本の中で、彼らはそのような宣言をしました:

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
vector <vii> AdjList;

次のグラフの入力を隣接リストとして取得し、隣接リスト表現を出力するにはどうすればよいですか? エッジのすべてのコストが 10 であるとします。

グラフのさまざまな表現

4

1 に答える 1

8

グラフ隣接実装を使用して 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;
}
于 2014-08-12T07:17:18.140 に答える