Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 16.06.2013
Сообщений: 8
1

Неверная работа алгоритма нахождения моста в графе

27.06.2013, 19:33. Показов 878. Ответов 6
Метки нет (Все метки)

есть работающий код на с++:
C++ (Qt)
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
void bridge(int v, int p = -1)
    {
        used[v] = true;
        timer++;
        _low[v] = timer;
        numvert[v] = _low[v];
        for (size_t i=0; i<around[v].size(); ++i) //around[v] - окрестность для вершины v
        {
            int to = around[v][i];
            if (to == p)  continue;
            if (used[to])
                _low[v] = min (_low[v], numvert[to]);
            else 
            {
                bridge (to, v);
                _low[v] = min (_low[v], _low[to]);
                if (_low[to] > numvert[v])
                    cout << "Мост из: " << v+1 << " в: " << to+1 << endl;
            }
        }
    }   
    void find_bridge()
    {
        timer = 0;
        for (int i=0; i<quantity; ++i)
            used[i] = false;
        for (int i=0; i<quantity; ++i)
            if (!used[i])
                bridge(i);
    }
переделала код в джаве, не работает:
Java
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
43
void bridge(int v, int p)    
    {
        p = -1;
    used.setElementAt(true, v);
        timer++;
    numvert.setElementAt(timer, v); 
        _low.setElementAt(timer, v); 
        int minimal;
    for (int i = 0; i < around.elementAt(v).size(); ++i) 
    {
            int to = around.elementAt(v).elementAt(i);
            if (to != p)  // { continue;}
            {
                if (used.elementAt(to))
                {
                    minimal = min (_low.elementAt(v), numvert.elementAt(to));
                    _low.setElementAt(minimal, v);
                }
                else
                {
                    bridge (to, v);
                    minimal = min (_low.elementAt(v), _low.elementAt(to));
                    _low.setElementAt(minimal, v);
                    if (_low.elementAt(to) > numvert.elementAt(v)) // проблема тут
                    {
                       System.out.print("Мост из: " + (v+1));
                       System.out.println(" в: " + (to+1));
                    }
                }   
            }
         }
    }
    void find_bridge()
    {
        timer = 0;
        int t = 0;
    for (int i=0; i<quantity; i++)
            used.set (i, false);
    for (int i = 0; i < quantity; ++i)
        { if (!used.elementAt(i))
            {bridge(i, t);}
        }
    }
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.06.2013, 19:33
Ответы с готовыми решениями:

Поиск моста в графе
namespace WindowsFormsApp8 { public partial class Form1 : Form { public Form1()...

Анимирование алгоритма поиска в глубину на графе
Вообщем нужно сделать такую же анимация как здесь -...

Реализация алгоритма А* (поиск кратчайших расстояний на графе)
В общем, уже несколько дней бьюсь над небольшой проблемой: написал поиск кратчайших путей на...

Алгоритм нахождения вершин маршрута в графе
По запросам в поисковике всё время выдаёт решение на тему поиск кратчайшего пути, мне это не нужно,...

6
Заблокирован
27.06.2013, 20:30 2
ок!
1
0 / 0 / 0
Регистрация: 16.06.2013
Сообщений: 8
27.06.2013, 20:37  [ТС] 3
а помочь можете?
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
27.06.2013, 20:53 4
Цитата Сообщение от fitter_happier Посмотреть сообщение
p = -1;
Это же параметр по умолчанию в C++ коде. В Java нужно сделать два метода с разным количеством аргументов:
Java
1
void bridge(int v, int p)
и
Java
1
void bridge(int v) { bridge(v, -1); }
1
0 / 0 / 0
Регистрация: 16.06.2013
Сообщений: 8
27.06.2013, 21:14  [ТС] 5
а как будет различаться реализация, не пойму
0
127 / 131 / 11
Регистрация: 25.12.2011
Сообщений: 443
27.06.2013, 21:51 6
Цитата Сообщение от fitter_happier Посмотреть сообщение
а как будет различаться реализация, не пойму
Для метода с одним параметром уже приведена реализация выше.
1
0 / 0 / 0
Регистрация: 16.06.2013
Сообщений: 8
27.06.2013, 22:00  [ТС] 7
спасибо, сейчас попробую

Добавлено через 6 минут
всё получилось, спасибо большое
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.06.2013, 22:00

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Алгоритм нахождения ВСЕХ ободов в графе
Дан связанный граф (не менее 16 вершин), нужно найти все подграфы, являющиеся ободами. (Обод –...

работа прозрачного моста
Почему фреймы компьютера Барни не могут вступать в коллизии с компьютером Бетти Устройство со...

Исследовать алгоритм нахождения Эйлерова пути в неориентированном графе
Задание: Реализовать в виде программы и исследовать алгоритм нахождения эйлерова пути в...

Алгоритм Флери для нахождения цикла Эйлера в графе
Может кто-нибудь делал такую работу, я просто не представляю как ее делать. Помогите пожалуйста.


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

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

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