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

Матрица смежности графа - поиск в глубину - 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
Сообщений: 168

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

11.05.2014, 19:13. Просмотров 4528. Ответов 7
Метки (Все метки)

Здравствуйте дорогие форумчане. У меня тут небольшая ошибка. Никак не могу понять что к чему. Объясните пожалуйста.
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
#include <iostream>
#include <vector>
#include <conio.h>
using namespace std;
const int n=5;
int i, j;
//матрица смежности графа
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}
};
vector < vector <int> > g(n);
vector <int> used(n);
void dfs2 (int v){
    used[v] = 1; // ставим метку, что посетили данную вершину
    for (i = 0; i < (int)g[v].size(); i++){ // проходим по все ребрам.
        if (!used[g[v][i]]){ // смотрим были ли мы в вершине раньше
            //cout<<g[v][i]+1<<" "<<v<<" "<<i<<endl;
                 dfs2(g[v][i]); // если нет, то запускаемся из нее.
        }
    }
}
void main()
{
setlocale(LC_ALL, "Rus");
    int start;
    cout<<"Стартовая вершина >> "; cin>>start;
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;
    }
    for (i=0; i<n; i++)
    {
        for (j=0; j<(int)g[i].size(); j++)
        {
            
            cout<<" "<<g[i][j];
        }
        cout<<endl;
    }
cout<<"Порядок обхода в глубину: ";
    dfs2(start-1);
}
Добавлено через 34 минуты
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
#include <iostream>
#include <ctime>
#include <vector>
//#include <algorithm>
#include <conio.h>
using namespace std;
const int n=5;
int i, j;
//матрица смежности графа
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}
};
vector < vector <int> > g(n);
vector <int> used(n); // массив меток. в начале его нужно заполнить 0.
//vector <int> tin, tout; // время входа и выхода для каждой вершины.
//int timer = 0; // данная переменная поможет нам определять время входа и выхода.
 
bool *visited=new bool[n];
//int main()
//{ 
//  unsigned int start_time =  clock();
//  unsigned int end_time = clock();
//  cout << "runtime N^2 = " << (end_time-start_time)/1000.0 <<" N="<<N<< endl;
    
//}
 
//_______________________________________
void BFS(bool *passed, int unit)
{
    //очередь
    int *queue=new int[n];
    //указатели очереди
    int count, head;
    for (i=0; i<n; i++) queue[i]=0;
    count=0; head=0;
    queue[count++]=unit;
    passed[unit]=true;
    while (head<count)
    {
        unit=queue[head++];
        cout<<unit+1<<" ";
        for (i=0; i<n; i++)
            if (GM[unit][i] && !passed[i])
            {
                queue[count++]=i;
                passed[i]=true;
            }
    }
    delete []queue;
}
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);
}
void dfs2 (int v){
    used[v] = 1; // ставим метку, что посетили данную вершину
    for (i = 0; i < (int)g[v].size(); i++){ // проходим по все ребрам.
        
        if (!used[g[v][i]]){ // смотрим были ли мы в вершине раньше
            cout<<v+1<<" "<<g[v][i]<<""<<endl;
            dfs2(g[v][i]-1); // если нет, то запускаемся из нее.
        }
    }
    
}
//_______________________________________
//Главная функция
void main()
{
    setlocale(LC_ALL, "Rus");
    int start;
    cout<<"Стартовая вершина >> "; cin>>start;
    //массив посещенных вершин
    bool *vis=new bool[n];
    cout<<"Матрица смежности графа: "<<endl;
    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;
    }
    for (i=0; i<n; i++)
    {
        for (j=0; j<(int)g[i].size(); j++)
        {
            
            cout<<" "<<g[i][j];
        }
        cout<<endl;
    }
    cout<<"Порядок обхода в ширину: ";
    BFS(vis, start-1);
    cout<<"Порядок обхода в глубину: ";
    DFS(start-1);
    cout<<"Порядок обхода в глубину: \n";
    dfs2(start-1);
    delete []visited;
    delete []vis;
    system("pause>>void");
}
Вообщем весь код. Наполовину работает.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru