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

Для заданного графа создать поиск в ширину на с++ - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ вывод массива из функции http://www.cyberforum.ru/cpp-beginners/thread859508.html
как можно передать массив optimal из функции #include<iostream> using namespace std; const int m1=1,m2=2,m3=3,r1=30,r2=60,r3=80; const int massa=4; int recurs(int); int main() {
C++ Функциональные объекты Здравствуйте. Я начал изучать STL и столкнулся с трудностями в работе с шаблонами. Я знаю как выглядят и работают простые шаблоны функций и классов, разобрался с шаблонами алгоритмов, но совсем запутался с функциональными объектами( В книге приведен следующий код: #include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; http://www.cyberforum.ru/cpp-beginners/thread859506.html
C++ Виртуальные функции
Здравствуйте,уважаемые посетители форума.Пишу программу созданию фигур и их перемещению на экране использую виртуальные функции.И написал,все работает,но возник один вопрос я объявляю виртуальные функции: virtual void Show();//функция показывает фигуру virtual void Hide();// скрывает фигуру virtual void ChangePosition(int NewX1,int NewY1);//изменяет её координаты и собственно...
C++ Лафоре, преобразование классов
// times1.cpp // программа перевода времени в 24-часовом написании // в 12-часовое #include <iostream> #include <string> using namespace std; /////////////////////////////////////////////////////////// class time12 { private:
C++ Зачем нужны сортировки http://www.cyberforum.ru/cpp-beginners/thread859476.html
Скажите пожалуйста, зачем при подготовке к олимпиаде по программированию, нужно учить алгоритмы: Быстрая сортировка, сортировка пузырьком и так дальше, если в языке c++ есть функция sort. И не нужно морочиться!. Смысл изучения этих алгоритмов?
C++ Запуск cmd с командой из программы Добрый вечер! В программе потребовалось запустить cmd с командой. Сначала подумал, мне нужно что то вроде system("H:\Graphviz2.30\bin\dot.exe -Tsvg H:\TSD\tsd9\tsd9\tsd9\current_graph.graphviz -o H:\TSD\tsd9\tsd9\tsd9\current_graph.svg"); но оно не заработало. Подскажите как запустить командную строку с данной строчкой? подробнее

Показать сообщение отдельно
ks192
Сообщений: n/a
08.05.2013, 21:14     Для заданного графа создать поиск в ширину на с++
Доброго времени суток всем!!!
Помогите пожалуйста нужно: для заданного графа создать поиск в ширину на с++. Граф задается пользователем не через файл. Нашла программу но там задается нулями и единицами, а нужно и другими цифрами

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
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <sstream>
#include <conio.h>
namespace mygraph
{
    typedef std::vector< int > T_row;
    typedef std::vector< T_row > T_matr;
    typedef std::vector< std::pair< int, int > > T_vertex_list;
 
    T_vertex_list Adjacency_matrix_to_Vertex_list( const T_matr & );
   
    int length_of_shortest_path( const T_matr &matrix, int start, int end );
    std::vector< int > shortest_path( const T_matr &matrix, int start, int end );
}
 
const int INF = -1;
 
int main()
{
    using namespace mygraph;
   
    int n;
    std::cin >> n;
 
    T_matr matrix(n, T_row(n) );
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            std::cin >> matrix[i][j];
    }
 
    int start, end;
    std::cin >> start >> end;
   
    if ( start == end )
    {
        std::cout << 0 << std::endl << start << std::endl;
        return 0;
    }
   
    std::vector< int > res = shortest_path( matrix, start - 1, end - 1 );
   
    if ( res.size() == 0 )
    {
        std::cout << -1 << std::endl;
        return 0;
    }
   
    std::cout << res.size() << std::endl << start << ' ';
    for (int i = 0; i < (int) res.size(); ++i)
        std::cout << res[i] + 1 << ' ';
       
    std::cout << std::endl;
   
}
 
namespace mygraph
{
    int length_of_shortest_path( const T_matr &matrix, int start, int end )
    {
        const int n = matrix.size();
       
        std::vector< int > d(n, INF);
        std::vector< bool > used(n);
        std::queue< int > qu;
       
        used[ start ] = true;
        d[ start ] = 0;
       
        qu.push( start );
       
        while ( !qu.empty() )
        {
            int v = qu.front();
            qu.pop();
           
            for (int i = 0; i < n; ++i)
            {
                if ( matrix[v][i] && !used[i] )
                {
                    used[i] = true;
                    qu.push(i);
                   
                    d[i] = d[v] + 1;
                }
            }
                   
        }
       
        return d[end]; 
    }
   
    T_vertex_list Adjacency_matrix_to_Vertex_list( const T_matr &matrix )
    {
        T_vertex_list res;
 
        for (int i = 0; i < (int) matrix.size(); ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if ( matrix[i][j] == 1 )
                {
                    res.push_back( std::make_pair(j + 1, i + 1) );
                }
            }
        }
 
        return res;
    }
   
    std::vector< int > shortest_path( const T_matr &matrix, int start, int end )
    {
        const int n = matrix.size();
       
        std::vector< int > len(n, INF);
        std::vector< int > parent(n);
        std::vector< bool > used(n);
       
        std::queue< int > qu;
       
        qu.push(start);
        used[start] = true;
        parent[start] = -1;
        len[start] = 0;
       
        while ( !qu.empty() )
        {
            int v = qu.front();
            qu.pop();
           
            for (int i = 0; i < n; ++i)
            {
                if ( !used[i] && matrix[v][i] )
                {
                    qu.push(i);
                    parent[i] = v;
                    len[i] = len[v] + 1;
                    used[i] = true;                
                }
            }
           
        }
       
        if ( len[end] == INF )
            return std::vector< int > ();
       
        int x = end;
           
        std::deque< int > res;
       
        while ( parent[x] != -1 )
        {
            res.push_front(x);
            x = parent[x];
        
        }
 
            system("pause");
 
        return std::vector<int> (res.begin(), res.end() );;
        
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 01:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru