Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
6o6ep4ik
-9 / 0 / 1
Регистрация: 23.10.2015
Сообщений: 175
1

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

12.10.2016, 09:32. Просмотров 405. Ответов 10
Метки нет (Все метки)

Нужно использовать матрицу смежности.
Можно ли это реализовать так: строится матрица смежности [nxn].
Проставляются значения. (или определенная матрица и определенные значения).
А потом алгоритм пытается удалить одно ребро и проверяет, действительно ли это мост.
Если удалить одно ребро, то нельзя будет попасть в другую вершину. Это и будет мостом.
Мысли, определения верные? Посоветуйте что-нибудь пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2016, 09:32
Ответы с готовыми решениями:

Построить алгоритм прохождения всех циклов графа
Задан граф G=(V,R) из N связанных вершин. Построить алгоритм прохождения всех...

Алгоритм для поиска всех путей между 2 вершинами графа
Здравствуйте, возник вопрос какой алгоритм необходимо использовать для поиска...

Алгоритм нахождения всех возрастающих комбинаций
Доброго время суток форумчане. Встретил задачу над корой бьюсь уже второй день,...

Алгоритм для нахождения всех булевых функций от N переменных
Помогите придумать оптимальный алгоритм для данного условия! очень нужно...

Запишите программу нахождения изолированных вершин графа
Помогите пожалуйста.Запишите программу нахождения изолированных вершин графа. ...

10
Dmitriy_M
1428 / 1308 / 131
Регистрация: 20.03.2009
Сообщений: 4,677
Записей в блоге: 11
12.10.2016, 12:34 2
Роберт Седжвик Алгоритмы на C++
0
6o6ep4ik
-9 / 0 / 1
Регистрация: 23.10.2015
Сообщений: 175
12.10.2016, 18:33  [ТС] 3
Dmitriy_M, книга это, конечно, хорошо, но не то что мне нужно. Я хочу понять, что я должен сделать, и правильно ли я мыслю.
0
Avazart
15.10.2016, 21:12
  #4

Не по теме:

Цитата Сообщение от 6o6ep4ik Посмотреть сообщение
книга это, конечно, хорошо, но не то что мне нужно.
Тогда может бухло и наркотики помогут?
Цитата Сообщение от 6o6ep4ik Посмотреть сообщение
Я хочу понять что я должен сделать и правильно я мыслю.
Мыслите уже хорошо ))

PS: Может все же удастся вас уговорить по хорошему посмотреть книгу )))

0
6o6ep4ik
-9 / 0 / 1
Регистрация: 23.10.2015
Сообщений: 175
15.10.2016, 21:33  [ТС] 5
Avazart,

Не по теме:

да, я уже пролистал половину сегодня (книги), завтра внимательно этим вопросом займусь.

p.s. ошибся, должно было быть написано: правильно ли я мыслю

0
Croessmah
15.10.2016, 22:13
  #6

Не по теме:

Цитата Сообщение от 6o6ep4ik Посмотреть сообщение
p.s. ошибся, должно было быть написано: правильно ли я мыслю
Исправил.

0
6o6ep4ik
-9 / 0 / 1
Регистрация: 23.10.2015
Сообщений: 175
16.10.2016, 14:24  [ТС] 7
Как исправить ошибки:
Ошибка (активно) class "std::vector<int, std::allocator<int>>" не содержит члена "pb" (строка 51, 64)
Ошибка C2039 pb: не является членом "std::vector<int,std::allocator<_Ty>>" (строка 55, 68)

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <vector>
#include <iostream>
using namespace std;
 
const int MAXN = ... ; //максимальное возможное количество вершин во входном графе
 
int n, bridges, par[MAXN], bl[MAXN], comp[MAXN], sizen[MAXN];
 
void init() {
    for (int i = 0; i<n; ++i) {
        bl[i] = comp[i] = i;
        sizen[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}
 
int get(int v) {
    if (v == -1)  return -1;
    return bl[v] == v ? v : bl[v] = get(bl[v]);
}
 
int get_comp(int v) {
    v = get(v);
    return comp[v] == v ? v : comp[v] = get_comp(comp[v]);
}
 
void make_root(int v) {
    v = get(v);
    int root = v,
        child = -1;
    while (v != -1) {
        int p = get(par[v]);
        par[v] = child;
        comp[v] = root;
        child = v;  v = p;
    }
    sizen[root] = sizen[child];
}
 
int cu, u[MAXN];
 
void merge_path(int a, int b) {
    ++cu;
 
    vector<int> va, vb;
    int lca = -1;
    for (;;) {
        if (a != -1) {
            a = get(a);
            va.pb(a);
 
            if (u[a] == cu) {
                lca = a;
                break;
            }
            u[a] = cu;
 
            a = par[a];
        }
 
        if (b != -1) {
            b = get(b);
            vb.pb(b);
 
            if (u[b] == cu) {
                lca = b;
                break;
            }
            u[b] = cu;
 
            b = par[b];
        }
    }
 
    for (size_t i = 0; i<va.size(); ++i) {
        bl[va[i]] = lca;
        if (va[i] == lca)  break;
        --bridges;
    }
    for (size_t i = 0; i<vb.size(); ++i) {
        bl[vb[i]] = lca;
        if (vb[i] == lca)  break;
        --bridges;
    }
}
 
void add_edge(int a, int b) {
    a = get(a);   b = get(b);
    if (a == b)  return;
 
    int ca = get_comp(a),
        cb = get_comp(b);
    if (ca != cb) {
        ++bridges;
        if (sizen[ca] > sizen[cb]) {
            swap(a, b);
            swap(ca, cb);
        }
        make_root(a);
        par[a] = comp[a] = b;
        sizen[cb] += sizen[a];
    }
    else
        merge_path(a, b);
}
0
Avazart
Эксперт С++
7723 / 5632 / 549
Регистрация: 10.12.2010
Сообщений: 25,402
Записей в блоге: 17
16.10.2016, 14:36 8
Цитата Сообщение от 6o6ep4ik Посмотреть сообщение
Как исправить ошибки:
Ошибка (активно) class "std::vector<int, std::allocator<int>>" не содержит члена "pb" (строка 51, 64)
Никак, ибо в векторе нет pb.
Может va.push_back(a) ? Может кто-то гений-сокращений? )))
1
6o6ep4ik
-9 / 0 / 1
Регистрация: 23.10.2015
Сообщений: 175
16.10.2016, 14:39  [ТС] 9
Avazart, отлично, а что в main функции писать?
0
Avazart
Эксперт С++
7723 / 5632 / 549
Регистрация: 10.12.2010
Сообщений: 25,402
Записей в блоге: 17
16.10.2016, 14:40 10
А мне покуда знать?
0
6o6ep4ik
-9 / 0 / 1
Регистрация: 23.10.2015
Сообщений: 175
16.10.2016, 14:41  [ТС] 11
Avazart, а должно быть что там реализовано?
0
16.10.2016, 14:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.10.2016, 14:41

Нахождения кратчайших путей между всеми парами вершин графа
Подскажите как можно улучшить алгоритм Флойда-Уоршелла что-бы он верно работал...

Алгоритма Дейкстры: нахождения расстояния от узла 1 в каждый узел графа
помогите с реализацией алгоритма Дейкстры для нахождения расстояния от узла 1 в...

Написать программу для нахождения кратчайшего пути между заданными вершинами графа
visual studio windows forms нужна программа,которая будет вычислять...


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

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

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