邻接列表使用向量和对的图表表示 [英] Adjacency list Graph representation using vector and pair

问题描述

我想实现书竞争性编程1中的邻接表图表示。实现使用V个顶点的向量，并且对于每个顶点v，另一个
向量包含（邻近顶点和它的边权重）有连接
到vI有问题需要输入这个图表并显示输出。

在这本书中，他们做了这样的声明： / p>

  #include< iostream> 
 #include< vector> 
使用namespace std; 
 typedef pair< int，int> II; 
 typedef vector< ii>七; 
 vector< vii> AdjList; 
  

如何输入以下图形作为邻接列表并输出邻接列表表示？假设每个边缘成本为10美元。b
$ b

图形的各种表示形式http://img35.imageshack.us/img35/8370/edrp.png

解决方案

如果我们想使用图形邻接实现以n个顶点和m个边缘的形式读取图形输入。

 ＃include< ;&的iostream GT; 
＃include< vector> 
使用namespace std; 
 typedef vector< int>六; 
 typedef pair< int，int> II; 
 typedef vector< ii>七; 
 
 int main（）
 {
 int n，m; 
 cin>> n>> m; 
 vector< vii> adjList（N + 1）; //对于顶点1 ... n 
 //读取输入图的边
（int i = 0; i  {
 int u ，v; 
 cin>> u>> v; 
 / *这里u-> v是边和第二项可用于存储加权图的
情况下的权重。 
 * / 
 adjList [u] .push_back（make_pair（v，10））; 
} 
 //打印存储在邻接列表中的边
 for（int i = 1; i <= n; i ++）
 {
 for（int j = 0; j <（int）adjList [i] .size（）; j ++）
 {
 cout <<<边缘是<< - > << adjList [i] [j]。首先<< ENDL; 
 cout<<Weight is<< adjList [i] [j] .second<< endl; 
} 
} 
返回0; 
} 
  

I want to implement the adjacency list graph representation from the book competitive programming 1.The implementation uses a vector of V vertices and for each vertex v,another vector that contains pairs of (neighboring vertex and it’s edge weight) that have connection to v.I am having problems to take input of this graph and showing the output.

In the book,they have done such declarations :

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

How should I take input of the following graph as adjacency list and output it's adjacency list representation ? Suppose , every cost of edge is 10.

Various representation of graphs http://img35.imageshack.us/img35/8370/edrp.png

解决方案

If we want to read graph input in form of n vertices and m edges using graph adjacency implementation.

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

这篇关于邻接列表使用向量和对的图表表示的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！