|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
12.04.2011, 19:14 | #1 |
Пользователь
Регистрация: 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 |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Объединение 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 |