Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 20.08.2008, 23:38
гость

 
Сообщений: n/a

реализация графа на с++
Я конечно посмотрела алгоритмы графов, но как выглядит реализация не доходит. Можете написать(с++). Например нам дан неориентированный граф требуется найти длину минимального пути между двумя вершинами(путь существует)
т.е.
Сначала записано число N - количество вершин в графе (1 < = N < = 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем записаны номера двух вершин - начальной и конечной. И выводится одно число - длина пути (количество ребер, которые нужно пройти).

Пример:


5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5


ответ:
3
  #2  
Старый 21.08.2008, 08:55
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Граф невзвешенный, так что можно использовать поиск в ширину или волновой алгоритм. И то, и другое нетрудно реализовать на матрице смежности - например, для обхода в ширину из третьей вершины ищем единицы в третьей строке, рекурсивно выполняем обход для соотв. строк матрицы.
А если из матрицы получить списки смежности, то будет еще проще.
  #3  
Старый 22.08.2008, 10:43
гость

 
Сообщений: n/a

хочу код!!!
  #4  
Старый 22.08.2008, 13:38
Аватар для Schemer
Пользователь

Отправить личное сообщение для Schemer Посмотреть профиль Найти все сообщения от Schemer
 
Регистрация: 26.07.2008
Адрес: Moscow
Сообщений: 93

Сообщение от гость Посмотреть сообщение
хочу код!!!
Ну и в чем проблема?
http://google.ru/search?q=поиск+в+ширину+c%2B%2B
http://google.com/search?q=breadth+f...+c%2B%2B&hl=en

Вот например даже в вики какой-то код есть
http://en.wikipedia.org/wiki/Breadth-first_search
  #5  
Старый 24.12.2009, 19:54
гость

 
Сообщений: n/a

почему никто не может нормально ответить на заданный вопрос... ?! попросили же - код написать ... а вы тут ссылки какие то даете ... и то там я ничего не нашла вообще
  #6  
Старый 24.12.2009, 20:24
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
попросили же - код написать
код давно написать. искать надо лучше.

http://www.google.com/codesearch?q=b...nG=Search+Code
  #7  
Старый 24.12.2009, 20:24
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
код давно написать
*написан
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
реализация алгоритма хаффмана на Php и си Саня Реализация, исходники, языки 5 19.05.2010 14:03
Реализация ввода Олег Павлыш Реализация, исходники, языки 13 17.03.2008 23:16
реализация алгоритма ахо-корасик Straight Сортировка и поиск 0 28.04.2007 09:32
реализация B++ на сайте Dok Реализация, исходники, языки 0 30.11.2006 14:36