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
this fucking code aint running
The code works, e.g. try the code on http://ideone.com and make sure you use the latest C++ version.
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
//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);
}/