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

Транзитивное замыкание неор графа - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 17
28.12.2011, 19:38     Транзитивное замыкание неор графа #1
Имеется задача : построить транзитивное замыкание для неориентир графа(метод Уоршала не предлагать) , помогите с этим делом ,хотя бы алгоритм.Вообще как мне сказал препод ,можно использовать поиск в глубину, но я не могу понять как .
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2011, 08:53     Транзитивное замыкание неор графа #2
MaX47, какие-нибудь наработки есть?
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 17
29.12.2011, 10:00  [ТС]     Транзитивное замыкание неор графа #3
Вот что успел сделать,но прога зависает, причем непонятно где.и еще ответ желателен в виде матрицы достижимости
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <conio.h>
#define __SIZE 5
#include <stdlib.h>
 
 
int Graf[__SIZE][__SIZE];
int size = __SIZE;
int FIFO[__SIZE];
int Label[__SIZE];
 
 
 
void rndMX( void ) {
      int i,j;
    for(  i=0; i<size; i++ )
    {   for(  j=0; j<size; j++ )
            Graf[i][j] = rand()%2 ? !!rand()%10 : 0;
 
    }
 
    for( i=0;i<size;i++)
       {      Graf[i][i]=0;    }
 
    for( i=0;i<size;i++)
      for( j=0;j<size;j++)
     if(Graf[i][j]==1){
            Graf[i][j]=Graf[j][i];}
 
}
 void printMX( void ) {
    for( int i=0; i<size; i++ ) {
        for( int j=0; j<size; j++ )
            printf( " %2d", Graf[i][j] );
        printf( "\n" );
    }
}
void  main()
{
   randomize();
   int Start=0,i,j,k,p=0,m;
   rndMX( );
   for(i=0;i<(size);i++)
    {
     FIFO[i]=0;
     Label[i]=0;
    }
     printMX( );
    FIFO[0]=Start;     // Заносим в стек стартовую вершину
    Label[Start]=1;    // Присваиваем стартовой вершине метку 1
     k=1;
     m=1;
      
   while (k!=0)
  {
    
/*Находим вершину с минимальным номером, смежную с
вершиной, номер которой находится в стеке в позиции к*/
    for (i=0; i<size; i++)
     if (Graf[FIFO[k-1]][i]==1)
     {
       p=1; 
       break; 
     }      
     if (p!=0)
     {
      if (Label[i]==0) 
      {
        FIFO[k]=i;     // Заносим вершину в стек 
          m++; // Увеличиваем значение метки
         Label[i]=m;    // Помечает вершину          
         Graf[FIFO[k-1]][i]=2;
         Graf[i][FIFO[k-1]]=2;// Помечаетмребро как прямее
          k++; // Сдвигаем позицию вершины стека
                                                //на единицу вверх
      }    
      
      else 
      {
         // Помечаем ребро как обратное
       Graf[i][FIFO[k-1]]=3;
       Graf[FIFO[k-1]][i]=3;
      }
     }  
    
    else k--; // Сдвигаем позицию вершины стека на единицу вниз, тем самым удаляя  вершину из стека
   
  }
   
// Выводим результат
    
    printMX( );
  
   
   getch();
 }
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2011, 10:21     Транзитивное замыкание неор графа #4
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <conio.h>
#define __SIZE 5
#include <stdlib.h>
 
 
int Graf[__SIZE][__SIZE];
int size = __SIZE;
int FIFO[__SIZE];
int Label[__SIZE];
int LL[__SIZE][__SIZE];//матрица транзитивного замыкания графа
 
 
void rndMX( void ) {
      int i,j;
        for(  i=0; i<size-1; i++ )
        {       for(  j=i+1; j<size; j++ )
                        Graf[i][j] = Graf[j][i]= rand()%2;
                Graf[i][i]=0;
 
        }
        Graf[size-1][size-1]=0;
}
 void printMX( void ) {
        for( int i=0; i<size; i++ ) {
                for( int j=0; j<size; j++ )
                        printf( " %2d", Graf[i][j] );
                printf( "\n" );
        }
}
void  main()
{
   randomize();
   int Start, End,i,j,;
   rndMX( );
   printMX( );
   for(i=0; i<size; i++)
   {
       for(j=0; j<size; j++)
           Label[j]=0;
       Label[i]=1;
       Start=0; End=1; FIFO[0]=i;
       while(Start<End)
       {
           for(j=0; j<size; j++)
               if(Graf[FIFO[Start]][j]==1 && Label[j]==0)
               {
                   Label[j]=1;
                   FIFO[End++]=j;
               }
            Start++;
       }
       for(j=0; j<size; j++)
           LL[i][j]=Label[j];
   }    
   // а вот здесь вместо вывода на экран Graf[__SIZE][__SIZE] нужно вывести LL[__SIZE][__SIZE] - матрицу транзитивного замыкания графа
  
   
   getch();
 }
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 10:33     Транзитивное замыкание неор графа #5

Не по теме:

простите что вмешиваюсь. тема интересна.


Цитата Сообщение от valeriikozlov Посмотреть сообщение
int Start, End,i,j,;
эта строчка (№34)разве корректна ?
Цитата Сообщение от valeriikozlov Посмотреть сообщение
randomize();
не подскажите функция из какой библиотеки?

Добавлено через 4 минуты
да и еще хотел спрасить какой смысл делать так

C++
1
2
3
#define __SIZE 5
.....
int size = __SIZE;
я не увидел по коду чтобы значение size где-нибудь менялось
почему бы тогда везде не использовать __SIZE
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.12.2011, 10:36     Транзитивное замыкание неор графа #6
Цитата Сообщение от greeezz Посмотреть сообщение
эта строчка (№34)разве корректна ?
да здесь запятую нужно убрать.

Цитата Сообщение от greeezz Посмотреть сообщение
randomize();
вопрос к автору темы


Цитата Сообщение от greeezz Посмотреть сообщение
#define __SIZE 5
.....
int size = __SIZE;
вопрос к автору темы
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 17
29.12.2011, 11:06  [ТС]     Транзитивное замыкание неор графа #7
По поводу __SIZE действительно глупость.



Спасибо большое,заработало

Добавлено через 8 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сообщение от greeezz
randomize();
вопрос к автору темы
из STDLIB если не ошибаюсь
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 11:11     Транзитивное замыкание неор графа #8
Цитата Сообщение от MaX47 Посмотреть сообщение
из STDLIB если не ошибаюсь
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2011, 17:05     Транзитивное замыкание неор графа
Еще ссылки по теме:

C++ Конденсация графа
C++ Насколько корректно будет работать замыкание?
Объяснить термин "замыкание" и код C++

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

Или воспользуйтесь поиском по форуму:
MaX47
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 17
29.12.2011, 17:05  [ТС]     Транзитивное замыкание неор графа #9
Цитата Сообщение от greeezz Посмотреть сообщение
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете
В нем ,В нем родимиом!
Yandex
Объявления
29.12.2011, 17:05     Транзитивное замыкание неор графа
Ответ Создать тему
Опции темы

Текущее время: 12:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru