Модуль: Графы. Начало


Задача

2/13

Хранение взвешенных графов (C++)

Теория Нажмите, чтобы прочитать/скрыть

Взвешенный граф


 

Во взвешенном графе, помимо самих ребер и их направления, каждое ребро обладает также весом или стоимостью. Существует несколько способов хранения списка вершин во взвешенном графе:

  1. Матрица смежности. В этом способе граф представляется в виде двумерной матрицы, где строки и столбцы соответствуют вершинам графа, а элементы матрицы содержат информацию о весе ребер между вершинами. Если между вершинами нет ребра, то соответствующий элемент матрицы будет иметь значение "бесконечность" или другое специальное значение.

  2. Список смежности. В этом способе каждая вершина представляется в виде списка, содержащего пары (или кортежи) вершин, с которыми она имеет ребра, и их соответствующие веса. Например, для вершины A список смежности может выглядеть как [(B, 5), (C, 3)], что означает наличие ребра с весом 5 к вершине B и ребра с весом 3 к вершине C.

  3. Список ребер: В этом способе граф представляется в виде списка всех его ребер, где каждое ребро содержит информацию о вершинах, которые оно соединяет, и его весе. Например, [(A, B, 5), (A, C, 3)].

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

Задача

По заданному изображению ориентированного графа сформируйте список смежных вершин для всех вершин. Вершины добавляйте в порядке возрастания.
 
 


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
	
int main() 
{
	int n, m, s, f;
	const int V = 4;
	vector< vector < pair <int, int>>>  adj(V+1);

	adj[1].push_back({ 2,5 });
	// остальные ребра добавьте сами в порядке возрастания вершин     
	for (size_t i = 1; i <= V; i++)
	{
		cout << i << ": ";
		for (auto x : adj[i])
			cout << "-> " << x.first << "("<<x.second<<")";
		cout << "\n";
	}

	return 0;
}

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!