Weighted graph implementation in C++

Below is an implementation of a weighted graph in C++.

Let’s consider the following weighted graph:

           389
      0 --------- 1
      |           |
      |           |
  405 |           | 818
      |           |
      |           |
      2 --------- 3
           765

The following code in C++ 4.9.2 builds and prints that graph. The idea is to use the adjaceny list representation. Each adjacency list stores stores pairs (neighbor_id, weight).

#include <bits/stdc++.h>
using namespace std;

const int N = 4;
vector<pair<int, int> > adj[N];

int main(){
        // The following two lines are for a faster io with cin and cout
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	// build the graph
	adj[0].push_back(make_pair(1, 389));
	adj[0].push_back(make_pair(2, 405));

	adj[1].push_back(make_pair(0, 389));
	adj[1].push_back(make_pair(3, 818));

	adj[2].push_back(make_pair(0, 405));
	adj[2].push_back(make_pair(3, 765));

	adj[3].push_back(make_pair(1, 818));
	adj[3].push_back(make_pair(2, 765));


	// print the graph
	int v, w;

	for (int u=0; u<N; u++) {
	    cout << "Node u=" << u << " has the following neighbors:\n";

	    for (auto it=adj[u].begin(); it!=adj[u].end(); it++) {
	        v = it->first;
	        w = it->second;
	        cout << "\tNode v=" << v << " with edge weight w=" << w << "\n";
	    }

	    cout << "\n";
	}

	return 0;
}

You can try out the code here. The output is

Node u=0 has the following neighbors:
	Node v=1 with edge weight w=389
	Node v=2 with edge weight w=405

Node u=1 has the following neighbors:
	Node v=0 with edge weight w=389
	Node v=3 with edge weight w=818

Node u=2 has the following neighbors:
	Node v=0 with edge weight w=405
	Node v=3 with edge weight w=765

Node u=3 has the following neighbors:
	Node v=1 with edge weight w=818
	Node v=2 with edge weight w=765

4 thoughts on “Weighted graph implementation in C++

      • the code only works if you select the c++ option which uses clang 3.7 compiler but if you select other c++ compiler like gcc 5.1 which is the default compiler in linux , the code doesn’t work; the c++ option you recommend is not a standard version of the c++ compiler

  1. //stl representation of weighted bidirected weighted graph
    #include
    using namespace std;
    vector<pair >graph[20];
    int visited[20];
    void dfs(int beg)
    { visited[beg]=1;
    for(int i=0;i<graph[beg].size();i++)
    { if(!visited[graph[beg][i].first])
    { cout<“<<graph[beg][i].first<<" "<<graph[beg][i].second<<" "<<graph[beg][i].first;
    dfs(graph[beg][i].first);
    }
    }
    }
    int main()
    { int n,e,u,v,w;
    cout<>n;
    cout<>e;
    cout<>u>>v>>w;
    graph[u].push_back(make_pair(v,w));
    graph[v].push_back(make_pair(u,w));
    }
    cout<<0;
    dfs(0);
    }/

Leave a comment