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

Нахождение мостов в графе. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.96
Wolfed
2 / 2 / 1
Регистрация: 15.02.2011
Сообщений: 70
04.05.2011, 22:40     Нахождение мостов в графе. #1
Дан граф.Найти все мосты.Мост-ребро при удалении которого создается компонента связности(проще говоря если удалить такое ребро,то невозможно будет попасть из одной вершины в ны другую(ну которые соединяло ребро, тоесть если ребро соединяло вершину 1 и вершину 2, то если при удалении из вершины 1 нельзя попасть в вершину 2, то это мост))
входные данные статические, тоесть представлены квадратным массивом размерности NxN,где N количество вершин,если между вершиной N и вершиной M есть ребро, то значение в массиве A[N][M]=1. Если же нет то a[N][m]=0.
Например
0 1 1
1 0 0
1 0 0
Означает что существует ребро между вершинами 1-2,1-3,3-1,3-2.
Предлагаю решить все через рекурсию.
Предлагаю свой алгоритм
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
#include <iostream>
#include <vector>
using std::vector;
int g[10][10];
vector<char> used;
int timer;
int tin[10],fup[10];
int min(int a,int b)
{ if(a<b) return a;else return b;}
 
void dfs (int v, int p) {
    int i;
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (i=0; i<4;i++) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] > tin[v])
                printf ("MOST raspolojen mejdy vershinami %d - %d\n",v+1,to+1);
        }
    }
}
 
int main(){
    int n=4,x,i,j;  
FILE *in=fopen("input.txt","r");
for (i=0;i<n;i++)
    for (j=1;j<=n;j++)
    {fscanf(in,"%d",&x);
        g[i][j]=x;
}
fclose(in);
timer=0;
used.assign(n,false);
dfs(0,0);
system("PAUSE");
}
Интересует вопрос,почему высчитывает неправильно, тоесть какую бы я матрицу не вводил то всеравно ответ будет 1 2(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2011, 22:40     Нахождение мостов в графе.
Посмотрите здесь:

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). C++
C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
C++ Поиск мостов в графе
Реализация поиска мостов на графе C++
C++ Нахождение отрицательного цикла в графе и вывод цикла
C++ Нахождение циклов в графе , используя смежную матрицу

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.05.2011, 06:07     Нахождение мостов в графе. #2
Цитата Сообщение от Wolfed Посмотреть сообщение
Означает что существует ребро между вершинами 1-2,1-3,3-1,3-2.
Правильно будет: 1-2,1-3,3-1,2-1.
Куча ошибок в коде. Это те которые бросились в глаза:
Цитата Сообщение от Wolfed Посмотреть сообщение
vector<char> used;
Цитата Сообщение от Wolfed Посмотреть сообщение
used[v] = true;


Цитата Сообщение от Wolfed Посмотреть сообщение
FILE *in=fopen("input.txt","r");
for (i=0;i<n;i++)
for (j=1;j<=n;j++)// обратите внимание на индексацию по j
{fscanf(in,"%d",&x);
g[i][j]=x;
}
Цитата Сообщение от Wolfed Посмотреть сообщение
void dfs (int v, int p) {
....
for (i=0; i<4;i++) {
int to = g[v][i];
Wolfed, Вы лучше словами опишите Ваш алгоритм. На примере той матрицы смежности, которую привели.
Yandex
Объявления
05.05.2011, 06:07     Нахождение мостов в графе.
Ответ Создать тему
Опции темы

Текущее время: 20:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru