Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Шпоры по МПиПА / Графы / Существование пути между 2 вершинами / C / Исходник / existWay
.cpp#include "iostream.h"
#include "stdio.h"
bool existWay( int **array, int size, int from, int to ) {
bool find = false;
int i, j, k, step = 0;
int **temp1, **temp2;
temp1 = new int*[size];
for ( i = 0; i < size; i ++ ){
temp1[i] = new int[size];
}
temp2 = new int*[size];
for ( i = 0; i < size; i ++ ){
temp2[i] = new int[size];
}
for ( i = 0; i < size; i ++ ){
for ( j = 0; j < size; j ++ ){
temp2[i][j] = array[i][j];
}
}
find = ( temp2[from][to] == 1 );
while ( !find && step < size ){
for ( i = 0; i < size; i ++ ){
for ( j = 0; j < size; j ++ ){
temp1[i][j] = temp2[i][j];
}
}
for ( i = 0; i < size; i ++ ){
for ( j = 0; j < size; j ++ ){
temp2[i][j] = 0;
for ( k = 0; k < size; k ++ ){
temp2[i][j] += temp1[i][k]*array[k][j];
}
}
}
find = ( temp2[from][to] == 1 );
step++;
}
return find;
}
void main() {
int i, j;
int from, to, size;
int **array;
bool answer;
cout << "Exist Way.\nEnter graph dimension: ";
cin >> size;
array = new int*[size];
for ( i = 0; i < size; i++ ) {
array[i] = new int[size];
}
for ( i = 0; i < size; i ++ ){
cout << "Enter " << i + 1 << " row: ";
for ( j = 0; j < size; j ++ ){
cin >> array[i][j];
}
}
cout << "Enter From Node: ";
cin >> from;
cout << "Enter To Node: ";
cin >> to;
answer = existWay( array, size, from - 1, to - 1 );
cout << "\nExist way from " << from << " to " << to << " ?\nAnswer: " << ( answer ? "true" : "false" );
cout << "\nPress \"Enter\" to continue..." << endl;
getchar();
}