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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
JerryJackson
50 / 6 / 1
Регистрация: 15.07.2010
Сообщений: 112
#1

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

04.03.2012, 23:19. Просмотров 1165. Ответов 7
Метки нет (Все метки)

Здравствуйте!
Необходимо написать такую программу:
Входные данные - количество вершин графа и его ребра. Выход - вектор, содержащий кратчайшие пути из корня к соответствующей вершине.

выдает 0

Вот один из вариантов:
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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
 
#define N       500
 
typedef int graph_t[N][N];
typedef int labels_t[N];
 
struct queue_t
{
        // информационное поле
        int value;
        struct queue_t *next;
};
 
int scan_graph(graph_t graph)
{
        int tops_count, edges_count;
        int i,j,k;
 
        printf("Enter: ");
        scanf("%d",&tops_count);
        scanf("%d",&edges_count);
 
        for (i = 0; i < tops_count; i++)
                for (j = 0; j < tops_count; j++)
                        graph[i][j] = 0;
 
        for (k = 0; k < edges_count; k++)
        {
                scanf("%d%d", &i, &j);
                graph[i][j] = 1;
        }
 
        return tops_count;
}
 
void push(struct queue_t **start, struct queue_t **end, int value)
{
        struct queue_t *q = (struct queue_t *)malloc(sizeof(struct queue_t));
 
        q->next = NULL;
        q->value = value;
 
        if (*end != NULL)
        {
                (*end)->next = q;
                *end = q;
        }
        else
        {
                *start = q;
                *end = *start;
        }
}
 
int pop(struct queue_t **start, struct queue_t **end)
{
        int v = (*start)->value;
 
        struct queue_t *q = (*start)->next;
 
        free(*start);
 
        *start = q;
 
        if (*start == NULL)
                *end = NULL;
 
        return v;
}
 
int tops_count;
graph_t graph;
labels_t labels;
 
void func(graph_t graph, labels_t labels, int tops_count, int start_top)
{
        // поиск в ширину
        int i;
 
        for (i = 0; i < tops_count; i++)
                labels[i] = 0;
 
        struct queue_t *start = NULL, *end = NULL;
 
        push(&start, &end, start_top);
        labels[start_top] = 1;
 
        do
        {
                int top = pop(&start, &end);
 
                for (i = 0; i < tops_count; i++)
                        if (!labels[i] && graph[top][i])
                        {
                                labels[i] = 1;
                                push(&start, &end, i);
                        }
        } while (start != NULL);
}
 
int main()
{
        int i;
 
        tops_count = scan_graph(graph);
        func(graph,labels,tops_count,0);
 
        for (i = 0; i < tops_count; i++)
                if (labels[i])
                        printf("%d ", i);
 
        printf("\n");
 
        getch();
 
        return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
681 / 583 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
05.03.2012, 00:21     Помогите написать программу поиск в ширину #2
поиском в ширину кротчайшие пути не найдешь
тут например Дейкстра нужен или алгоритм Форда-Беламанна
JerryJackson
50 / 6 / 1
Регистрация: 15.07.2010
Сообщений: 112
05.03.2012, 01:18  [ТС]     Помогите написать программу поиск в ширину #3
Дейкстра
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
#include <iostream>
 
 
 
#define VERTEXES 9      //Число вершин в графе
 
using namespace std;
 
int v;
int main(int argc, char* argv[])
{
   
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;                             // Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
                                 0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };
 
   // Будем искать путь из вершины s в вершину g
   int s;                       // Номер исходной вершины
   int g;                       // Номер конечной вершины
   cout<<"Введите s: ";         // Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине
                         // на кратчайшем пути
 
   // Инициализируем начальные значения массивов
   int u;                   // Счетчик вершин
   for (u=0;u<p;u++)
   {
      t[u]=infinity; //Сначала все кратчайшие пути из s в i
        //равны бесконечности
      x[u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // Кратчайший путь из s в s равен 0
   x[s]=1; // Для вершины s найден кратчайший путь
   v=s;    // Делаем s текущей вершиной
 
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
        //найден кратчайший путь
                // и новый путь в u короче чем
        //старый, то
         {
            t[u]=t[v]+a[v][u];  //запоминаем более короткую длину пути в
        //массив t и
            h[u]=v;     //запоминаем, что v->u часть кратчайшего
        //пути из s->u
         }
      }
 
      // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет
                       // найден новый кратчайший путь. Она станет
                       // текущей вершиной
      for(u=0;u<p;u++) // Перебираем все вершины.
      {
         if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший
                               // путь и если длина пути в вершину u меньше
                               // уже найденной, то
         {
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1)
      {
         cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
         break;
      }
      if(v==g) // Найден кратчайший путь,
      {        // выводим его
         cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
           u=g;
           while(u!=s)
         {
            cout<<" "<<u;
            u=h[u];
         }
         cout<<" "<<s<<". Длина пути - "<<t[g];
           break;
      }
      x[v]=1;
   }
   system("pause");
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит
 
Нет пути из вершины 3 в вершину 6.
 
После ввода s = 0, q = 2 программа выводит
 
Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/
Добавлено через 1 минуту
я понимаю но дано задание именно поиском в ширину найти кратчайшие пути
sandye51
программист С++
681 / 583 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
05.03.2012, 11:32     Помогите написать программу поиск в ширину #4
Цитата Сообщение от JerryJackson Посмотреть сообщение
я понимаю но дано задание именно поиском в ширину найти кратчайшие пути
значит нифига ты не понимаешь
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.03.2012, 12:41     Помогите написать программу поиск в ширину #5
Цитата Сообщение от 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, затем номера стартовой и конечной вершины.
JerryJackson
50 / 6 / 1
Регистрация: 15.07.2010
Сообщений: 112
05.03.2012, 18:50  [ТС]     Помогите написать программу поиск в ширину #6
спасибо

только после ввода данных, результат не выводит

Добавлено через 20 секунд
Error выскакивает "Прервать"

Добавлено через 25 минут
[IMG]http://i026.***********/1203/60/39e43b93299b.png[/IMG]
[IMG]http://i026.***********/1203/60/39e43b93299bt.jpg[/IMG]
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.03.2012, 18:57     Помогите написать программу поиск в ширину #7
JerryJackson, а как вводите?
Пример ввода
C++
1
2
3
4
5
6
7
8
5 //количество вершин
//матрица смежности 5*5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5 //номера стартовой и конечной вершин
Вывод будет
C++
1
2
3 //количество промежуточных вершин
3 2 1 5 // номера промежуточных вершин, включая начальную
Вообще код заточен под эту задачу, проходит там все тесты.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2012, 19:22     Помогите написать программу поиск в ширину
Еще ссылки по теме:
C++ Помогите написать программу. Символы и строки
C++ Помогите написать программу простого словаря
Помогите написать программу с действительными числами. C++
Новичек) не могу написать программу, помогите плиз) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
JerryJackson
50 / 6 / 1
Регистрация: 15.07.2010
Сообщений: 112
05.03.2012, 19:22  [ТС]     Помогите написать программу поиск в ширину #8
Извините , да все таки все работает
я неправильно вводил данные
спасибо)
Yandex
Объявления
05.03.2012, 19:22     Помогите написать программу поиск в ширину
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru