Advertisement
alanchua

Using Adjacency List to represent Graph

Jul 20th, 2017
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. /*
  2.  
  3. 4 5
  4. 1 2
  5. 1 3
  6. 2 3
  7. 3 4
  8. 4 2
  9. Edge is 1 -> 2
  10. Weight is 10
  11. Edge is 1 -> 3
  12. Weight is 10
  13. Edge is 2 -> 3
  14. Weight is 10
  15. Edge is 3 -> 4
  16. Weight is 10
  17. Edge is 4 -> 2
  18. Weight is 10
  19.  
  20. */
  21.  
  22. // From above, First line is number of vertex and number of edges (4 Vertices, 5 Edges)
  23. // The rest of the 5 lines refer to the edges,
  24. // 1 2 mean 1 connect to 2, 1 connect to 3 etc
  25.  
  26. #include <bits/stdc++.h>
  27. using namespace std;
  28.  
  29. typedef vector<int> vi;       // vector of int
  30. typedef pair<int,int> ii;     // pair
  31. typedef vector<ii> vii;       // vector of pairs
  32.  
  33. int main()
  34. {
  35.    int n,m ; // n is the number of Vertices, m is the number of Edges
  36.    cin>>n>>m;
  37.    vector<vii> adjList(n+1); //For vertex 1...n. vector of vector pairs
  38.    //Reading edges for the input for graph
  39.    for(int i=0;i<m;i++)
  40.    {
  41.       int u,v;
  42.       cin>>u>>v;
  43.     /*Here u->v is the edge and pair second term can be used to store weight in
  44.       case of weighted graph.
  45.     */
  46.       adjList[u].push_back(make_pair(v,10));
  47.    }
  48.    //To print the edges of every nodes stored in the adjacency list
  49.    for(int i=1;i<=n;i++)
  50.    {
  51.        for(int j=0;j<(int)adjList[i].size();j++)
  52.        {
  53.            cout<<"Edge is "<<i<<" -> "<<adjList[i][j].first<<endl;
  54.            cout<<"Weight is "<<adjList[i][j].second<<endl;
  55.        }
  56.    }
  57.    return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement