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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 31.10.2010, 14:43
Новичок

Отправить личное сообщение для tewi Посмотреть профиль Найти все сообщения от tewi
 
Регистрация: 31.10.2010
Сообщений: 1

Граф
Есть файл в котором записан граф в виде списка смежностей (т.е. у нас есть вершина и смежные с ней ). По данному графу найти кротчайшее расстояние от одной точки до другой , делается это с помощью алгоритма поиск в ширину.Выводом должен быть путь из вершин.

Очень прошу помочь с реализацией на c++ самый простой пример хотя бы...
  #2  
Старый 31.10.2010, 15:28
гость

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

http://google.com/codesearch?hl=en&&...ng%3Ac% 2B%2B
  #3  
Старый 01.11.2010, 00:42
Новичок

Отправить личное сообщение для WieRuindl Посмотреть профиль Найти все сообщения от WieRuindl
 
Регистрация: 12.06.2010
Сообщений: 13

что такое "алгоритм поиск в ширину"?
  #4  
Старый 01.11.2010, 12:53
гость

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

гугли BFS C++

Ребята у меня тоже вопрос но не по сабжу, тему создавать просто не охота:

вот нам задан граф в виде списка ребер
например
3 - количество ребер
//потом идет описание ребер какие вершины оно соединяет
1 2
2 3
3 1

мне нужно каждое ребро представить в виду вершины, а вершины в виде ребер, то есть преобразовать граф, как мне это сделать?

то есть вот например вершина V есть мы ее расщепляем на V1 и V2, получается ребро из нее, а из старых ребер делаем вершины.

Я раньше делал это только сейчас забыл, а в гугле найти не могу, там вроде за куб или и того меньше как то можно сделать. Приведите плз алгоритм.
  #5  
Старый 01.11.2010, 13:49
гость

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

то есть ребра которые даны нужно сжать в вершину а вершины расщепить на ребра

1 2 сжимаем 1 и 2 получаем вершину x
2 3 сжимаем 2 и 3 получаем вершину y
3 1 сжимаем 3 и 1 получаем вершину z
расщепляем 2
получаем что:
x смежно y
y смежно z
z смежно x
  #6  
Старый 01.11.2010, 15:47
гость

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

более точнее будет так:
как построить матрицу смежности вершин (не ребер)
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как красиво нарисовать граф? Selmaril Графы 2 08.10.2010 22:45
Платоновый граф helm Графы 3 25.12.2009 01:02
Граф Эйлеров или Гамильтонов? Таня Графы 1 18.06.2009 18:47
граф в win32 гость Графы 11 08.04.2009 03:07
задача про кубический граф гость Графы 4 22.05.2008 09:42