Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
#1

Проверка графа на возможность достижимости одной вершины из другой - C++

16.11.2010, 18:46. Просмотров 1907. Ответов 7
Метки нет (Все метки)

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

Как решить данную прогу? Я создал матрицу смежности, а вот прогу для проверки не могу((
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2010, 18:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Проверка графа на возможность достижимости одной вершины из другой (C++):

Нахождение кратчайшего пути от одной вершины графа до другой - C++
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include <iostream.h> #include...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А - C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А. Никаких наработок нет, к сожалению, вообще...

Нахождение всех путей в графе от одной вершины до другой обходом в ширину - C++
Здравствуйте, уважаемые любители и профессионалы программирования. Нужна мне помощь в такой задаче. Необходимо найти для любого...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте! Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте.Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной длины от...

Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. - C++
Помоги написать программу по графам плиз Найти все вершины графа, к которым существует путь заданной длины (не обязательно кратчайший)...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.11.2010, 19:23 #2
Я создал матрицу смежности
это как?
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
16.11.2010, 19:56  [ТС] #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void VVOD_MSM(int msm[NMAX][NMAX], int n)
{
 int i,j;
 printf("\nВведите матрицу смежности\n");
 printf("|");
 for(j=0;j<n;j++) printf("%d ",j);
 putchar('\n');
 for(i=0;i<2*n+2;i++) putchar('-');
 for(i=0;i<n;i++)
 {printf("\n%d| ",i);
  for(j=0;j<n;j++) scanf("%d", &msm[i][j]);
 }
 putchar('\n');
}
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.11.2010, 20:07 #4
на матрицу смежности похоже, а входные данные откуда? с клавиатуры или с файла?
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
16.11.2010, 21:16 #5
Цитата Сообщение от Мунир Посмотреть сообщение
Как решить данную прогу?
определить является ли заданый граф минимальным остовным деревом за алгоритмом Прима
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
16.11.2010, 21:25  [ТС] #6
С клавиатуры данные)
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.11.2010, 05:57 #7
Мунир, Я так понимаю что в матрице смежности, которая у нас есть уже отражен случай закрытия одной из дорог и имеются города между которыми нужно проверить связь.
Я бы сделал так:
Создаем массив int размером N (где N кол-во вершин) - будем использовать его в качестве очереди.
Создаем массив bool размером N (Для отметок уже пройденных вершин).
Далее алгоритм следующий:
Берем первую вершину (город от которого ищем путь), отмечаем ее в массив bool, и номер ее заносим в очередь.
Следующее ниже организуется в цикле, например с помощью while():
Затем берем первую вершину из очереди. По матрице смежности смотрим с какими вершинами она связана, если у этих вершин уже есть метки в массиве bool, то пропускаем их, если меток нет, то берем эти вершины, ставим им метки в массиве bool, а номера загоняем в очередь.
Теперь вопрос когда выйти из цикла. Выйти из цикла нужно в двух случаях: когда мы достигнем второй вершины (это легко проверить по массиву bool), или когда очередь опустеет.
Мунир
0 / 0 / 0
Регистрация: 16.11.2010
Сообщений: 4
17.11.2010, 16:38  [ТС] #8
Спасибо за информацию) Буду пытаться написать что-то)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2010, 16:38
Привет! Вот еще темы с ответами:

Удаление вершины графа - C++
Добрый вечер. Нужна помощь в удалении вершины графа. Вот код: struct arc; struct node { int id; ...

Вершины графа выводить буквами - C++
Добрый день Помогите пожалуйста с задачей обхода графа в ширину Есть граф с 6 вершинами от 1 до 6 После обхода результат - met...

Вывод простых циклов, из каждой вершины графа - C++
здравствуйте, помогите переделать код выводящий все простые цепи из каждой вершины графа, в код выводящий все простые циклы из каждой...

Найти степени входа и выхода каждой вершины графа. - C++
Задано множество упорядоченных пар вершин, соответствующих дугам ориентированного графа. Найти степени входа и выхода каждой вершины. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
17.11.2010, 16:38
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru