Вопросы с меткой [графы]
Граф - совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).
416 вопросов
-1
голос
1
ответ
62
показа
Списки смежности в джава
При решении задач на графы используются списки смежности.
В C++ список смежности находится в массиве векторов:
vector<int> adj[n];
и заполняется этот массив векторов так:
adj[1].push_back(2);
...
1
голос
1
ответ
130
показов
Задача по графам (BFS)
Подскажите, пожалуйста, как решить вот такую задачку на графы:
Условия:
Дан массив из целых чисел (-100 000 000 ≤ arr[i] ≤ 100 000 000).
Можно перемещаться по массиву вперед и назад на один шаг (i - ...
-2
голоса
1
ответ
399
показов
Задача по графам
Условия:
Дан массив из целых чисел (-100 000 000 ≤ arr[i] ≤ 100 000 000).
Можно перемещаться по массиву вперед и назад на один шаг (i - 1 или i + 1).
Также можно перемещаться по массиву по ...
1
голос
2
ответа
843
показа
Задача о перемещении между островами
Отдыхая в деревне, Пётр мысленно вернулся в детство и вспомнил одну из своих любимых компьютерных игр. В мире этой игры произошёл катаклизм, разорвавший его на множество островов, летающих в ...
0
голосов
0
ответов
113
показов
Поиск в глубину
Дан неориентированный граф, возможно, с петлями и кратными ребрами. Необходимо построить компоненту связности, содержащую вершину с номером 1.
Петля в графе - это ребро, которое соединяет вершину с ...
1
голос
1
ответ
95
показов
Отображение направленного графа ( networkx)
Всем привет!
Задачка у меня такая:
Есть направленный граф из двух вершин A, B, вершины связаны так:
A->B = 100
B->A = 50
При отрисовке у меня теряется информация о том, что путь из A->B ...
0
голосов
0
ответов
46
показов
Обход графа в Neo4j с использованием свойств узлов и связей
Есть ориентированный граф, состоящий из узлов с метками Node и связями HAS_CHILD. Связи могут иметь свойство deleted_at. Есть задача обойти этот граф и сделать определенные действия с каждым узлом (...
-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, ...
-1
голос
1
ответ
34
показа
С++ DFS, Memory limit [закрыт]
мой код решает задачу:
Почему передача массивов по ссылке в DFS вызывает Memory Limit, а их объявление глобально проходит все тесты?
Решение с ошибкой:
#include <bits/stdc++.h>
using namespace ...
0
голосов
1
ответ
88
показов
Гамильтонов цикл в неориентированном графе и генератор неориентированных графов
Задание :Гамильтонов цикл в графе G = (V, E) – это цикл в графе G, содержащий все вершины из V. Найти гамильтонов цикл в заданном неориентированном графе. Исследовать асимптотическую временную ...
0
голосов
0
ответов
21
показ
Какой обход должен использоваться в алгоритме Белмана Форда?
обойти граф нужно V-1 кол-во раз но какой обход использовать ? В глубину,в ширину или очередь с приоритетом строить? И нужно ли помечать вершину как пройденная или непройденная?
0
голосов
0
ответов
15
показов
Отображение маршрута на графах
пытаюсь сделать навигацию по круизному лайнеру на реакте. Сама карта будет графом, помещения это вершины, пути это ребра.
Пока что сделал просто демоверсию
Но возник вопрос, как сделать так, чтобы ...
-3
голоса
1
ответ
57
показов
Как найти количество помеченных связных графов? [закрыт]
2
Задача похожа на codeforces 1009D, но только с одним числом в вводе
Можете пожалуйста написать способ нахождения помеченных связных графов когда на вход подается только одно число?(если не ...
2
голоса
1
ответ
192
показа
Компоненты вершинной двусвязности
Дан неориентированный граф без петель в следующем формате:
Первая строка - n m (|V|, |E| соответственно)
Следующие m строк содержат описание ребер: i u_i v_i.
Требуется выделить компоненты вершинной ...
0
голосов
0
ответов
34
показа
максимальный поток в потоковой сети
Решите, является ли следующее утверждение истинным или ложным. Если утверждение истинно, приведите краткое объяснение, а если ложно — приведите контрпример.
Пусть G — произвольная потоковая сеть с ...
3
голоса
2
ответа
192
показа
Найти все простые циклы планарного графа
Возможно, это и XY-проблема, хотя лично мне так не кажется...
Имеется планарный неориентированный граф. По-сути, разбиение некоторого многоугольника на части (это и есть X :)). Задача - найти простые (...
0
голосов
0
ответов
101
показ
Как исправить ошибку. Необходимо находить мосты в графе. Реализация алгоритма
Решаю задачу на поиск мостов в неориентированном графе с возможными кратными ребрами и петлями. Необходимо посчитать и вывести количество мостов а также номера соответсвующих ребер в графе.
При ...
-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;
...
0
голосов
0
ответов
50
показов
Как отобразить граф в виде правильной треугольной решетки в networkx
Нужно отобразить граф в виде такой решетки:
Нужно установить какой-то определенный layout или есть другой способ?
-1
голос
1
ответ
45
показов
питон просит изменить sent.words, т.к. не может найти имя, но всё написано правильно
я разрабатываю граф знаний по текстовым данным. вроде весь код правиильный, но всё равно выдаёт вот такую ошибку
for word in sent.words:
^^^^
NameError: name 'sent' is not defined. Did you mean: 'ent'...
0
голосов
0
ответов
88
показов
Поиск кратчайшего пути из одной вершины графа в другую
Помогите решить задачку на python:
n - количество вершин в графе. n-1 - количество рёбер в графе, соединяющих вершины. Сначала пользователю предлагается ввести количество вершин. После пользователь ...
1
голос
1
ответ
73
показа
Некорректно работает алгоритм Дейкстры
Код должен работать для взвешенного неориентированного графа, состоящего из n вершин и m ребер. Вершины пронумерованы целыми числами от 1 до n. Необходимо найти длину кратчайшего пути из вершины с ...
0
голосов
0
ответов
96
показов
Алгоритм Форда-Беллмана работает некорректно на некоторых тестах. Не могу понять в чём ошибка
уже очень долго сижу и не могу понять, где ошибка в моей реализации алгоритма Беллмана-Форда.
Задан ориентированный граф, в нём не может быть петель и кратных рёбер. Необходимо найти длину кратчайшего ...
0
голосов
0
ответов
56
показов
Алгоритм оптимального обхода графа с условием
Есть граф без отрицательных весов. Нужно из одной вершины в другую найти оптимальный путь и чтобы в цепи обязательно присутствовала вершина по условию. То есть оптимальный путь обязательно проходящий ...
0
голосов
1
ответ
148
показов
Задача о подсчете дорог, код выдаёт неверный ответ
Всем привет, решала следующую задачу:
ограничение по времени 1 секунда ограничение по памяти 256 мегабайт
В Ваканде есть N городов, некоторые из которых соединены дорогами.
Король решил провести ...
0
голосов
0
ответов
54
показа
Удаление циклов из графа в SQL
Предположим, у вас есть таблица рёбер со столбцами A и B, в которых указаны номера вершин, соединенных ребром. Как выбрать из неё ребра так, чтобы в выборке не оказалось ни одного ребра, создающего ...
-2
голоса
1
ответ
392
показа
Задача из яндекс контест по графам. 2 варианта кода, один проходит все тесты другой нет, почему?
Ниже представлены два кода, тот, что на Python мой. На плюсах взял из инета. Алгоритм на плюсах проходит все тесты. Мой не проходит 6 тест (не знаю точно какие входные данные). Помогите разобраться в ...
3
голоса
2
ответа
284
показа
Графы, подсчёт изолированных вершин с помощью матрицы смежности, код выдаёт неверный ответ
решала следующую задачу:
На острове расположены несколько государств, изолированных
друг от друга. У программиста Васи есть данные обо всех дорогах
острова, заданные в виде весовой матрицы ...
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 и ...
-1
голос
2
ответа
443
показа
Графы, обход в глубину. Задача "Построение"
Код прошел не все тесты(, скажите, пожалуйста, в чем ошибка
https://informatics.msk.ru/mod/statements/view.php?id=256&chapterid=166#1 - задача
Группа солдат-новобранцев прибыла в армейскую часть ...
1
голос
1
ответ
932
показа
Графы, компоненты связности, питон
Мой код прошел не все тесты(( а что не так? вот задача https://informatics.msk.ru/mod/statements/view.php?id=256&chapterid=111540#1
Дан неориентированный невзвешенный граф. Необходимо посчитать ...
0
голосов
0
ответов
42
показа
Как графически отобразить все нейроны в виде графа?
Основная проблема заключается в том, что не хватает знаний, как можно графически показать в отдельном окне, желательно с интеграцией в pyQt5, нейроны в виде графа, которые получились в процессе ...
0
голосов
0
ответов
65
показов
Удаление ребра в графе и поиск пути
У меня есть неориентированный граф состоящий из n вершин и n ребёр. Мне нужно быстро отвечать на запрос, существует ли путь из точки А в точку В, если я удалю определённое ребро из точки А.
Сначала я ...
0
голосов
1
ответ
694
показа
Графы. зашла в тупик, почти решив задачу
решала такую задачу на графы:
В стране 77 городов, некоторые из которых соединены дорогами. При этом из любого города до любого существует путь, в котором ни один город не повторяется, а количество ...
3
голоса
1
ответ
578
показов
доказательство утверждения по эйлеровым циклам
недавно столкнулась с интересным утверждением:
а) если в связном графе все вершины четны, то внем существует эйлеров цикл
б) если в связном графе не более двух вершин с нечетными степенями, то в нем ...
0
голосов
0
ответов
42
показа
Направление стрелок в графе
Разве здесь стрелки не должны идти в обратном направлении? Мы же сначала просыпаемся, потом чистим зубы, а после завтракаем. На рисунке кажется, будто мы сначала завтракаем, потом чистим зубы, а после ...
1
голос
2
ответа
119
показов
Как по матрице смежности нескольких графов найти множество отдлеьных графов?
Пусть граф задаётся как множество вершин = (в1,в2 ...) и есть матрица смежности для подобного набора графов:
В данном случае она будет выглядеть так :
Как по матрице смежности понять, что граф (в1,...
-3
голоса
2
ответа
169
показов
Задача о кратчайшем пути [закрыт]
Классическая задача, помогите найти подходы к ней
Имеется N населенных пунктов , пронумерованных от 1 до N. Некоторые пары пунктов соединены дорогами. вывести самый короткий путь из L-го пункта в M-й....
1
голос
1
ответ
590
показов
Как сделать циклом Функциональный граф?
Добрый день!
Помогите пожалуйста или дайте подсказку. Решаю задачу. Условие следующее:
В школе перед Новым Годом устраивают игру в Тайного Санту. Каждому ученику i выдается ученик
ai, которому он ...
-1
голос
1
ответ
749
показов
Теория графов. Поиск циклов длины 3 и 4
Задан граф матрицей смежности. Необходимо найти циклы длины 3 и 4.
Матрица смежности возводится в степень 3 или 4... дальнейший алгоритм мне известен.
Однако препод в универе задаёт один вопрос: ...
-4
голоса
1
ответ
92
показа
Выражение должно иметь константное значение C++ (помогите пофиксить ошибку)
Выдает ошибку: "выражение должно иметь константное значение". Как можно пофиксить?
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
struct {
...
0
голосов
1
ответ
214
показов
Перебор всех возможных вариантов на основании ответов
Нужно посчитать общее количество комбинаций и посторить все возможные последовательности ответов на основании массива вопросов и ответов к ниму.
по сути вывести все возможные варианты вопрос->ответ ...
2
голоса
0
ответов
1k
показов
Как найти минимальное количество ребер, которое нужно добавить, чтобы граф стал эйлеровым путем или циклом?
Есть некоторые графы, например как на скриншоте. Как узнать, сколько раз (если их рисовать карандашом) надо оторвать карандаш от бумаги, чтобы нарисовать граф.
Граф задается по одной компоненте ...
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
...
1
голос
1
ответ
54
показа
Подсчет суммы длин между пунктами на графе
сделал программу, которая считает количество путей на графе из точки 1 в точку N через точку M. Попробовал изменить ее чтобы вместо количества путей считалось расстояние, но у меня не вышло. ...
0
голосов
0
ответов
234
показа
Найти цикл в неориентированном графе
Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — ...
-1
голос
1
ответ
96
показов
Вывести номер компоненты связности, к которой принадлежит вершина
Программа не проходит тесты...
В первой строчке выходного файла выведите количество компонент связности. Далее выведите
N
целых чисел,
i
-е из них задаёт номер компоненты связности для
i
-й вершины. ...
0
голосов
0
ответов
1k
показов
Как построить компоненту связности,содержащую первую вершину для неориентированного графа C#
Дан неориентированный граф, возможно, с петлями и кратными ребрами. Необходимо построить компоненту связности, содержащую первую вершину.
Формат ввода следующий:
В первой строке записаны два целых ...
1
голос
1
ответ
133
показа
Как оптимизировать программу по памяти?
Решаю задачу для контеста Яндекса, вылетает на одном тесте, пишет Memory Limited. Пытался делать решение через списки, но так получается что программа тратит еще больше памяти.
conf_num = int(input())...
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'] =...