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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
тАлекс
0 / 0 / 0
Регистрация: 03.01.2013
Сообщений: 2
03.01.2013, 18:50     Методом обхода в глубину определить число компонент связности и цикломатическое число графа #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
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
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
#include <locale.h>
#include <conio.h>
#include <string>
#include <math.h>
using namespace std;
 
int main()
{setlocale(LC_ALL,"RUSSIAN"); 
int n;  
bool**b;
cout << "\nВВЕДИТЕ РАЗМЕРНОСТЬ (ЧИСЛО ВЕРШИН): " ;
cin >> n;
const int nn=n;
b=new bool*[nn];
for (int i=0;i<nn;i++)
{
    b[i]=new bool[nn];
}
cout << "\nЗАДАТЬ ГРАФ (МАТРИЦА СМЕЖНОСТИ): \n" ;
for (int i=0;i<nn;i++)
    for (int j=0;j<nn;j++)
{
    int c;
    cout<<"["<<char(int('a')+i)<<"]"<<"["<<char(int('a')+j)<<"]"<<" = ";
    cin>>c;
    if (c==1||c==0)
    {if(c==1)
    b[i][j]=true;
    else b[i][j]=false;
    }
    else {cout<<"\nОШИБКА!\n";j=j-1;continue;}
    b[i][i]=false;
}
    cout <<"\n\nМАТРИЦА СМЕЖНОСТИ: \n";
    for (int i=0;i<nn;i++)
    {cout<<endl;
    for (int j=0;j<nn;j++)
        cout<<b[i][j];
    }
 
 
//---------------------МАТРИЦА ПУТЕЙ
    bool**p;
    p=new bool*[nn];
for (int i=0;i<nn;i++)
{
    p[i]=new bool[nn];
}
int re=0;
for (int i=0;i<nn;i++)
    for (int j=0;j<nn;j++)
    {
        if(b[i][j]==1) re++;
        p[i][j]=b[i][j];
    }
 
    for (int i=0;i<nn;i++)
    for (int j=0;j<nn;j++)
        if (p[i][j]==true)
         for (int z=0;z<nn;z++)
        if (p[j][z]==true&i!=z)    
        p[i][z]=true;
    cout <<"\n\nМАТРИЦА ПУТЕЙ: \n";
    for (int i=0;i<nn;i++)
    {cout<<endl;
    for (int j=0;j<nn;j++)
        cout<<p[i][j];
    }
//------------------------------------
    int *visit=new int[nn];
    int ssk=0;
    char**Gl=new char*[nn];
    for (int i=0;i<nn;i++)
    Gl[i]=new char[nn];
    for (int i=0;i<nn;i++) visit[i]=0;
    for (int g=0;g<nn;g++)
    {int k=1;
        if (visit[g]==0)//если не посетили вершину
        {Gl[g][0]=char(int('a')+g);
        visit[g]=1;
    for (int j=0;j<nn;j++)
        if (p[g][j]==1 & p[j][g]==1){
        Gl[g][k]=char(int('a')+j);
        visit[j]=1;
        k++;
        }ssk++;
        }
    }
    cout <<"\n\nСИЛЬНО СВЯЗНАЯ КОМПОНЕНТА: \n";
    for (int i=0;i<nn;i++)
    {cout<<endl;
    for (int j=0;j<nn;j++)
        cout<<Gl[i][j];
    }
    cout<<"\n\nЧИСЛО CCK = "<<ssk<<endl;
    int cm=0;
    cm=ssk+re-nn;
    cout<<"\n\nЦИКЛОМАТИЧЕСКОЕ ЧИСЛО  = "<<cm<<endl;
    getch();
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.01.2013, 18:50     Методом обхода в глубину определить число компонент связности и цикломатическое число графа
Посмотрите здесь:

Дано натуральное число n (n>99). Определить число сотен внем C++
C++ Определить, сколько пар (положительное число, отрицательное число) находятся в начале массива
C++ не компилируется задание: компонент связности графа - кто разберется
C++ Дано натуральное четырехзначное число n. Определить, является ли это число перевертышем
C++ Дано натуральное число х. Определить кратно ли это число 2, 3, 5
Компоненты связности графа поиском в глубину C++
C++ Ввести произвольное целое положительное число. Определить число с обратным порядком цифр заданного числа
C++ Дано трицифровое число.Определить имеет ли число одинаковые первую и последнюю цифры

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
03.01.2013, 20:17     Методом обхода в глубину определить число компонент связности и цикломатическое число графа #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
пример поиска в глубину
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; 
}
оформление и проверки добавите сами
тАлекс
0 / 0 / 0
Регистрация: 03.01.2013
Сообщений: 2
04.01.2013, 15:29  [ТС]     Методом обхода в глубину определить число компонент связности и цикломатическое число графа #3
Цитата Сообщение от softmob Посмотреть сообщение
пример поиска в глубину
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; 
}
оформление и проверки добавите сами

Я, наверно, чего-то не понимаю, но никакими ухищрениями я не смог запустить эту программу.
Ругается на:
error C2039: vector: не является членом "std"
error C2065: used: необъявленный идентификатор
error C2065: gr: необъявленный идентификатор
error C2228: выражение слева от ".resize" должно представлять класс, структуру или объединение
Yandex
Объявления
04.01.2013, 15:29     Методом обхода в глубину определить число компонент связности и цикломатическое число графа
Ответ Создать тему
Опции темы

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