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

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

18.04.2020, 17:10. Показов 964. Ответов 0
Метки нет (Все метки)

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

input.txt
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
69
class Graph
{
public:
    Graph(std::istream& in);
    void AdjacencyMatrixInitialization();
    void UploadGraph(std::istream& in);
    void DFS(int v, int p = -1);
    void FindBridges();
    void PrintBridgesAndPoints();
 
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);
        }
    }
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.04.2020, 17:10
Ответы с готовыми решениями:

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

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

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

Программа, которая будет минимальным изминением убирать в заданном графе мосты
*Убирать Скорее всего при помощи добавления рёбер..

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

Как найти число вершин и ребер в графе окресности каждой пары вершин
Как найти число вершин и ребер в графе окресности каждой пары вершин? Добавлено через 5 минут В...

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

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

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

Количество ребер в полном графе
Откуда взята формула, которая определяет количество ребер в полном графе?? n(n-1)/2 Если можно, то...

Вероятность отсутствия ребер в графе
Доброго времени суток! Нуждаюсь в вашей помощи. Есть граф типа квадратной решетки N*N, в котором мы...


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

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

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