Структурный анализ ориентированных графов. - Помощь студентам

Zo0M · 02.11.2009, 13:57

В общем преподаватель подкинул задачку, я уже 3-ий день к ней никак подобраться не могу. Код ни в коем случае не нужен. Нужны ссылки / советы.
Он сказал что это по теме "Структурный анализ ориентированных графов". Яндекс таких слов не знает.

Дан ориентированный граф. 5 точек соединённых произвольно. Точки пронумерованы.
Пример:

Задаются начальное и конечное значение.
По которым программа должна вывести все пути, по которым можно проследовать от начальной точки до конечной. К примеру:
Входное значение - 1
Выходное - 5

Должно вывести:

1-2-5
1-2-3-5
1-4-5
1-2-4-5

Граф задаётся массивом вида:

1-есть связь
0(пусто)- нет связи

Мне в голову всё лезут бинарные деревья, но как прикрутить их сюда - ума не приложу.

Если нет вариантов - Скиньте задачки с решениями на графы.
Поиск таковых для Паскаля успехом не увенчался.

---Добавлено-------

По одному пути можно проходить лишь один раз.

В пути можно использовать каждую вершину только один раз.

Alex2009 · 02.11.2009, 15:24

http://www.google.com.ua/search?q=%D...client=firefox

Gonzo · 02.11.2009, 15:25

А Google знает? Смотри в Wiki по графам, там всё есть

Zo0M · 02.11.2009, 16:13

Цитата:

Сообщение от Alex2009

http://www.google.com.ua/search?q=%D...client=firefox

Там первая ссылка - мой пост, а вторая про частично ориентированные. Дальше - ерунда в стиле "СТРУКТУРНЫЙ АНАЛИЗ ДЕМОГРАФИЧЕСКОГО КРИЗИСА В ЛАТВИИ"

Цитата:

Сообщение от Gonzo

А Google знает? Смотри в Wiki по графам, там всё есть

Вика ничего толкового не сказала. Просто сказала, какие графы есть, чем они отличаются и всё. Интересуют именно алгоритмы работы с ними.

quit · 02.11.2009, 16:22

Дискретная математика вам в помощь

там очень хорошо рассматривается работа с графами и разными алгоритмами их обхода и подсчета.

Levsha100 · 02.11.2009, 16:27

Начните с алгоритма Дейкстры, а дальше уже раскручивайте сами.

LeBron · 02.11.2009, 16:49

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

Levsha100 · 02.11.2009, 16:55

А вообще ответов безчисленное множество, ибо можно некоторый участок пути проходить произвольное количество раз.

LeBron · 02.11.2009, 17:05

Ну тогда сначала проверка на цикличность, если ацикличен - решать, иначе - не решать и выводить сообщение. Хотя циклы могут быть и вне допустимого пути,но это уже такое. Хотя и влияние циклов можно проверить - тем же БФС. А еще, как вариант, можно проверять на цикличность в процесе БФС. Если граф ациклический, то мы никогда не попадем в вершину, в которой уже были.

Zo0M · 03.11.2009, 13:28

Кажется нашёл достаточно нубское решение. Но преподаватель сказал:
хоть как-нибудь, так что попробую реализовать.

Идея:

Максимальное количество путей содержит граф вида:

т.к у него соединены все вершины во всех направлениях.

Для него максимальное число путей из одной точки в другую - 16

1-2-3-4-5
1-2-4-3-5
1-3-2-4-5
1-3-4-2-5
1-4-2-3-5
1-4-3-2-5

1-2-3-5
1-2-4-5
1-3-2-5
1-3-4-5
1-4-2-5
1-4-3-5

1-2-5
1-3-5
1-4-5

1-5

То есть в задаче максимальное число путей - 16

Я хочу построить массив из 16 строк[5] и потом уже обрабатывать их на предмет есть ли связь, удаляя ненужные строки.

Обрабатывать на основе исходной матрицы, думаю будет не сложно, сейчас приступлю.

02.11.2009, 13:57	#1
Zo0M Пользователь Регистрация: 09.07.2009 Сообщений: 42	Структурный анализ ориентированных графов. В общем преподаватель подкинул задачку, я уже 3-ий день к ней никак подобраться не могу. Код ни в коем случае не нужен. Нужны ссылки / советы. Он сказал что это по теме "Структурный анализ ориентированных графов". Яндекс таких слов не знает. Дан ориентированный граф. 5 точек соединённых произвольно. Точки пронумерованы. Пример: Задаются начальное и конечное значение. По которым программа должна вывести все пути, по которым можно проследовать от начальной точки до конечной. К примеру: Входное значение - 1 Выходное - 5 Должно вывести: 1-2-5 1-2-3-5 1-4-5 1-2-4-5 Граф задаётся массивом вида: 1-есть связь 0(пусто)- нет связи Мне в голову всё лезут бинарные деревья, но как прикрутить их сюда - ума не приложу. Если нет вариантов - Скиньте задачки с решениями на графы. Поиск таковых для Паскаля успехом не увенчался. ---Добавлено------- По одному пути можно проходить лишь один раз. В пути можно использовать каждую вершину только один раз. Последний раз редактировалось Zo0M; 03.11.2009 в 13:06.

02.11.2009, 15:24	#2
Alex2009 Proger Man Форумчанин Регистрация: 07.03.2009 Сообщений: 584	http://www.google.com.ua/search?q=%D...client=firefox ShowMessage('Добро пожаловать!');

02.11.2009, 15:25	#3
Gonzo Форумчанин Регистрация: 07.03.2009 Сообщений: 123	А Google знает? Смотри в Wiki по графам, там всё есть Не говорите что мне делать, и я не скажу куда Вам идти. Пишу программы на заказ на Delphi и Pascal Форум разработчиков Pascal и Delphi

02.11.2009, 16:22	#5
quit Я есть! Форумчанин Регистрация: 17.02.2008 Сообщений: 318	Дискретная математика вам в помощь там очень хорошо рассматривается работа с графами и разными алгоритмами их обхода и подсчета. ©Учиться, учиться и еще раз учиться!

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Генератор графов	bondik	Общие вопросы C/C++	6	18.02.2011 17:52
СТРУКТУРНЫЙ ТИП ДАННЫХ "МАССИВ"	Urz-3	Помощь студентам	11	07.06.2009 14:40
С++. Теория графов	curly182	Общие вопросы C/C++	3	28.05.2009 23:14
рисование графов	Pitbull	Общие вопросы Delphi	0	13.12.2008 19:26

02.11.2009, 16:27	#6
Levsha100 Заблокирован Старожил Регистрация: 20.07.2008 Сообщений: 4,032	Начните с алгоритма Дейкстры, а дальше уже раскручивайте сами.

02.11.2009, 16:49	#7
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Дейкстры? Это уже дело вкуса, можно и Дейкстрой. Я бы делал обходом в ширину (проще всего для каждого елемента очереди организировать свой массив путевых указателей, можно сделать через общий список указателей). Делаем полный обход и для каждого попадания в конечную точку выводим путь.

02.11.2009, 16:55	#8
Levsha100 Заблокирован Старожил Регистрация: 20.07.2008 Сообщений: 4,032	А вообще ответов безчисленное множество, ибо можно некоторый участок пути проходить произвольное количество раз.

02.11.2009, 17:05	#9
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Ну тогда сначала проверка на цикличность, если ацикличен - решать, иначе - не решать и выводить сообщение. Хотя циклы могут быть и вне допустимого пути,но это уже такое. Хотя и влияние циклов можно проверить - тем же БФС. А еще, как вариант, можно проверять на цикличность в процесе БФС. Если граф ациклический, то мы никогда не попадем в вершину, в которой уже были.

03.11.2009, 13:28	#10
Zo0M Пользователь Регистрация: 09.07.2009 Сообщений: 42	Кажется нашёл достаточно нубское решение. Но преподаватель сказал: хоть как-нибудь, так что попробую реализовать. Идея: Максимальное количество путей содержит граф вида: т.к у него соединены все вершины во всех направлениях. Для него максимальное число путей из одной точки в другую - 16 1-2-3-4-5 1-2-4-3-5 1-3-2-4-5 1-3-4-2-5 1-4-2-3-5 1-4-3-2-5 1-2-3-5 1-2-4-5 1-3-2-5 1-3-4-5 1-4-2-5 1-4-3-5 1-2-5 1-3-5 1-4-5 1-5 То есть в задаче максимальное число путей - 16 Я хочу построить массив из 16 строк[5] и потом уже обрабатывать их на предмет есть ли связь, удаляя ненужные строки. Обрабатывать на основе исходной матрицы, думаю будет не сложно, сейчас приступлю.