Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Visual C++/MFC/WTL > Найти число компонент связностей.

Автор: castle29 11.5.2013, 19:11

Пишу в Visual Studio 2010 C++.
Вообще мне надо посчитать количество граней в графе, который задаётся матрицей смежности. Матрицу смежности забиваю в двумерный массив. Нахожу количество рёбер.

Код


private: System::Void button1_Click(System::Object^  sender, System::EventArgs^  e) {
    int N=3,  kv=3, kr=0, kg,ks=0  ;
    int mas[3][3];    
     
    mas[0][0] = Convert::ToInt32(richTextBox2->Text); 
    mas[0][1] = Convert::ToInt32(richTextBox1->Text);
    mas[0][2] = Convert::ToInt32(richTextBox3->Text);
    mas[1][0] = Convert::ToInt32(richTextBox4->Text);
    mas[1][1] = Convert::ToInt32(richTextBox5->Text);
    mas[1][2] = Convert::ToInt32(richTextBox6->Text);
    mas[2][0] = Convert::ToInt32(richTextBox7->Text);
    mas[2][1] = Convert::ToInt32(richTextBox8->Text);
    mas[2][2] = Convert::ToInt32(richTextBox9->Text);

    
//ищем число рёбер
for (int k=1; k<N; k++)
{ for (int l=0; l< k;l++)
{
if (mas[k][l]>0)
kr++;}}      

//ищем число копм. связностей
//.....

//считаем кол-во граней
kg=1+ks-kv+kr;
//выводим
        label1->Text= String::Format("Количество граней:{0}", kg);

         }

Я нашла вот такой код для нахождения компонент связностей

Код


std::vector<std::vector<int> > gr;
std::vector<bool> used;
 
void dfs(int v)
{
    used[v] = true;
    for (int i = 0; i < gr[v].size(); ++i)
    {
         if (!used[gr[v][i]])
             dfs(gr[v][i]);
    }
}

как его переделать под мою программу?
Надо очень срочно!!!!!!!!!К понедельнику!!
Буду очень благодарна!!

Автор: akizelokro 12.5.2013, 06:26

Вместо "gr[v].size" написать "3", потом в теле функции вместо "gr" написать "mas" и удалить первую строчку в рассматриваемом коде?
ну, и, конечно, vector used переписать как массив[3].
или они в vector<bool> побитно рассчитывают число?

Автор: akizelokro 12.5.2013, 07:07

если, конечно, взводом битов в "used", это самое число не подсчитвывают)

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com//object-id518e6ddb6ccc194113000002#findElement_E7045_518f157f6ccc19211b0003f7_0

Автор: castle29 12.5.2013, 23:08

Спасибо, попробую.

Автор: castle29 15.5.2013, 20:03

Ничего не получается=/////
Как это фенкция dfs вообще работает???
Может кто-нибудь подскажет как лучше сделать этот поиск??
Пожалуйста!!!!!!!

Автор: castle29 17.5.2013, 21:25

Всё разобралась.