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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.96
Wolfed
2 / 2 / 1
Регистрация: 15.02.2011
Сообщений: 70
#1

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

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

Поиск мостов в графе - C++
Доброй ночи,задача состоит в отыскании мостов в графе. Много где есть в свободном доступе алгоритм примерно такого рода: ...

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

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Нахождение циклов в графе , используя смежную матрицу - C++
Возникла такая задача: используя смежную матрицу, нужно определить циклы графа. Граф ненаправленный и нет мультивекторов(т.е. наша матрица...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...

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

1
valeriikozlov
Эксперт С++
4672 / 2498 / 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, Вы лучше словами опишите Ваш алгоритм. На примере той матрицы смежности, которую привели.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2011, 06:07
Привет! Вот еще темы с ответами:

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

Нахождение отрицательного цикла в графе и вывод цикла - C++
Вот программа по нахождению отрицательного цикла в графе и вывод цикла void Floyd(int GR, int parents , int V) { int checking; int...

Алгоритм нахождения всех мостов графа - C++
Нужно использовать матрицу смежности. Можно ли это реализовать так: строится матрица смежности . Проставляются значения. (или...

Поменять нахождение min среди двумерного массива, на нахождение min в каждой сточке - C++
Поменять нахождение min среди двумерного массива, на нахождение min в каждой сточке #include &lt;iostream&gt; #include &lt;cstddef&gt; #include...


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

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

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