0 / 0 / 0
Регистрация: 29.07.2019
Сообщений: 10
1

Поиск мостов в в неорированном графе (без петель и кратных ребер)

18.04.2020, 19:49. Показов 813. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
В чём суть. На просторах инет находил реализации алгоритма поиска мостов в графе. Все они похожи, запускается обход в глубину и в нём же условия для поиска моста. Но проблема в том, что все эти алгоритмы находят либо не все мосты, либо добавляют лишние.
Пожалуйста помогите разобраться в чём может быть ошибка или я что-то не учёл...
Пробую реализовать через ООП, только начал изучать, поэтому особо не критикуйте

Пример графа, в которым некорректно находит мосты. Первая строка это количество высот и рёбер, далее сами рёбра
5 5
1 2
2 3
3 1
3 4
3 5

Правильный ответ: 3 - 4 и 3 - 5 но выводит иное((
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Graph
{
public:
    Graph(std::istream& in);
    void AdjacencyMatrixInitialization();
    void UploadGraph(std::istream& in);
    void DFS(int v, int p = -1);
    void FindBridges();
private:
    int timer;
    size_t edgesCount;
    size_t pointsCount;
 
    std::vector<int> tin, fup;
    std::vector<bool> used;
    std::vector<std::vector<int>> AdjacencyMatrix;
    std::map<int, int> junctionBridges;
    std::vector<size_t> junctionPoints;
 
    static const size_t NUMBER_INPUT_PARAMETERS = 2;
    static const size_t MAX_POINTS_COUNT = 400;
    static const size_t MAX_EDGES_COUNT = Graph::MAX_POINTS_COUNT * (Graph::MAX_POINTS_COUNT - 1) / 2;
};
}
 
void Graph::DFS(int v, int p)
{
    used[v] = true;
    tin[v] = fup[v] = timer++;
 
    for (int i = 0; i < this->pointsCount; ++i)
    {
        if (AdjacencyMatrix[v][i] == 1)
        {
            int to = 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])
                {
                    //junctionBridges.insert(pair<int, int>(++v, ++to));
                    cout << "bridge: (" << ++v << " , " << ++to << ")\n";
                }
            }
        }
    }
}
 
void Graph::FindBridges()
{
    for (int i = 0; i < this->pointsCount; ++i)
    {
        if (!used[i])
        {
            DFS(i);
        }
    }
}
Добавлено через 3 часа 12 минут
Нашёл ошибку! Тема снята!

Добавлено через 50 секунд
Нашёл ошибку! Тема снята!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.04.2020, 19:49
Ответы с готовыми решениями:

Сколько существует неизоморфных графов без петель и кратных ребер, имеющих 7 вершин и 18 ребер?
Помогите, пожалуйста. Задачи: 1) Сколько существует неизоморфных графов без петель и кратных...

Поиск мостов в графе
дано условие: найти мосты в графе. порылся в книжках и соорудил вот это. vector&lt;int&gt; g; bool...

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

Нахождение мостов в графе.
Дан граф.Найти все мосты.Мост-ребро при удалении которого создается компонента связности(проще...

0
18.04.2020, 19:49
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.04.2020, 19:49
Помогаю со студенческими работами здесь

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

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

Добавление ребер в графе
Дано n вершин и m ребер в неориентированном графе без петель и кратных ребер. Нужно добавить...

Количество ребер в графе
Какое максимальное количество ребер может быть в простом слабо связном ориентированном графе на 10...

Сколько ребер в графе?
Помогите, пожалуйста разъяснить мне данную задачку по графам. Верно ли я решила задание? Условие:...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru