0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24
1

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

28.12.2011, 19:38. Показов 8382. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Имеется задача : построить транзитивное замыкание для неориентир графа(метод Уоршала не предлагать) , помогите с этим делом ,хотя бы алгоритм.Вообще как мне сказал препод ,можно использовать поиск в глубину, но я не могу понять как .
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.12.2011, 19:38
Ответы с готовыми решениями:

Транзитивное замыкание
Добрый вечер! Разбираю транзитивное замыкание и насколько я поняла, выполняется перемножение...

Транзитивное замыкание
Нужно написать программу для Транзитивного замыкания. Я не могу сделать чтобы строка умножалась на...

Транзитивное замыкание Уоршелла
Реализовать алгоритм построения транзитивного замыкания Уоршелла и проиллюстрировать по шагам этапы...

Что такое транзитивное замыкание?
Можете привести парочку простых примеров, а то не очень понял что это такое и как применяется.

8
Эксперт С++
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
29.12.2011, 08:53 2
MaX47, какие-нибудь наработки есть?
1
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24
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();
 }
0
Эксперт С++
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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();
 }
0
278 / 173 / 21
Регистрация: 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
0
Эксперт С++
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
29.12.2011, 10:36 6
Цитата Сообщение от greeezz Посмотреть сообщение
эта строчка (№34)разве корректна ?
да здесь запятую нужно убрать.

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


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



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

Добавлено через 8 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Сообщение от greeezz
randomize();
вопрос к автору темы
из STDLIB если не ошибаюсь
0
278 / 173 / 21
Регистрация: 10.07.2011
Сообщений: 441
29.12.2011, 11:11 8
Цитата Сообщение от MaX47 Посмотреть сообщение
из STDLIB если не ошибаюсь
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете ?
0
0 / 0 / 0
Регистрация: 02.01.2011
Сообщений: 24
29.12.2011, 17:05  [ТС] 9
Цитата Сообщение от greeezz Посмотреть сообщение
если б оно у меня там было я бы и не интересовался.. вы случаем не в борланде все это делаете
В нем ,В нем родимиом!
0
29.12.2011, 17:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.12.2011, 17:05
Помогаю со студенческими работами здесь

Как задать транзитивное замыкание?
M=\begin{Bmatrix}1,3,5,7\end{Bmatrix} Отношение R= \begin{Bmatrix}(a,b):b=a+2\end{Bmatrix} Если...

Транзитивное замыкание бинарного отношения
Подскажите пожалуйста как на заданном графе R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) )...

Алгоритмом Уоршелла построить транзитивное замыкание для отношения
Алгоритмом Уоршелла построить транзитивное замыкание для отношения a+b=10, реализация на С++,...

Транзитивное замыкание для бинарного соотношения (тройной цикл...)
Приветствую. Что то не пойму никак, как реализовать данный алгоритм. С программированием в маткаде...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru