С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Kill100
406 / 272 / 37
Регистрация: 11.12.2010
Сообщений: 1,157
Завершенные тесты: 1
#1

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

16.04.2011, 00:06. Просмотров 906. Ответов 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");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2011, 00:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Компоненты связанности графа (C++):

[C++] Компоненты связанности :( - C++
Помогите решть:(( уже 4 день мучаюсь :(( Дано: n- количество вершин графа. Ag матрица смежности n*n Найти матрицу сильной...

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

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

Дан ориентированный граф. Найти все сильно связные компоненты графа - C++
Есть вот такой код, очень прошу исправить под задание в теме поста Спасибо заранее! #include &lt;iostream&gt; #include &lt;vector&gt; ...

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Упорядочить компоненты вектора так, чтобы сначала размещались все отрицательные компоненты, а затем положительные - C++
заранее спасибо! кто поможет мне с задачей Дан вектор Х(а1,а2...аn)(n=100) упорядочить компоненты вектора так, чтобы сначала размещались...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.04.2011, 00:06
Привет! Вот еще темы с ответами:

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

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

Конденсация графа - C++
Найти число компонент сильной связности, вот может быть кто-нибудь реализовывал нечто подобное?

построение графа - C++
Задача: &quot;Задан граф дерево с корневой вершиной. Нужно, начиная с корневой вершины, обойти все концевые вершины (концевая вершина имеет...


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

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

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