Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск мостофф в графе. (С++)

Автор: sapphiro 4.5.2007, 13:23

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

Код


#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.
где то я промазал, но не могу понять где... помогите пожалуйста...!!!!!!

Автор: Promitheus 4.5.2007, 17:44

Слушай, я тут накидал граф, может надо удалить то, что пометил красным крестом. Вообще надо теорию точно вспомнить, что такое связанный граф, что такое сильно связанный, что такое мост , что такое несвязанный граф и тэдэ. Может позже напишу, если мысли будут.

Может надо так:

цикл смотрим какой элемнт связан с более, чем одним элементом. Находим такой удаляем связь, далее цикл сначала и так пока не пройдем весь граф полностью.

Автор: sapphiro 4.5.2007, 18:21

вспомнить теорию: граф связный, если мы можем попасть из любой точки в любую...(по крайне мере я так решил). сильно связный - это вроде односвязный, это если из любой точки в любую(из начальной в конечную, относительно задачи) мы можем попасть только одним путем. про мост написано в первом посте. несвязный граф - это если мы НЕ можем попасть из начальной точки в конечную.

см рисунок - красные кресты - мосты.

Вопрос: под элементом ты видимо понимаешь ребро, я тоже. смысл у меня в том(мой алгоритм) что я удаляю ребро, проверяю, можно ли попасть из начальной точки во ВСЕ, если да - это не ребро, если НЕ можем попасть, то это было ребро. проверим, затем восстановим ребро. и т.д.

Мне кажется что бяка сидит в функции Next, где то я просмотрел что то, скорее всего связанное с возвращаемыми значениями, хотя я не уверен.

зы ОЧЕНЬ жду помощи....

зыы пример в первом посте совпадает с рисунком.
зыыы граф БЕЗ стрелок!!

Автор: Lomir 4.5.2007, 18:34

Promitheus, у тебя как бы разбивания циков в графе. Но думаю ты хотел сделать разбивание ССК (сильно-связанных компонннтов), но ССК существую только с орентированных графах.

sapphiro, твоим методом нахождение мостов на O(E*V^2) ~ О(V^4) на полном графе.
Если надо что-то более быстрое, тогда вроде надо копать на тему maxflow/mincut, хотя нехнаю сможет ли mincut найти все мосты.

У тебя кажись next() неправильно работает, попробуй так:

Код


int visited[100];

void DFS(int vertex)
{
    visited[vertex] = 1;
    for (int i = 0; i < n; ++i)
        if (MAT[vertex][i] && !visited[i]) DFS(i);
}

int isBridge()
{
    memset(visited, 0, sizeof visited);
    DFS(0);
    for (int i = 0; i < n; ++i)
        if (!visited[i])
           return 0;
    return 1;
}

Автор: Promitheus 5.5.2007, 09:40

Вы имеете ввиду, что если можно попасть из 1 в 2, то само собой можно попасть из 2 в 1, и ориентация путей в графе не имеет значения ? Просто есть виды графов, в которых имеют место быть стрелки т.е если есть путь из 3 в 4, то не факт существования пути из 4 в 3. Насколько мне помнится.

Исходя из ваших определений получится 3 пары элементов и один как нечетный будет болтаться один, так и задумано ?

Автор: sapphiro 5.5.2007, 18:15

Исправил кое что в NEXT или DFS (куму как нравится...)

Код


int Next(int i, int j){                        
if (i == j)
    return 1;
for(k = i-j; k < n; k++)
{
    if(MAT[i][k]==1)
        return Next(k ,j);           // вот в этом месте не возвращается, подъем с рекурсии идет тупо прямо...

    else{
        if(k == (n - 1))
            return 0;
    }

}
}

тока теперь она не ходит обратно....
МОЖЕТ ЕСТЬ У КОГО АЛГОРИТМ "ПОИСКА ПУТЕЙ В ГРАФЕ"?, я думаю он сюда очень подойдет, но нигде не нашел на С++?????????

Автор: Lomir 5.5.2007, 20:50

Поиска путей!? Это как понять? Поиск крадчайшего из путей?
А чем моя реализация DFS неподходит?

П.С. У тебя в Next() нету запоминания пройденых вершин. И вопше, странных какой-то DFS.

Автор: sapphiro 6.5.2007, 12:04

1 - поиска ЛЮБОГО из путей
2 - я в твоей не вьехал, где вторая вершина.... т.е мост или ребро это типа две соединенные вершины. Получается что isBridge() возврщает 1 если НЕ мост, 0 - если мост. А мост между чем и чем??? между vertex и (?).......(?). Вот тут я не вьехал.....
--------------------------------------------------------------------------------------(Добавлено позже)
Я ее сделал!!!! Ура!!
Как всегда выкладываю никому не нужный код этой программы, может кому пригодится. Вроде работает!!!

Код


#include <stdio.h>                
#include <windows.h>
int n, k, kol;    //n вершин
int MAT[7][7];    //матца смежности            //7 или 5 - число вершин в мат-це
int visited[7*7];
char message[100];    
//int Next(int i, int j);
int IsZero (int j);
int isBridge(int j);
int DFS(int vertex, int j);
bool key = true;
int Ti, Tj;

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 = i+1; j < n; j++){    
    if(MAT[i][j]==1){         
        MAT[i][j]=0;        
        MAT[j][i]=0;    
 
        if (IsZero(i) == 0){
            CharToOem("\nНайден мост: ",message);                
            printf(message);
            printf("%d - %d\n", i+1,j+1);}
        else{

            if(isBridge(j) == 0){

                if(key == true && Tj != j){
                    CharToOem("\n\nНайден мост: ",message);                
                    printf(message);
                    printf("%d - %d\n", i+1,j+1);}
            }
            
        }
        MAT[i][j]=1;
        MAT[j][i]=1;    
    }
}
return 0;        
}
int IsZero (int i){
int Sum = 0;    

for(int e = 0; e < n; e++)
    Sum += MAT[i][e];    
            
if(Sum == 0) 
    return 0;    
else 
    return 1;
}
int DFS(int vertex, int j)
{
    if(vertex != j){
    visited[vertex] = 1;
    for (int i = 0; i < n; ++i)
        if (MAT[vertex][i] && !visited[i])
            if(DFS(i, j) == 0)
                break;
                key = true;
    }
    if (vertex == j) {
        Tj = j;
        key = false;
        
        return 0;
    }
}
int isBridge(int j)
{
    bool key = true;
    memset(visited, 0, sizeof visited);
    DFS(0, j);
    for (int i = 0; i < n; ++i)
        if (!visited[i])
           return 0;
    return 1;
}
/*
int Next(int i, int j){                        
if (i == j)
    return 1;
for(k = 0; k < n; k++)
{

    if(MAT[i][k]==1)
    {
        if(k == j) 
            continue;
        return Next(k ,j);
    }
    else{
        if(k == (n - 1))
            return 0;
    }
}
}*/