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

Методом обхода в глубину определить число компонент связности и цикломатическое число графа - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Разработать приложение, позволяющее организовать работу по учету занятости номеров гостиницы http://www.cyberforum.ru/cpp-beginners/thread751953.html
Всем доброго времени суток! Решила сама начать осваивать С++ до поступления в институт, где изучение этого языка программирования обязательно будет. Уже начала неплохо разбираться в некоторых вещах, но одно остается для меня дремучим лесом: работа с файлами. Мне было предложено разработать приложение, позволяющее организовать работу по учету занятости номеров гостиницы. Так вот, всю ту кучу,...
C++ Как задать кодировку при записи в файл или чтения из него У меня блокнот Notepad++, своей программой я записываю в некоторый текстовый файл все символы ASCII. Проблема вот в чем: программа отображает символы правильно, а блокнот крякозябры. Если я меняю кодировку в блокноте на такую, что он все нормально показывает, то моя программа открывает этот файл с другими символами запись: ofstream my ("1.txt"); char a; for (int i = 0; i <... http://www.cyberforum.ru/cpp-beginners/thread751940.html
C++ Не работает подсчет суммы введенных чисел
#include <iostream> using namespace std; int main() { std::cout << 'Enter two numbers' << std::endl; int v1, v2; std::cin >> v1 >> v2; std::cout << 'The summ of' << v1 << 'and' << v2 << 'is' << v1 + v2 << std::endl; return 0;
C++ Видео лекции: Основы C++
На просторах интернета нашел замечательный ресурс как lektorium.tv Мне понравились предоставленные азы в этих видео лекциях, которые в большинстве ВУЗов не даются. Список тем: Эффективная работа с памятью. Объектно-ориентированное программирование на примере языка C . Обобщенное программирование на примере языка C . STL. Дополнительная литература:
C++ Вычислить сумму значений элементов массива http://www.cyberforum.ru/cpp-beginners/thread751909.html
Сделайте три варианта программы. В первом элементы массива определяются в программе, во втором задаются пользователем, а в третьем заполняются с помощью генератора случайных чисел. Помогите пожалуйста.
C++ Определить, сколько значений в массиве превышают среднее значение [-50.120] Сделайте три варианта программы. В первом элементы массива определяются в программе, во втором задаются пользователем, а в третьем заполняются с помощью генератора случайных чисел. Помогите пожалуйста. подробнее

Показать сообщение отдельно
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
03.01.2013, 20:17     Методом обхода в глубину определить число компонент связности и цикломатическое число графа
пример поиска в глубину
C++
1
2
3
4
5
6
7
8
9
10
11
12
std::vector<std::vector<int> > gr;
std::vector<bool> used;
 
void dfs(int v)
{
    used[v] = true;
    for (int i = 0; i < gr[v].size(); ++i)
    {
         if (!used[gr[v][i]])
             dfs(gr[v][i]);
    }
}
поиск подсчет компонент связности с использование поиска в глубину
C++
1
2
3
for (int i = 0; i < gr.size(); ++i)
    if (!used[i])
        dfs(i), ++c;
Добавлено через 42 минуты
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
#include <iostream> 
#include <vector>
 
std::vector<std::vector<int> > gr;
std::vector<bool> used;
 
void dfs(int v)
{
    used[v] = true;
    for (size_t i = 0; i < gr[v].size(); ++i)
    {
        if (gr[v][i] && !used[i])
            dfs(i);
    }
}
 
int main(void) 
{
    size_t n, r = 0;
    std::cin >> n;
    gr.resize(n, std::vector<int> (n) );
    used.resize(n, false);
    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < n; ++j)
        {
            std::cin >> gr[i][j];
            if (i < j && gr[i][j])
                ++r;
        }
    }
    size_t c = 0;
    for (size_t i = 0; i < used.size(); ++i)
    {
        if (!used[i])
            dfs(i), ++c;
    }
    std::cout << c << std::endl;
    std::cout << r - n + c;
    return 0; 
}
оформление и проверки добавите сами
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru