1 / 1 / 0
Регистрация: 08.10.2018
Сообщений: 34
|
|
1 | |
Найти вершины графа, находящихся на заданном расстоянии от данной вершины05.12.2018, 21:28. Показов 3895. Ответов 8
Метки нет Все метки)
(
Есть неориентированный граф задан матрицей смежности, нужно найти вершины графа находящихся на заданном расстоянии от данной вершины. Буду благодарен за любую помощь.
0
|
|
05.12.2018, 21:28 | |
Ответы с готовыми решениями:
8
Найти вершины графа, находящихся на заданном расстоянии от данной вершины Обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии от данной вершины Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины |
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
|
05.12.2018, 21:36 | 2 |
Используйте поиск в ширину (BFS).
0
|
1 / 1 / 0
Регистрация: 08.10.2018
Сообщений: 34
|
|
05.12.2018, 22:05 [ТС] | 3 |
valen10, а можете описать реализацию программы в целом
0
|
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
||||||
05.12.2018, 23:00 | 4 | |||||
В целом описывает алгоритм. Рассматриваем соседей вершины, запоминаем расстояние до них, потом рассматриваем соседей для соседей и так далее, пока не рассмотрим все вершины. Могу пример показать. Его правда придется доработать (динамическое выделение памяти, нумерация вершин с 1 а не с 0, еще что-то может быть).
0
|
1 / 1 / 0
Регистрация: 08.10.2018
Сообщений: 34
|
||||||
06.12.2018, 19:00 [ТС] | 5 | |||||
Что можно ещё исправить в коде?
0
|
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
|
|||||||||||
06.12.2018, 19:20 | 6 | ||||||||||
Можно пример, когда не работает?
Добавлено через 4 минуты Полагаю, причина в этом. Номера вершин графа != индексы массива. Добавлено через 10 минут Предлагаю внести следующие изменения.
0
|
1 / 1 / 0
Регистрация: 08.10.2018
Сообщений: 34
|
|
06.12.2018, 19:22 [ТС] | 7 |
valen10, примеры некоторых тестов
0
|
1 / 1 / 0
Регистрация: 08.10.2018
Сообщений: 34
|
|
06.12.2018, 19:25 [ТС] | 9 |
valen10, Благодарю всё работает
![]()
0
|
06.12.2018, 19:25 | |
Помогаю со студенческими работами здесь
9
Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа Найти кратчайшее расстояние из вершины v1 неориентированного взвешенного графа в другие вершины графа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |