Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.04.2011, 19:14   #1
Lodyr
Пользователь
 
Регистрация: 15.12.2009
Сообщений: 69
По умолчанию Построение ПВШ-деревьев

Добрый вечер!
Помогите пожалуйста с графами.
Задача такая: Есть связный граф, который задается матрицей смежности. Построить от всех его вершин ПВШ-деревья.
ПВШ - дерево - дерево, полученное исключением поперечных ребер, посредством Поиска В Ширину.
есть процедура

void BFS(graphms& gm, massiv& gm1, massiv& gm2, ofstream& f2)
{
queue<int>q;//ochered
for(int i=0; i<gm1.m*2; i++) //massiv metok na prosmotr vershiny
{gm1.nt[i]=0;}; //zanulaem ego
q.push(0); //poseshenie pervoy vershiny
gm1.nt[0]=1;//pomeshenie kak prosmotrennoy
f2<<"one of the ways:"<<" ";
while(q.size()>0) //poka ne vse vershiny prosmotreny
{
int u=q.front(); //izvlekaem iz ocheredi vershiny
q.pop();
f2<<u+1<<" "; //vivodim ee
for (int i=0; i<gm.n; i++) //cikl po vsem vershinam
if (gm.mt[u][i]==1 && gm1.nt[i]!=1) // esli vershina smegna s dannoy i neprosmotrena
{q.push(i); //pomeshaem v ochered
gm1.nt[i]=1;} //pomeshaem kak prosmotrennyy
}
f2<<endl;
for(int i=0; i<gm2.m*2; i++)
f2<<gm2.nt[i]<<" ";
}

graphms& gm, - матрица смежности графа
massiv& gm1, - массив меток из 0 и 1
massiv& gm2, - массив ребер (для примера из 7 ребер - [1,2,1,5,2,5,2,6,3,4,3,5,4,5]
ofstream& f2 - вывод информации в файл

Для примера
ребра
1 2
1 5
2 5
2 6
3 4
3 5
4 5
вершин - 6
если начинать будем с первой вершины, то в случае прохода процедуры получаем 1 2 5 6 3 4
а выходное дерево состоит из 5 ребер
1 2
1 5
2 6
3 5
4 5
Lodyr вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Объединение 2-х бинарных деревьев в одно qwerty6789 Общие вопросы C/C++ 1 22.02.2011 22:03
Визуализатор деревьев Alekc1989 Помощь студентам 0 03.02.2011 11:02
Ошибка в сравнении деревьев kaizer131 Помощь студентам 4 26.05.2010 13:36
Сравнение деревьев kaizer131 Общие вопросы Delphi 0 22.05.2010 10:00
компонент отображения деревьев IgorKr Компоненты Delphi 3 03.05.2008 09:01