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

Матрица смежности графа - поиск в глубину - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры http://www.cyberforum.ru/cpp-beginners/thread1172474.html
Задача на С++ (do..while) Нужно ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры? Буду премного благодарна за помощь ^^
C++ Преобразовать символ '5' в число 5 добрый день, надо перемножить элементы типа char: с*c но данные тип не перемножается, по этому мне нужно перевести символ в число, но как это сделать я не знаю, подскажите пожалуйста, спасибо заранее. http://www.cyberforum.ru/cpp-beginners/thread1172460.html
C++ Как объединенить две строки для передачи функции соообщения?
#include "stdafx.h" #include <windows.h> //#include <iostream> //using namespace std; int main() { char* str = new char; double dbl = 1.1234123412341234; sprintf(str, "%.16g", dbl...
Определить k-ю цифру последовательности 10111213...9898 (выписаны подряд все двухзначные числа) C++
Даны целое число л (1<=k<=180) и последовательность цифр 10111213...9898, в которой вписаны подряд все двухзначные числа. Определить k-ю цифру, если известно, что k - нечетное число.
C++ Чат-Бот с++ http://www.cyberforum.ru/cpp-beginners/thread1172427.html
Хочу написать чат-бот на с++ для простого общения(друзей нет) но даже не знаю с чего начинать, весь интернет перешарил но так и не нашёл нормальный исходник. Прошу дать хоть маленький исходник чтобы...
C++ Посоветуйте хорошую библиотеку для работы с zip-архивами Здравствуйте. Быть может кто-то посоветует что-то хорошее? В гугл не посылать, пол интернета перелопатил, попадается только либы каменного века, которые не хотят компилироваться или не... подробнее

Показать сообщение отдельно
krvnk
13 / 13 / 1
Регистрация: 01.04.2010
Сообщений: 166
12.05.2014, 02:12  [ТС]
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <ctime>
#include <vector>
#include <queue>  
//#include <algorithm>
#include <conio.h>
using namespace std;
 
const int n=10000;
int i, j;
int GM[n][n];
//матрица смежности графа
/*int GM[n][n] =
{
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0}
};*/
 
bool *vis=new bool[n];
bool *visited=new bool[n];
 
vector < vector <int> > g(n);
vector <int> used(n); // массив меток. в начале его нужно заполнить 0.
 
//  unsigned int end_time = clock();
//  cout << "runtime N^2 = " << (end_time-start_time)/1000.0 <<" N="<<N<< endl;
    
//сложность n^2
void BFS(bool *passed, int unit)
{
    //очередь
    int *posl=new int[n];
    //указатели очереди
    int count, head;
    for (i=0; i<n; i++) posl[i]=0;
    count=0; head=0;
    posl[count++]=unit;
    passed[unit]=true;
    while (head<count)
    {
        unit=posl[head++];
        //cout<<unit+1<<" ";
        for (i=0; i<n; i++)
            if (GM[unit][i] && !passed[i])
            {
                posl[count++]=i;
                passed[i]=true;
            }
    }
    delete []posl;
}
//сложность n+m
void bfs2 (int s)
{
queue<int> q;
q.push (s);
//cout<<s+1<<" ";
vector<bool> used (n);
used[s] = true;
while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
        if (!used[*i-1])
        {
            used[*i-1]=true;
            q.push(*i-1);
            //cout<<*i<<" ";
        }
}
}
//сложность n^2
void DFS(int st)
{
    int r;
    //cout<<st+1<<" ";
    visited[st]=true;
    for (r=0; r<=n; r++)
        if ((GM[st][r]!=0) && (!visited[r]))
    DFS(r);
}
//сложность n+m
void dfs2 (int v) {
    used[v] = true;
    //cout<<v+1<<" ";
    for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
        if (!used[*i-1])
        {
            dfs2 (*i-1);
            
        }
    
}
 
void main()
{
    srand (time(NULL));
    setlocale(LC_ALL, "Rus");
    int start;
    cout<<"Стартовая вершина >> "; cin>>start;
    cout<<"Матрица смежности графа: "<<endl;
 
    for (i=0;i<n;i++)
        for (j=i;j<n;j++)
        {
            GM[i][j]=rand() % 2;
            GM[j][i]=GM[i][j];
        }
    for (i=0;i<n;i++)
        GM[i][i]=0;
    int l,k;
    l=k=0;
    for (i=0; i<n; i++)
    {
        used[i]=0;
        visited[i]=false;
        vis[i]=false;
        for (j=0; j<n; j++)
        {
            
            //cout<<" "<<GM[i][j];
        }
        cout<<endl;
    }
    for(i = 0; i < n; ++i)
    {
        for (j=0;j<n;j++)
            if (GM[i][j]==1) k++;
        g[i].resize(k);
        for (j=0;j<n;j++)
            if (GM[i][j]==1) 
            {
                g[i][l] = j+1;
                l++;
            }
     l=0;k=0;
    }
    cout<<"Матрица векторная: "<<endl;
    for (i=0; i<n; i++)
    {
        for (j=0; j<(int)g[i].size(); j++)
        {
            
            //cout<<" "<<g[i][j];
        }
    }
    cout<<"Порядок обхода в ширину N^2: \n";
    unsigned int start_time =  clock();
    BFS(vis, start-1);
    //cout<<endl;
    unsigned int end_time = clock();
    cout << "runtime N^2 = " << (end_time-start_time)/1000.0 <<" N="<<n<< endl;
    cout<<endl;
 
    cout<<"Порядок обхода в ширину N+M: \n";
    start_time =  clock();
    bfs2(start-1);
    end_time =  clock();
    //cout<<endl;
    cout << "runtime N^2 = " << (end_time-start_time)/1000.0 <<" N="<<n<< endl;
    cout<<endl;
 
    cout<<"Порядок обхода в глубину N^2: \n";
    start_time =  clock();
    DFS(start-1);
    end_time =  clock();
    //cout<<endl;
    cout << "runtime N^2 = " << (end_time-start_time)/1000.0 <<" N="<<n<< endl;
    cout<<endl;
 
    cout<<"Порядок обхода в глубину M+N: \n";
    start_time =  clock();
    dfs2(start-1);
    end_time =  clock();
    //cout<<endl;
    cout << "runtime N^2 = " << (end_time-start_time)/1000.0 <<" N="<<n<< endl;
    delete []visited;
    delete []vis;
    system("pause>>void");
}
всё работает спасибо.
но тут вопрос, а почему с вектором и с очередью дольше выполняется программа, чем просто с массивом? Слишком много обращений да?
И как упростить, чтобы быстрее чем с матрицами выполнялось? Что нужно использовать?
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru