0 / 0 / 1
Регистрация: 03.01.2013
Сообщений: 2
1

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

03.01.2013, 18:50. Показов 5161. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Методом обхода в глубину определить число компонент связности и цикломатическое число графа – минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим.
Способ представления графа - матрица смежности.
Подскажите, пожалуйста, является ли написанный мной способ поиска числа компонент связности поиском в глубину?
Если нет, то подскажите, что требуется изменить.

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();
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.01.2013, 18:50
Ответы с готовыми решениями:

Как вычислить цикломатическое число графа?
Как вычислить компонент связности графа &quot;p&quot; и цикломатическое число графа? using namespace std;...

Компоненты связности графа поиском в глубину
Доброго времени суток милые форумчане!!! Очень нужна ваша помощь, сама справиться не в силах. Нужно...

не компилируется задание: компонент связности графа - кто разберется
#include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;stdlib.h&gt; class Stack { private: int...

Цикломатическое число графа.
Найдите цикломатическое число графа G2 и нарисуйте его независимые циклы.

2
1255 / 705 / 359
Регистрация: 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; 
}
оформление и проверки добавите сами
3
0 / 0 / 1
Регистрация: 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" должно представлять класс, структуру или объединение
0
04.01.2013, 15:29
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.01.2013, 15:29
Помогаю со студенческими работами здесь

Цикломатическое число связного графа
Подскажите, пожалуйста, верно ли я решила задание? Дан G - связной граф (псевдограф). Количество...

Найти цикломатическое число графа
Степени вершин графа заданы списком (1,2,3,4,5,6,7,8,9,10,10,11). Найти цикломатическое число графа

Найдите цикломатическое число графа.
Найдите цикломатическое число графа G2 и нарисуйте его независимые циклы.

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru