50 / 6 / 2
Регистрация: 15.07.2010
Сообщений: 112
1

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

04.03.2012, 23:19. Показов 1516. Ответов 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;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.03.2012, 23:19
Ответы с готовыми решениями:

Разработайте программу реализующую поиск в ширину в графе из заданной вершины
Лекции пропустил теперь незнаю как написать=( выручайте.. 1.Разработайте программу с очередью....

Написать программу с использованием алгоритма обхода графа в ширину
Написать программу с использованием алгоритма обхода графа в ширину.За ранее спасибо

Поиск строки в строке, помогите написать макрос
Подскажите, пожалуйста, как написать макрос чтобы выполнял следующее: из двух независимых...

Помогите написать программу
Доброго времени суток всем! Сразу к делу. Я хочу написать программу учета...

7
программист С++
841 / 600 / 147
Регистрация: 19.12.2010
Сообщений: 2,014
05.03.2012, 00:21 2
поиском в ширину кротчайшие пути не найдешь
тут например Дейкстра нужен или алгоритм Форда-Беламанна
1
50 / 6 / 2
Регистрация: 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 минуту
я понимаю но дано задание именно поиском в ширину найти кратчайшие пути
0
программист С++
841 / 600 / 147
Регистрация: 19.12.2010
Сообщений: 2,014
05.03.2012, 11:32 4
Цитата Сообщение от JerryJackson Посмотреть сообщение
я понимаю но дано задание именно поиском в ширину найти кратчайшие пути
значит нифига ты не понимаешь
1
Higher
1952 / 1218 / 120
Регистрация: 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, затем номера стартовой и конечной вершины.
1
50 / 6 / 2
Регистрация: 15.07.2010
Сообщений: 112
05.03.2012, 18:50  [ТС] 6
спасибо

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

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

Добавлено через 25 минут

0
Higher
1952 / 1218 / 120
Регистрация: 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 // номера промежуточных вершин, включая начальную
Вообще код заточен под эту задачу, проходит там все тесты.
1
50 / 6 / 2
Регистрация: 15.07.2010
Сообщений: 112
05.03.2012, 19:22  [ТС] 8
Извините , да все таки все работает
я неправильно вводил данные
спасибо)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.03.2012, 19:22
Помогаю со студенческими работами здесь

Помогите написать программу
Даны действительные числа a1, a2, …, a2n. Получить: а) a1, an+1, a2, an+2, …, an, a2n; єсли...

Помогите написать программу!!!
Пусть дан текстовый файл. Заменить последовательность P1 подряд идущих символов последовательностью...

Помогите написать программу
Здравствуйте! Извиняюсь конечно что обращаюсь к вам с таким, казалось бы, пустяковым вопросом, но...

помогите написать программу
помогите написать программу на языке lisp даны два списка одинаковой длины, эленты которых-числа....


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru