Skip to main content

Вопросы с меткой [графы]

Граф - совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

Фильтрация
Сортировка
Метки
-1 голос
1 ответ
62 показа

Списки смежности в джава

При решении задач на графы используются списки смежности. В C++ список смежности находится в массиве векторов: vector<int> adj[n]; и заполняется этот массив векторов так: adj[1].push_back(2); ...
kazosh's user avatar
  • 11
1 голос
1 ответ
130 показов

Задача по графам (BFS)

Подскажите, пожалуйста, как решить вот такую задачку на графы: Условия: Дан массив из целых чисел (-100 000 000 ≤ arr[i] ≤ 100 000 000). Можно перемещаться по массиву вперед и назад на один шаг (i - ...
Илья's user avatar
-2 голоса
1 ответ
399 показов

Задача по графам

Условия: Дан массив из целых чисел (-100 000 000 ≤ arr[i] ≤ 100 000 000). Можно перемещаться по массиву вперед и назад на один шаг (i - 1 или i + 1). Также можно перемещаться по массиву по ...
Alexander Sergeev's user avatar
1 голос
2 ответа
843 показа

Задача о перемещении между островами

Отдыхая в деревне, Пётр мысленно вернулся в детство и вспомнил одну из своих любимых компьютерных игр. В мире этой игры произошёл катаклизм, разорвавший его на множество островов, летающих в ...
Александр's user avatar
0 голосов
0 ответов
113 показов

Поиск в глубину

Дан неориентированный граф, возможно, с петлями и кратными ребрами. Необходимо построить компоненту связности, содержащую вершину с номером 1. Петля в графе - это ребро, которое соединяет вершину с ...
Folombo's user avatar
  • 55
1 голос
1 ответ
95 показов

Отображение направленного графа ( networkx)

Всем привет! Задачка у меня такая: Есть направленный граф из двух вершин A, B, вершины связаны так: A->B = 100 B->A = 50 При отрисовке у меня теряется информация о том, что путь из A->B ...
Shika_meow's user avatar
0 голосов
0 ответов
46 показов

Обход графа в Neo4j с использованием свойств узлов и связей

Есть ориентированный граф, состоящий из узлов с метками Node и связями HAS_CHILD. Связи могут иметь свойство deleted_at. Есть задача обойти этот граф и сделать определенные действия с каждым узлом (...
Платон's user avatar
-2 голоса
1 ответ
39 показов

BFS, решение задачи об обходе матрицы [закрыт]

Мой код решает задачу #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector <vector<int>> g(n+1, vector<int> (m+1, ...
Kirill's user avatar
  • 3
-1 голос
1 ответ
34 показа

С++ DFS, Memory limit [закрыт]

мой код решает задачу: Почему передача массивов по ссылке в DFS вызывает Memory Limit, а их объявление глобально проходит все тесты? Решение с ошибкой: #include <bits/stdc++.h> using namespace ...
Kirill's user avatar
  • 3
0 голосов
1 ответ
88 показов

Гамильтонов цикл в неориентированном графе и генератор неориентированных графов

Задание :Гамильтонов цикл в графе G = (V, E) – это цикл в графе G, содержащий все вершины из V. Найти гамильтонов цикл в заданном неориентированном графе. Исследовать асимптотическую временную ...
sasha vasiliev's user avatar
0 голосов
0 ответов
21 показ

Какой обход должен использоваться в алгоритме Белмана Форда?

обойти граф нужно V-1 кол-во раз но какой обход использовать ? В глубину,в ширину или очередь с приоритетом строить? И нужно ли помечать вершину как пройденная или непройденная?
sashareznik's user avatar
0 голосов
0 ответов
15 показов

Отображение маршрута на графах

пытаюсь сделать навигацию по круизному лайнеру на реакте. Сама карта будет графом, помещения это вершины, пути это ребра. Пока что сделал просто демоверсию Но возник вопрос, как сделать так, чтобы ...
Martin Iden's user avatar
-3 голоса
1 ответ
57 показов

Как найти количество помеченных связных графов? [закрыт]

2 Задача похожа на codeforces 1009D, но только с одним числом в вводе Можете пожалуйста написать способ нахождения помеченных связных графов когда на вход подается только одно число?(если не ...
Elias en's user avatar
2 голоса
1 ответ
192 показа

Компоненты вершинной двусвязности

Дан неориентированный граф без петель в следующем формате: Первая строка - n m (|V|, |E| соответственно) Следующие m строк содержат описание ребер: i u_i v_i. Требуется выделить компоненты вершинной ...
AmEl's user avatar
  • 73
0 голосов
0 ответов
34 показа

максимальный поток в потоковой сети

Решите, является ли следующее утверждение истинным или ложным. Если утверждение истинно, приведите краткое объяснение, а если ложно — приведите контрпример. Пусть G — произвольная потоковая сеть с ...
Ron's user avatar
  • 25
3 голоса
2 ответа
192 показа

Найти все простые циклы планарного графа

Возможно, это и XY-проблема, хотя лично мне так не кажется... Имеется планарный неориентированный граф. По-сути, разбиение некоторого многоугольника на части (это и есть X :)). Задача - найти простые (...
Harry's user avatar
  • 226k
0 голосов
0 ответов
101 показ

Как исправить ошибку. Необходимо находить мосты в графе. Реализация алгоритма

Решаю задачу на поиск мостов в неориентированном графе с возможными кратными ребрами и петлями. Необходимо посчитать и вывести количество мостов а также номера соответсвующих ребер в графе. При ...
Илья Трушкин's user avatar
-2 голоса
1 ответ
45 показов

Код неправильно расчитывает расстояние до 3 и 4 вершин графа

У меня есть код: #include<iostream> #include<vector> #include<fstream> using namespace std; struct kr { int w2; int wg; }; typedef vector<vector<kr> > tgraf; ...
Zayvik's user avatar
  • 1
0 голосов
0 ответов
50 показов

Как отобразить граф в виде правильной треугольной решетки в networkx

Нужно отобразить граф в виде такой решетки: Нужно установить какой-то определенный layout или есть другой способ?
fetcher's user avatar
  • 33
-1 голос
1 ответ
45 показов

питон просит изменить sent.words, т.к. не может найти имя, но всё написано правильно

я разрабатываю граф знаний по текстовым данным. вроде весь код правиильный, но всё равно выдаёт вот такую ошибку for word in sent.words: ^^^^ NameError: name 'sent' is not defined. Did you mean: 'ent'...
Екатерина Попова's user avatar
0 голосов
0 ответов
88 показов

Поиск кратчайшего пути из одной вершины графа в другую

Помогите решить задачку на python: n - количество вершин в графе. n-1 - количество рёбер в графе, соединяющих вершины. Сначала пользователю предлагается ввести количество вершин. После пользователь ...
Alina Mokhna's user avatar
1 голос
1 ответ
73 показа

Некорректно работает алгоритм Дейкстры

Код должен работать для взвешенного неориентированного графа, состоящего из n вершин и m ребер. Вершины пронумерованы целыми числами от 1 до n. Необходимо найти длину кратчайшего пути из вершины с ...
Василий Захаров's user avatar
0 голосов
0 ответов
96 показов

Алгоритм Форда-Беллмана работает некорректно на некоторых тестах. Не могу понять в чём ошибка

уже очень долго сижу и не могу понять, где ошибка в моей реализации алгоритма Беллмана-Форда. Задан ориентированный граф, в нём не может быть петель и кратных рёбер. Необходимо найти длину кратчайшего ...
Василий Захаров's user avatar
0 голосов
0 ответов
56 показов

Алгоритм оптимального обхода графа с условием

Есть граф без отрицательных весов. Нужно из одной вершины в другую найти оптимальный путь и чтобы в цепи обязательно присутствовала вершина по условию. То есть оптимальный путь обязательно проходящий ...
Никита Секушин's user avatar
0 голосов
1 ответ
148 показов

Задача о подсчете дорог, код выдаёт неверный ответ

Всем привет, решала следующую задачу: ограничение по времени 1 секунда ограничение по памяти 256 мегабайт В Ваканде есть N городов, некоторые из которых соединены дорогами. Король решил провести ...
Настя's user avatar
0 голосов
0 ответов
54 показа

Удаление циклов из графа в SQL

Предположим, у вас есть таблица рёбер со столбцами A и B, в которых указаны номера вершин, соединенных ребром. Как выбрать из неё ребра так, чтобы в выборке не оказалось ни одного ребра, создающего ...
Виталий Яндулов's user avatar
-2 голоса
1 ответ
392 показа

Задача из яндекс контест по графам. 2 варианта кода, один проходит все тесты другой нет, почему?

Ниже представлены два кода, тот, что на Python мой. На плюсах взял из инета. Алгоритм на плюсах проходит все тесты. Мой не проходит 6 тест (не знаю точно какие входные данные). Помогите разобраться в ...
Artem Ishmukhamedov's user avatar
3 голоса
2 ответа
284 показа

Графы, подсчёт изолированных вершин с помощью матрицы смежности, код выдаёт неверный ответ

решала следующую задачу: На острове расположены несколько государств, изолированных друг от друга. У программиста Васи есть данные обо всех дорогах острова, заданные в виде весовой матрицы ...
Настя's user avatar
0 голосов
3 ответа
291 показ

Помогите с задачей с++ или питон на графы

Постройте какой-нибудь неориентированный граф из N вершин содержащий K компонент связности. пример ввод 5 2 вывод 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 Входные данные Даны два числа N и ...
user504877's user avatar
-1 голос
2 ответа
443 показа

Графы, обход в глубину. Задача "Построение"

Код прошел не все тесты(, скажите, пожалуйста, в чем ошибка https://informatics.msk.ru/mod/statements/view.php?id=256&chapterid=166#1 - задача Группа солдат-новобранцев прибыла в армейскую часть ...
Амогус's user avatar
1 голос
1 ответ
932 показа

Графы, компоненты связности, питон

Мой код прошел не все тесты(( а что не так? вот задача https://informatics.msk.ru/mod/statements/view.php?id=256&chapterid=111540#1 Дан неориентированный невзвешенный граф. Необходимо посчитать ...
Амогус's user avatar
0 голосов
0 ответов
42 показа

Как графически отобразить все нейроны в виде графа?

Основная проблема заключается в том, что не хватает знаний, как можно графически показать в отдельном окне, желательно с интеграцией в pyQt5, нейроны в виде графа, которые получились в процессе ...
KofMan's user avatar
  • 21
0 голосов
0 ответов
65 показов

Удаление ребра в графе и поиск пути

У меня есть неориентированный граф состоящий из n вершин и n ребёр. Мне нужно быстро отвечать на запрос, существует ли путь из точки А в точку В, если я удалю определённое ребро из точки А. Сначала я ...
Отчаявшийся чел's user avatar
0 голосов
1 ответ
694 показа

Графы. зашла в тупик, почти решив задачу

решала такую задачу на графы: В стране 77 городов, некоторые из которых соединены дорогами. При этом из любого города до любого существует путь, в котором ни один город не повторяется, а количество ...
Настя's user avatar
3 голоса
1 ответ
578 показов

доказательство утверждения по эйлеровым циклам

недавно столкнулась с интересным утверждением: а) если в связном графе все вершины четны, то внем существует эйлеров цикл б) если в связном графе не более двух вершин с нечетными степенями, то в нем ...
Настя's user avatar
0 голосов
0 ответов
42 показа

Направление стрелок в графе

Разве здесь стрелки не должны идти в обратном направлении? Мы же сначала просыпаемся, потом чистим зубы, а после завтракаем. На рисунке кажется, будто мы сначала завтракаем, потом чистим зубы, а после ...
Лосось Жареный's user avatar
1 голос
2 ответа
119 показов

Как по матрице смежности нескольких графов найти множество отдлеьных графов?

Пусть граф задаётся как множество вершин = (в1,в2 ...) и есть матрица смежности для подобного набора графов: В данном случае она будет выглядеть так : Как по матрице смежности понять, что граф (в1,...
Space Researcher's user avatar
-3 голоса
2 ответа
169 показов

Задача о кратчайшем пути [закрыт]

Классическая задача, помогите найти подходы к ней Имеется N населенных пунктов , пронумерованных от 1 до N. Некоторые пары пунктов соединены дорогами. вывести самый короткий путь из L-го пункта в M-й....
user549336's user avatar
1 голос
1 ответ
590 показов

Как сделать циклом Функциональный граф?

Добрый день! Помогите пожалуйста или дайте подсказку. Решаю задачу. Условие следующее: В школе перед Новым Годом устраивают игру в Тайного Санту. Каждому ученику i выдается ученик ai, которому он ...
Илья Ким's user avatar
-1 голос
1 ответ
749 показов

Теория графов. Поиск циклов длины 3 и 4

Задан граф матрицей смежности. Необходимо найти циклы длины 3 и 4. Матрица смежности возводится в степень 3 или 4... дальнейший алгоритм мне известен. Однако препод в универе задаёт один вопрос: ...
ЗЕЛЕНЫЙ ИНОПРЕШЕЛЕНЕЦ's user avatar
-4 голоса
1 ответ
92 показа

Выражение должно иметь константное значение C++ (помогите пофиксить ошибку)

Выдает ошибку: "выражение должно иметь константное значение". Как можно пофиксить? #include <iostream> #include <queue> #include <stack> #include <vector> struct { ...
Include91023123's user avatar
0 голосов
1 ответ
214 показов

Перебор всех возможных вариантов на основании ответов

Нужно посчитать общее количество комбинаций и посторить все возможные последовательности ответов на основании массива вопросов и ответов к ниму. по сути вывести все возможные варианты вопрос->ответ ...
Arbejdsglæde's user avatar
2 голоса
0 ответов
1k показов

Как найти минимальное количество ребер, которое нужно добавить, чтобы граф стал эйлеровым путем или циклом?

Есть некоторые графы, например как на скриншоте. Как узнать, сколько раз (если их рисовать карандашом) надо оторвать карандаш от бумаги, чтобы нарисовать граф. Граф задается по одной компоненте ...
fgrd4035's user avatar
0 голосов
1 ответ
64 показа

Матрица смежности: list index out of range

Это граф: Это рёбра, которые я должен был ввести, но программа вывела ошибку: 0 1 1 2 2 3 3 4 4 5 5 6 5 18 6 7 6 19 7 10 7 9 8 19 8 16 9 14 9 16 10 11 11 12 11 13 12 20 13 14 14 17 14 15 15 16 16 19 ...
user avatar
1 голос
1 ответ
54 показа

Подсчет суммы длин между пунктами на графе

сделал программу, которая считает количество путей на графе из точки 1 в точку N через точку M. Попробовал изменить ее чтобы вместо количества путей считалось расстояние, но у меня не вышло. ...
expriced's user avatar
0 голосов
0 ответов
234 показа

Найти цикл в неориентированном графе

Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — ...
Kerian's user avatar
  • 21
-1 голос
1 ответ
96 показов

Вывести номер компоненты связности, к которой принадлежит вершина

Программа не проходит тесты... В первой строчке выходного файла выведите количество компонент связности. Далее выведите N целых чисел, i -е из них задаёт номер компоненты связности для i -й вершины. ...
Kerian's user avatar
  • 21
0 голосов
0 ответов
1k показов

Как построить компоненту связности,содержащую первую вершину для неориентированного графа C#

Дан неориентированный граф, возможно, с петлями и кратными ребрами. Необходимо построить компоненту связности, содержащую первую вершину. Формат ввода следующий: В первой строке записаны два целых ...
Leonid Ten's user avatar
1 голос
1 ответ
133 показа

Как оптимизировать программу по памяти?

Решаю задачу для контеста Яндекса, вылетает на одном тесте, пишет Memory Limited. Пытался делать решение через списки, но так получается что программа тратит еще больше памяти. conf_num = int(input())...
sergei's user avatar
  • 13
0 голосов
1 ответ
97 показов

Реализую алгоритм Дейкстры для такого графа. Ответ должен быть 8, у меня 9. Не пойму в чём ошибка

graph = {} graph['s'] = {} graph['s']['A'] = 5; graph['s']['B'] = 2 graph['A'] = {} graph['A']['C'] = 4; graph['A']['D'] = 2 graph['B'] = {} graph['B']['A'] = 8; graph['B']['D'] = 7 graph['C'] =...
pro100noob's user avatar

1
2 3 4 5
9