Рубрики

Реализация графов с использованием STL для конкурентного программирования | Набор 2 (Весовой график)

В наборе 1 обсуждается невзвешенный граф. В этом посте обсуждается представление взвешенного графа с использованием STL. Реализация предназначена для представления списка смежности взвешенного графа.

Мы используем два контейнера STL для представления графика:

  • вектор: контейнер последовательности. Здесь мы используем его для хранения списков смежности всех вершин. Мы используем номер вершины в качестве индекса в этом векторе.
  • pair: простой контейнер для хранения пары элементов. Здесь мы используем его для хранения номера соседней вершины и веса ребра, соединяющегося с соседним.

Идея состоит в том, чтобы использовать вектор парных векторов. Ниже код реализует то же самое.

// C ++ программа для представления неориентированного и взвешенного графа
// используя STL. Программа в основном печатает список смежности
// представление графа
#include <bits/stdc++.h>

using namespace std;

  
// Добавить ребро

void addEdge(vector <pair<int, int> > adj[], int u,

                                     int v, int wt)

{

    adj[u].push_back(make_pair(v, wt));

    adj[v].push_back(make_pair(u, wt));

}

  
// Распечатка списка смежных представлений на графике

void printGraph(vector<pair<int,int> > adj[], int V)

{

    int v, w;

    for (int u = 0; u < V; u++)

    {

        cout << "Node " << u << " makes an edge with \n";

        for (auto it = adj[u].begin(); it!=adj[u].end(); it++)

        {

            v = it->first;

            w = it->second;

            cout << "\tNode " << v << " with edge weight ="

                 << w << "\n";

        }

        cout << "\n";

    }

}

  
// Код драйвера

int main()

{

    int V = 5;

    vector<pair<int, int> > adj[V];

    addEdge(adj, 0, 1, 10);

    addEdge(adj, 0, 4, 20);

    addEdge(adj, 1, 2, 30);

    addEdge(adj, 1, 3, 40);

    addEdge(adj, 1, 4, 50);

    addEdge(adj, 2, 3, 60);

    addEdge(adj, 3, 4, 70);

    printGraph(adj, V);

    return 0;

}

Выход:

Node 0 makes an edge with 
    Node 1 with edge weight =10
    Node 4 with edge weight =20

Node 1 makes an edge with 
    Node 0 with edge weight =10
    Node 2 with edge weight =30
    Node 3 with edge weight =40
    Node 4 with edge weight =50

Node 2 makes an edge with 
    Node 1 with edge weight =30
    Node 3 with edge weight =60

Node 3 makes an edge with 
    Node 1 with edge weight =40
    Node 2 with edge weight =60
    Node 4 with edge weight =70

Node 4 makes an edge with 
    Node 0 with edge weight =20
    Node 1 with edge weight =50
    Node 3 with edge weight =70

Эта статья предоставлена Сахилом Чхаброй (Акку) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Реализация графов с использованием STL для конкурентного программирования | Набор 2 (Весовой график)

0.00 (0%) 0 votes