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

Помогите написать программу поиск в ширину - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Продублировать в нем элементы с четными номерами (2, 4, …) http://www.cyberforum.ru/cpp-beginners/thread512446.html
Дан массив размера N. Продублировать в нем элементы с четными номерами (2, 4, …). Условный оператор не использовать.
C++ getpeername возвращает ошибку Получаю сообщение и пытаюсь определить адрес отправителя через: unsigned int len=sizeof addr; int getpeer=getpeername(desc,(struct sockaddr *) &addr, &len); При каждом вызове она возвращает -1, ошибку 310 (Transport endpoint is not connected) При этом IP адреса она возвращает, но я не могу быть уверен что ip правильные, т.к. иногда замечаю среди них локальные (например 192.168.5.55), хотя все... http://www.cyberforum.ru/cpp-beginners/thread512439.html
C++ Передача char массива в MessageBox
Добрый день господа. Не могу решить проблему. Пытаюсь обработать сообщение WM_MOVE и передать координаты окна в MessageBox. Но не знаю как правильно передать или сконвертировать массив типа char* в LPCTSTR. вот код программы: void CMyTestFrame::OnMove(int x, int y) { CFrameWnd::OnMove(x, y); char* coord= new char; sprintf(coord,"Left=%d|Top=%d",x,y);
Удаление из массива всех элементов, встречающихся ровно два раза C++
Дан целочисленный массив размера N. Удалить из массива все эле-менты, встречающиеся ровно два раза, и вывести размер полученного мас-сива и его содержимое
C++ Какая разница между #include<> и #include""? http://www.cyberforum.ru/cpp-beginners/thread512430.html
Позволите спросить несколько вопросов: 1)Какая разница между #include<> и #include"" 2)Если нужно значение объекта и я не собираюсь его менять, есть ли смысл передавать его по ссылке, чтобы избежать его копирования Заранее спасибо!
C++ Динамическая матрица, пять сортировок, перестановки и сравнения Здравствуйте! Нужна помощь с одним заданием... Задается размер квадратной матрицы, заполняется случайными числами, потом выводится таблица с количеством перестановок и сравнений по 5 видам сортировок. Сортируются диагональные элементы матрицы по возрастанию. Типы сортировок: быстрая, выборки, пузырьком, вставкой, шелла. Спасибо! подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.03.2012, 12:41     Помогите написать программу поиск в ширину
Цитата Сообщение от sandye51 Посмотреть сообщение
поиском в ширину кротчайшие пути не найдешь
тут например Дейкстра нужен или алгоритм Форда-Беламанна
Дейкстра и Форд-Беллман нужны для взвешенных графов, для невзвешенных есть поиск в ширину.
Так можно
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
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <sstream>
 
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];
        }
       
        return std::vector<int> (res.begin(), res.end() );;
    }
}
Только тут на другие входные данные рассчитано, а именно вначале задается количество вершин, затем матрица смежности n*n, затем номера стартовой и конечной вершины.
 
Текущее время: 21:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru