Форум программистов, компьютерный форум 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] Сделайте три варианта программы. В первом элементы массива определяются в программе, во втором задаются пользователем, а в третьем заполняются с помощью генератора случайных чисел. Помогите пожалуйста. подробнее

Показать сообщение отдельно
тАлекс
0 / 0 / 0
Регистрация: 03.01.2013
Сообщений: 2
03.01.2013, 18:50     Методом обхода в глубину определить число компонент связности и цикломатическое число графа
Методом обхода в глубину определить число компонент связности и цикломатическое число графа – минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим.
Способ представления графа - матрица смежности.
Подскажите, пожалуйста, является ли написанный мной способ поиска числа компонент связности поиском в глубину?
Если нет, то подскажите, что требуется изменить.

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();
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 17:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru