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

Поиск циклов в графе. Поиск центра взвешенного графа - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 96
26.08.2013, 23:31     Поиск циклов в графе. Поиск центра взвешенного графа #1
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2013, 23:31     Поиск циклов в графе. Поиск центра взвешенного графа
Посмотрите здесь:

C++ Поиск ободов в графе
C++ Поиск циклов в графе
C++ поиск центра графа
Поиск на графе C++
Поиск всех циклов в неориентированном графе. C++
C++ Поиск в ширину на графе
Поиск Ф-циклов в графе C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NurlashKO
 Аватар для NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
28.08.2013, 15:24     Поиск циклов в графе. Поиск центра взвешенного графа #21
2)
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define sz 1000
 
int n, a[sz][sz], d[sz], exc[sz], R, w;
 
int main()
{
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];           // Читаем матрицу смежности графа, если ребра между вершинами нет то а[i][j] = -1
 
    //Находим кратчайшие расстояния между всеми парами вершын
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (a[i][j] != -1 && a[i][k] != -1 && a[k][j] != -1)
                    a[i][j] = min(a[i][k] + a[k][j], a[i][j]);
    //
    //Находим радиус графа, за одно подсчитываем эксцентриситет для каждой вершины
    R = (int)1e9;
    for (int i = 1; i <= n; i++)
    {
        w = 0;
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] != -1)
                w = max(w, a[i][j]);
        }
        exc[i] = w;
        R = min(R, exc[i]);
    }
    //
    //Если эксцентриситет вершины равен радиусу графа то эта вершина центр графа, выводим её.
    cout << "Center :" << endl;
    for (int i = 1; i <= n; i++)
        if (exc[i] == R)
            cout << i << " ";
}
Добавлено через 15 минут
1)
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define sz 1000
 
int n, a[sz][sz], c, d[sz], cnt;
 
bool check(int p, int t)
{
    if (p == t)
        return a[d[t]][d[1]];
    if (!a[d[p]][d[p + 1]])
        return false;
    return check(p + 1, t);
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];   //Читаем матрицу смежности, если есть ребро а[i][j] = 1, иначе 0
 
 
    for (int mask = 1; mask < (1 << n); mask++)     //Перебираем все возможные комбинации вершин (2 ^ n)
    {
        c = 0;
        for (int i = 0; i < n; i++)    //Выписываем вершины из текущей комбинации
            if (mask & (1 << i))
                d[++c] = i + 1;
        if (check(1, c))        //Если данные вершины образуют цикл, сообщаем об этом.
        {
            cnt++;
            cout << "Cycl " << cnt << " :" << endl;
            for (int i = 1; i <= c; i++)
                cout << d[i] << " ";
            cout << endl;
        }
    }
    
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
28.08.2013, 19:44     Поиск циклов в графе. Поиск центра взвешенного графа #22
NurlashKO, у меня вопрос по программе 2): судя по 17 строке, работа будет идти с орграфом. в 34 строке ищется максимальное значение в i-ой строке, т.е. эксцентриситет вы ищите как:
максимальное расстояние из всех минимальных расстояний от данной вершины до других вершин.
в той статье из вики, что я приводил ранее, говорится про экцентриситет так:
максимальное расстояние из всех минимальных расстояний от других вершин до данной вершины.
так собственно вопрос: википедия обманывает или я чего-то непонял? просветите
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2013, 19:51     Поиск циклов в графе. Поиск центра взвешенного графа
Еще ссылки по теме:

C++ Поиск отрицательых циклов в графе
C++ Поиск мостов в графе
Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом C++
Поиск отрицательных циклов в графе C++
Реализация матрицы смежности и инцидентности, поиск циклов в графе C++

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

Или воспользуйтесь поиском по форуму:
NurlashKO
 Аватар для NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
28.08.2013, 19:51     Поиск циклов в графе. Поиск центра взвешенного графа #23
Да, я ошибся. Я предполагал что граф не ориентирован (Моя ошибка что я это не уточнил).
Yandex
Объявления
28.08.2013, 19:51     Поиск циклов в графе. Поиск центра взвешенного графа
Ответ Создать тему
Опции темы

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