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

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

Войти
Регистрация
Восстановить пароль
 
6o6ep4ik
-9 / 0 / 0
Регистрация: 23.10.2015
Сообщений: 175
#1

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

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

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

Построить алгоритм прохождения всех циклов графа - C++
Задан граф G=(V,R) из N связанных вершин. Построить алгоритм прохождения всех циклов графа. С++ Примечание: цикл – это замкнутое...

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

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

Алгоритм для нахождения всех булевых функций от N переменных - C++
Помогите придумать оптимальный алгоритм для данного условия! очень нужно плиз!!!!!!!(хотя бы для 4)

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

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

10
Dmitriy_M
1356 / 1239 / 114
Регистрация: 20.03.2009
Сообщений: 4,439
Записей в блоге: 11
12.10.2016, 12:34 #2
Роберт Седжвик Алгоритмы на C++
0
6o6ep4ik
-9 / 0 / 0
Регистрация: 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 / 0
Регистрация: 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 / 0
Регистрация: 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
Нарушитель
Эксперт С++
7231 / 5403 / 291
Регистрация: 10.12.2010
Сообщений: 23,945
Записей в блоге: 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 / 0
Регистрация: 23.10.2015
Сообщений: 175
16.10.2016, 14:39  [ТС] #9
Avazart, отлично, а что в main функции писать?
0
Avazart
Нарушитель
Эксперт С++
7231 / 5403 / 291
Регистрация: 10.12.2010
Сообщений: 23,945
Записей в блоге: 17
16.10.2016, 14:40 #10
А мне покуда знать?
0
6o6ep4ik
-9 / 0 / 0
Регистрация: 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
Привет! Вот еще темы с ответами:

Алгоритм определения планарности графа - C++
Задача: определить планарность графа, заданного списком смежности. Натолкните на истинный код, заранее признателен

Алгоритм получения кубического подграфа из графа - C++
Здравствуйте. Подскажите пожалуйста, где можно узнать алгоритм получения кубического подграфа из графа (не на с++) . Или литературу, где...

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

Напишите алгоритм вывода списка ребер неориентированного графа - C++
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер. Вот начало #include &lt;iostream&gt;...


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

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

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