Блог пользователя n8118

Weighted Graph implementation in c++ for n = 10^5.
Автор n8118, история, 9 лет назад, По-английски

How to implement weighted Graph in c++ for higher values of n = 10^5 (n vertices graph)?? If n = 10^3 i generally implement using adjacency matrix or by using vector stl.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

You can implement it using adjacency lists. Something as simple as this works...

// Declare adjacency list

vector<pair<int,int>> E[100005];

// Add an edge u,v with weight w

E[u].push_back({v,w});

// Process all edges u,v with cost w from node u

for(pair<int,int> p : E[u])
{
    int v = p.first, w = p.second;

    // Do something...
}
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Thanks a lot!!

    → Ответить
  • »
    »
    2 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится -36 Проголосовать: не нравится

    It only works for a directional graph.

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      i think you need to understand how the code above works instead of just taking it its basically creating an array of vectors every slot of the array represent a node so lets say i want to add a link from node u to node v then i will just push v in the uth slot thats why i need to do something like this: e[u].push_back({v, whatever_weight}) now, we want to make undirected graph just instead just adding u to slot v we also add v to slot u so conclusion just add e[v].push_back({u, w}) as well to make an undirected graph

      → Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

My bad

→ Ответить