VPF::[С++] Поиск мостофф в графе. - Форум программистов

sapphiro

Дата 4.5.2007, 13:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 13.11.2006

Репутация: нет
Всего: нет

ЗДРАСТВУЙТЕ...ПОМОГИТЕ!!!!!П-О-Ж-А-Л-У-Й-С-Т-А.....
таково условие:
Мост в связном неорграфе - это ребро, удаление которого делает граф несвязным. Найти все мосты.
ну я еще токо учусь и много не знаю, но вот что я написал(прочитайте пожалуйста...):

Код


#include <stdio.h>
#include <windows.h>
int n, kol; //n вершин
int MAT[7][7];  //матца смежности
char message[100];  
int Next(int i, int j);
//int Next(int i, int j, int MAT[][], int n){       //i - вершина, в которой находимся в данный момент; j - вершина, в которую собираемся шагнуть
int main() {
FILE *f=fopen("data.txt","rt");
fscanf(f,"%d",&n);
for (int i=0; i<n; i++)                                             
    for(int j = 0; j<n; j++)
    fscanf(f,"%d",&MAT[i][j]);
fclose(f);
CharToOem("Данные прочитаны успешно\n",message);
printf(message);
for (int i = 0; i < n; i++)     //цикл по мат-це
for (int j = 0; j < n; j++){    
    if(MAT[i][j]==1){       //если эл-нт равен 1, значит есть из нее ребро, 
        MAT[i][j]=0;        //удаляем его для проверки не мост ли это!!!!!!!!!!!!!
        MAT[j][i]=0;    
 
        if(Next(0, j) == 0){        //если не достигли вершины(вернули 0)
            CharToOem("\nНайден мост: ",message);               
            printf(message);
            printf("%d - %d\n", i+1,j+1);
        }
        MAT[i][j]=1;
        MAT[j][i]=1;        //восстанавливаем мост чтоб найти остальные!!!!!!!!
    }
}
return 0;       //UNhappy END.
}
int Next(int i, int j){     //собственно сама функция шагания по вершинам графа. вернет 1 - дошли, 0 не дошли
int Sum = 0;    
for(int e = 0; e < n; e++)
    Sum += MAT[j][e];       //если Sum = 0 - эта вершина ни с кем не связана
            
if(Sum == 0) 
    return 0;                       
if(i != j){                         
    for(int k = i+1; k < n; k++){
        if(MAT[k][i]==1){
            kol++;
            if(Next(k, j) == 0){         
                if(kol > (n-1))     
                    return 0;       
            }
 
            else{           
                Next(k+1, j);
                return 1;
            }
        }
    }
}
if (i == j)     
    return 1;       
return 1;   
}

вот. такой вот есть граф: (нарисуйте на бумажке, пожалуйста...)

_ _1 2 3 4 5 6 7
1 | 0 1 0 1 0 0 0 |
2 | 1 0 1 0 0 0 0 |
3 | 0 1 0 1 0 1 0 |
4 | 1 0 1 0 1 0 0 |
5 | 0 0 0 1 0 0 0 |
6 | 0 0 1 0 0 0 1 |
7 | 0 0 0 0 0 1 0 |
(1 - если вершина связана. 0 - нет) 7 вершин.
ну а ответ должен быть по идее: 3-6, 4-5, 5-4, 6-3, 6-7, 7-6
а получается: 4-5, 6-7.
где то я промазал, но не могу понять где... помогите пожалуйста...!!!!!!

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »