VPF::алгоритм - Форум программистов

rthsobakas

Дата 8.11.2008, 13:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Awaiting Authorisation
Сообщений: 562
Регистрация: 20.9.2007

Репутация: нет
Всего: -1

есть граф он записывается в виде матрицы смежности

то есть

     x1 x2 x3 x4 x5 x6
x1  0   1   1  0   0  0
x2  1   0   0  0   0  0
x3  1   0   0  0   0  0
x4  0   0   0  0   0  0
x5  0   0   0  0   0  1
x6  0   0   0  0   1  0

тут 2 графа и они не связаны , то есть  x1 ->x2 , x1->x3(первый)

x5->x6 (второй)

Связи вершин 1 2 3 с 5 6 и с 4 нет

ну так вот надо эту матрицу разбить на 3  матрицы(та как 2 графа + 1 x4 ваще одна)

первая
     x1 x2 x3
x1  0   1   1
x2  1   0   0
x3  1   0   0

вторая
        x5 x6
x5    0  1
x6    1  0

третья x4

Как это сделать?
Теоретически я представляю это вот так:
Выбираете строчку х1 и проверяете столбцы если в одном из столбов 1 то проверяете строку с номером это столбца на наличие единиц, если и там нашли то смотрите опять на столбец и и ищете опять строку с номером этого столбца и тд пока не заполните новую матрицу , потом  по индукции шпарите все остальные вершины.

ТОка 3 непонятки :
1) Как практически реализовать алгоритм?
2) Может есть такой алгоритм, как он называется?
3) "Производные" матрицы , сколько их делать не известно заранее, как решить эту проблему?

Это сообщение отредактировал(а) rthsobakas - 8.11.2008, 13:58

nworm

Дата 9.11.2008, 21:40 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

Репутация: 1
Всего: 8

Надо искать алгоритм поиска компонент связности.

см., например, здесь

Dmi3ev

Дата 13.11.2008, 13:31 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 1
Всего: 41

я делал что-то похожее, только мне надо было записать получившиеся матрицы в файл (делал по учебе), у тебя на диске д создадутся файлы после работы этой программы, в которых будут матрицы, получившиеся после отбора:

Код


//---------------------------------------------------------------------------
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
//#pragma hdrstop

//---------------------------------------------------------------------------

//#pragma argsused
//---------------------------------------------------------------------------
int main()
{
char fn[255]="", fn1[255]="";
char ch[10]="";
ofstream file;
int k=1;
int ind=0;
int mgraph[6][6]={
{0,1,1,0,0,0},
{1,0,0,0,0,0},
{1,0,0,0,0,0},
{0,0,0,0,0,0},
{0,0,0,0,0,1},
{0,0,0,0,1,0} };
int km[6]={0,0,0,0,0,0};
km[0]=k;
for (int i=0; i<=5; i++)
 {
 for (int j=0; j<=5; j++)
  {
   if (mgraph[i][j]==1)
    {
     if (km[j]==0)
      {
       if (km[i]==0)
        km[j]=k;
       else
        km[j]=km[i];
      }
    }
   else
    {
     for (int z=0; z<=5; z++)
      {
       if (mgraph[z][j]==1)
        ind=1;
      }
     if (ind==0)
      km[j]=++k;
    }
   ind=0;
  }
  k++;
 }
for (int i=0; i<=5; i++)
 cout<<"//"<<km[i]<<"\\";
int nm=1;
cout<<endl;
for (int i=0; i<=5; i++)
 {
  for (int j=0; j<=5; j++)
   {
    if (km[i]==km[j])
     {
      itoa(km[j],ch,10);
      strcat(fn,"D:\\matrix");
      strcat(fn,ch);
      strcat(fn,".txt");
      for (int l=0; l<=strlen(fn1); l++)
       fn1[l]=NULL;
      strcat(fn1, fn);
      file.open(fn, ios::app);
      file<<mgraph[i][j]<<";";
      cout<<mgraph[i][j]<<";";
      cout<<fn;
      file.close();
     }
     for (int l=0; l<=strlen(fn); l++)
       fn[l]=NULL;
     for (int l=0; l<=strlen(ch); l++)
       ch[l]=NULL;
   }
   file.open(fn1, ios::app);
   if (file)
   {
    file<<endl;
   }
   if(file.is_open())
    file.close();
   cout<<endl<<fn1;
   for (int l=0; l<=strlen(fn1); l++)
    fn1[l]=NULL;
   cout<<endl;
 }
char c;
cin>>c;
        return 0;
}
//---------------------------------------------------------------------------

не судите строго, я тогда вообще почти не умел программировать, но главное что он работает.
не обращай внимания на надписи, которые увидишь. главное, что матрицы лежат в отдельных файлах на диске д, в корне.
при следующем выполнении в файлы будет произведена дозапись, если имена совпадут!!! так что надо дорабатывать.
это было для учебы, так что я особо не старался, главное было сдать, и то препод удивился извращенности моей мысли)))

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »