-4 / 24 / 7
Регистрация: 16.12.2016
Сообщений: 716
1

Пару слов о графах (DFS)

25.11.2018, 19:05. Показов 1988. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
во всех примерах что я видел пока, оперируют такой фразой как - КОЛИЧЕСТВО ВЕРШИН ГРАФА! например при инициализации массива used уже надо знать сколько будет вершин:
C++
1
2
3
4
5
6
void dfs (int v){
used[v]=1;
 for (auto i=g[v].begin();i!=g[v].end();++i)
if(!used[*i])
dfs(*i);
}
Вот есть у меня заданный списком смежности ориентированный граф:
1:0,2,3
2:0,1,4
3:1,4
4:2,3,5
5:4,6
6:5
как посчитать ДО ОБХОДА DFS количество вершин? Строк у меня шесть, да, но у меня еще есть седьмая вершина 0 в которую есть дуги, но из которой нет!
и таких вершин может быть не одна, есть мысли как это решить? или может я упускаю что то фундаментальное из теории??
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.11.2018, 19:05
Ответы с готовыми решениями:

BFS и DFS в графах
Не могу понять почему при обходе графа в ширину (void bfs или void bfs1) выдает пустые результаты...

В массиве слов найти пару слов, из которых одно является обращением другого
Дали задачку, вроде простая, а мыслей нет(( вопрос как организовать поиск слов)) ну собственно...

В последовательности слов найти и поменять местами пару слов, у которых первые 3 буквы одного совпадают с последними 3 буквами другого
Лабораторная работа № 6 Строки Цель работы: изучение правил описания, ввода-вывода и основных...

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

5
165 / 108 / 57
Регистрация: 30.08.2018
Сообщений: 357
25.11.2018, 19:26 2
Лучший ответ Сообщение было отмечено SadiQ228 как решение

Решение

Может не понял вашей проблемы.

Нужно добавить седьмую вершину в список смежности.
Допустим такая задача: вершины населенные пункты, дороги -- ребра.
Пункт A
(A):0,2,3
Дороги перекрыли, а населенный пункт остался.
Пункт есть, а список смежных вершин пуст.
(А):

Все вершины должны быть в списке смежноси.
1
-4 / 24 / 7
Регистрация: 16.12.2016
Сообщений: 716
25.11.2018, 19:35  [ТС] 3
хотите сказать что мое представление графа не верно?
и количество вершин это количество строк в txt файле, в котором граф задается списком смежности верно?
интересное замечание спасибо!)
0
165 / 108 / 57
Регистрация: 30.08.2018
Сообщений: 357
25.11.2018, 19:41 4
Цитата Сообщение от SadiQ228 Посмотреть сообщение
хотите сказать что мое представление графа не верно?
Так вашей задачи не знаю
Цитата Сообщение от SadiQ228 Посмотреть сообщение
и количество вершин это количество строк в txt файле, в котором граф задается списком смежности верно?
Какой файл, где файл ? Что в файле ? )
количество вершин это количество строк в txt файле ? Вам лучше знать.
0
-4 / 24 / 7
Регистрация: 16.12.2016
Сообщений: 716
27.11.2018, 00:42  [ТС] 5
чтобы не создавать одинаковые темы спрошу тут
а как выписать интересующие меня ребра?
у меня есть задача выписать прямые(ребра дерева обхода dfs), обратные ребра(от вершины к предку) и поперечные ребра(не связывают предков и потомков).
сам dfs не вызывает вопросов как рекурсивный так и обычный ( через очередь или стэк) а вот с ребрами не могу придумать может кто подскажет?
0
-4 / 24 / 7
Регистрация: 16.12.2016
Сообщений: 716
27.11.2018, 15:25  [ТС] 6
друзъя если с прямыми и обратными ребрами еще можно подумать и прикинуть как работать,
то с поперечными ребрами ( которые не связывают предков и потомков) я просто даже не могу придумать как быть,
может кто то поможет идеей? может есть какие ни будь обходы типо Эйлеровского или вообще алгоритмы под это?
0
27.11.2018, 15:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.11.2018, 15:25
Помогаю со студенческими работами здесь

В заданном предложении найти пару слов, из которых одно является обращением другого
В заданном предложении найти пару слов, из которых одно является обращением другого /* В...

Строки (найти и поменять местами пару слов, у которых первые три буквы одного совпадают с...)
Дана последовательность символов S1, …, SN. Группы символов, разделенные пробелом (одним или...

найти и поменять местами пару слов, у которых первые три буквы одного совпадают с последними тремя буквами другого (дописать)
Задание: В последовательности из 10 пятибуквенных слов найти и поменять местами пару слов, у...

Создайте функцию, которая пару последовательных чисел Фибоначчи преобразует в следующую пару
Создайте функцию, которая пару последовательных чисел Фибоначчи преобразует в следующую пару....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru