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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Kill100
386 / 252 / 34
Регистрация: 11.12.2010
Сообщений: 1,078
Завершенные тесты: 1
#1

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

16.04.2011, 00:06. Просмотров 882. Ответов 0
Метки нет (Все метки)

[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++
Помогите решть:(( уже 4 день мучаюсь :(( Дано: n- количество вершин графа. Ag матрица смежности n*n Найти матрицу сильной...

Найти связные компоненты графа - C++
Здравствуйте, уже 2 ой день ломаю голову над этой элементарной задачей. Прошу Вас помочь разобраться, Вот мои наработки. Работает не...

Компоненты связности графа поиском в глубину - C++
Доброго времени суток милые форумчане!!! Очень нужна ваша помощь, сама справиться не в силах. Нужно посчитать количестко компонент...

Файл: Найдите номер первой положительной компоненты файла и номер последней положительной компоненты файла - C++
Организуйте заполнение типизированного файла случайными целыми числами из интервала . Выведите содержимое файла на экран. Найдите номер...

Построение графа - C++
Вершины и ребра графа назовем его элементами. По графу G построить граф T(G), у которого в качестве вершин взяты элементы G, а две вершины...

Центр графа - C++
Дана матрица смежности. Найти максимальное расстояние в графе. Пол дня уже мучаюсь, искал в гугле, сам пытался, но ничего не...

Импорт графа из файла - C++
Добрый день! Задача по графам. Вот так реализована функция вывода графа на экран: void Graph::display() { for (int i...

K-связность неориентированного графа - C++
Ребят, третью неделю уже думаю, не могу решить. Нужно написать программу на с++, определяющую k-связность графа. Как я понял с...

Построение графа лица - C++
Всех приветствую. Помогите пожалуйста в следующем деле.Имеется исходная фотография человеческого лица, нужно сравнить его с другой...

поиск центра графа - C++
Здраствуйте. нужен универсальный код поиска центра графа(вершины или двух). рисовать или вставлять граф не нужно.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru