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

Компоненты связанности графа - C++

Восстановить пароль Регистрация
 
Kill100
 Аватар для Kill100
359 / 248 / 33
Регистрация: 11.12.2010
Сообщений: 1,068
Завершенные тесты: 1
16.04.2011, 00:06     Компоненты связанности графа #1
[C++] Компоненты связанности графа
Необходимо найти матрицу сильной связанности.
Количество компонент связанности и вывести их на экран..
Половину сделал а вот со второй проблемы (
Не как не могу понять как искать сами компоненты и как их выводить..
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<conio.h> 
#include<iostream.h> 
#include <windows.h>
#include<iomanip.h>
//еще 1 попытка реализовать русский текст в консольке        
char NEWT[256];
char*RUS(char*TEXT) {
CharToOem(TEXT,NEWT);
return NEWT;}
 
int n; 
//Печать матрици 
void print(int**a){ 
      for (int i=0; i<n; i++) 
      { 
          for (int j=0; j<n; j++) 
          cout<<a[i][j]<<" "; 
          cout<<"\n";}; 
} 
//Ввод матриц клавы 
int** enter(){ 
 
int **a=new int*[n]; 
     for (int i=0; i<n;i++){ 
      a[i]=new int [n];}; 
 
for (int i=0; i<n; i++) 
      { 
          for (int j=0; j<n; j++) 
         cin>>a[i][j]; 
        } ; 
return a; 
} 
 
 
//умножение матрицы на матрицу по матричному правилу
int** ymnoz(int **a,int**b){ 
 
int **c=new int*[n]; 
     for (int i=0; i<n;i++){ 
      c[i]=new int [n];}; 
 for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
     c[i][j]=0 
     ;};} 
for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
        for (int k=0;k<n;k++){
            c[i][j]+=a[i][k]*b[k][j]
            ;}
         ;}
      ;}; 
      
return c; 
}
 
//функция возведения в степень и сложения
int** pow(int **Ag){
//создаю матрицу C 
int **c=new int*[n]; 
     for (int i=0; i<n;i++){ 
      c[i]=new int [n];}; 
//делаю матрицу единичной для последующего умножения на Ag
 for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
     c[i][j]=0;
     c[i][i]=1
     ;};} 
//Создаю матрицу Z в которой будет хранится E+Ag^1+Ag2+Ag^n
int **z=new int*[n]; 
     for (int i=0; i<n;i++){ 
      z[i]=new int [n];}; 
 for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
     z[i][j]=0;
     z[i][i]=1
     ;};}      
//Выполняю возведение в степень и сложение     
for(int i=0; i<n; i++){
c=ymnoz(Ag,c);
for(int k=0; k<n; k++)
for(int j=0; j<n; j++)
z[k][j]+=c[k][j];
};
return z;
}
 
//Создаём матрицу Tg
int** Matr_Tg (int**K){
int **Tg=new int*[n]; 
     for (int i=0; i<n;i++){ 
      Tg[i]=new int [n];}; 
//если  Ki,j>0 то пишем 1 иначе 0     
for(int i=0; i<n;i++)
for(int j=0; j<n;j++){
if(K[i][j]>0){
              Tg[i][j]=1;
              }else
              {
             Tg[i][j]=0;    
              };};
return Tg;//возвращаю матрицу Tg
}
 
//функция нахождения матрицы сильной связанности 
int** Matr_Sg(int** Tg){
    //Создаю матрицу Sg
int** Sg=new int*[n]; 
     for (int i=0; i<n;i++){ 
      Sg[i]=new int [n];}; 
//поэлементно умножаю Tg на Транспонированную(Конт достижимости)        
for(int i=0; i<n;i++)
for(int j=0; j<n;j++)
{     
Sg[i][j]=Tg[i][j]*Tg[j][i];
    };    
return Sg;//Возвращаю получившуюся матрицу Sg
}
 
 
int main(){ 
cout<<RUS("Введите количество вершин \n"); 
cin>>n; 
cout<<RUS("Введите матрицу Ag \n"); 
int** Ag=enter(); 
//возвожу в степень и складываю 
int** c= pow(Ag);//сумма возведенных в степень матриц будет хранится тут
cout<<RUS("Матрица Tg \n"); 
print(Matr_Tg(c));
cout<<RUS("Матрица Sg - сильной связанности \n"); 
int** Sg=Matr_Sg(Matr_Tg(c));//Матрица Ып сильной связаности
print(Sg);
system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2011, 00:06     Компоненты связанности графа
Посмотрите здесь:

[C++] Компоненты связанности :( C++
C++ Конденсация графа
C++ Упорядочить компоненты вектора так, чтобы сначала размещались все отрицательные компоненты, а затем положительные
Компоненты связности графа поиском в глубину C++
Найти связные компоненты графа C++
Файл: Найдите номер первой положительной компоненты файла и номер последней положительной компоненты файла C++
C++ Построение графа
C++ Подобие графа

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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