Помогите разобраться с графами!

← →
Terb (2006-10-08 14:29) [0]

Вот читаю, читаю и ничерта не понятно!
Что значит поиск в ширину, поиск в глубину. Что эти поиски ИЩУТ??
Например, алгоритм Дейкстры ищет путь с наименьшив весом. А что ещет поиск в ширину?

← →
Kolan © (2006-10-08 14:42) [1]

Читай еще...

> Что эти поиски ИЩУТ??

Обычно ищут узлы, или путь от одного узла к другому.

← →
Terb (2006-10-08 14:42) [2]

Да блин... ну че вы! Ну помогите, пожалуйста!

← →
DprYg © (2006-10-08 14:49) [3]

Что ты хочешь, то и будут искать. А сами эти поиски просто просматривают все вершины графа в разном порядке. Если нужно именно найти что-то - ставь условие при просмотре.

← →
iZEN © (2006-10-08 15:37) [4]

Процентов 80 людей до конца жизни физически не могут понять, что такое указатели и/или адресная арифметика.
Их мозг устроен по-другому.

← →
TUser © (2006-10-08 15:52) [5]

Замени слово "поиск" на "обход графа". Тогда не важно будет что они ищут. Просто есть такие способы перечисления вершин графа.

← →
Проггер из библиотеки (2006-10-08 15:54) [6]

Удобно для поиска кратчайшего пути среди дорог, заданных графами, и т.п. Лично мне за всёвремя, которое я отдал программированию (с 3-го по 10-й класс), ни разу не понадобилось...

← →
Ученик чародея © (2006-10-08 16:19) [7]

Курс: Дискретная математика
http://www.nkzu.edu/NKZU/FIT/mat/discretmath/kursDM.htm

← →
@!!ex © (2006-10-08 18:58) [8]

Графы - руллез форева!
В ВуЗе мы до них еще не добрались(вроде), но в программровании последнее время очень нужны, очень просты и очень полезны.

← →
Vendict © (2006-10-08 19:14) [9]

простым языком, допустим есть у нас граф (на каждой строчке, какая вершина с какой связана):
1) 2,3,6 2) 1,4 3) 1 4) 2,5,7 5) 4 6) 1 7) 4
поиск в ширину обойдёт вершины так:
1,2,3,6,4,5,7
а в глубину так:
1,2,4,5,4,7,4,2,1,3,1,6
добавив вершины в список в таком порядке:
1,2,4,5,7,3,6
т.е. поиск в ширину сначала добавляет в список все непросмотренные смежные с текущей вершины, потом начинает обход с первой не просмотреной.
А поиск в глубину добавляет в список первую попавшуюся вершину и переходит на неё, и начинает сначала (опять добавляет первую смежную непросмотреную вершину и запускается с неё), в случае когда добавить нечего, возвращается назад и добавляет следующую.
И ещё доказано, что поиск в глубину обойдёт весь компонент связности, в котором будет запущен.

Я сам в графах не силен, только взялся за них.. Но вроде-бы обходом в глубину можно определить связность графа и количество его связных компонент. А обход в ширину, наверное находит количество вершин между двумя вершинами (это наверное типа волнового алгоритма) - если в задаче требуется найти кратчайший путь в лабиринте или там в игре "Lines".

Кстати, есть ещё такая книга "Методы алгоритмизации" (В.М. Котов), там тоже про них можно почитать, но у нас в городе они - редкость...

Kair+ © (08.10.06 20:42) [10]
>>Но вроде-бы обходом в глубину можно определить
>>связность графа и количество его связных компонент.
да, если запускать его из разных вершин.
>>наверное типа волнового алгоритма
не "типа" а именно он и есть.

> iZEN © (08.10.06 15:37) [4]
>
> Процентов 80 людей до конца жизни физически не могут понять,
> что такое указатели и/или адресная арифметика.
> Их мозг устроен по-другому.
>

Я очень боялся, что никогда этого не пойму. Честно-честно...

Помогите разобраться с графами! Найти похожие ветки