|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
27.10.2011, 12:49 | #1 |
Пользователь
Регистрация: 01.12.2010
Сообщений: 20
|
Определение центра графа заданной матрице инцидентности
Помогите с кодом программы)
Задание "Определение центра графа заданной матрице инцидентности" |
27.10.2011, 12:56 | #2 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Тупой алгоритм: для каждой вершины, пустить волну по рёбрам и посчитать, когда она заглохнет. Взять вершину, в которой это число минимально.
|
27.10.2011, 13:00 | #3 |
Пользователь
Регистрация: 01.12.2010
Сообщений: 20
|
мне код проги нужен в си)
|
27.10.2011, 13:19 | #4 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Первая подпрограмма: определяет, можно ли из вершины a пройти в вершину b за один шаг.
Вторая подпрограмма: имея два массива значений в вершинах (найденная минимальная длина пути от вершины x до заданной, либо -1, если такая длина ещё не найдена; 1, если до вершины найден минимальный путь, но пути из неё ещё не исследовались и 0 иначе), заменить по меньшей мере одно значение 1 в первом массиве на 0 с сохранением условий и вернуть 1, либо вернуть 0, если найдены пути до всех вершин, либо вернуть -1, если найдены пути не до всех вершин, но во втором массиве все нули. Третья подпрограмма: для заданной вершины, найти максимальную из минимальных длин пути до всех вершин и вернуть её, либо вернуть -1, если хотя бы до одной вершины не получается дойти вообще. Четвёртая подпрограмма (основная программа): перебрать все вершины, держа в уме номер кандидата на центр и максимальное из расстояний до вершин для него. В конце либо сообщить номер найденного кандидата, либо с прискорбием сообщить пользователю, что в графе нет центра. |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Определение центра графа заданной матрице инцидентности | emsisem | Общие вопросы C/C++ | 2 | 27.10.2011 13:09 |
Определение центра графа заданной матрице инцидентности | emsisem | C++ Builder | 0 | 27.10.2011 12:48 |
Графы.Определение смежных вершин по заданной матрице | Solnce90 | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 28.06.2011 21:23 |
по заданной матрице смежности простого графа построить каркас этого графа с использованием поиска вширь | d1m2o3n4 | Помощь студентам | 0 | 22.06.2011 22:43 |
дана матрица( любая). если в заданной матрице количество | xov | Помощь студентам | 6 | 23.05.2011 17:29 |