ks192
1

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

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

Обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии от данной вершины
Реализуйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном...

Поиск в ширину по графу и вывод порядка обхода графа
Есть программа проводящая поиск в ширину по графу и выводящая порядок обхода этого графа, можете...

Поиск графа в ширину(без использования очереди и ArrayList)
Добрый день.Необходимо переделать следующий код,без использования Node,ArrayList,queue.Нужно...

По заданной матрице смежности простого графа построить каркас этого графа с использованием поиска в ширину
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.05.2013, 21:14

Выполнить обход в ширину неориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица инциденций
Буду очень благодарен, если поможете Выполнить обход в ширину неориентированного графа, начиная с...

Создать матрицу заданного графа
пользователь вводит количество ребер, вершин графа, а программа должна создать матрицу этого графа

Создать приложение, обработать событие OnShow, при котором форма плавно увеличивает ширину до заданного значения
Здравствуйте, помогите с задачей: Создать приложение, обработать событие OnShow, при котором форма...

Построить для заданного графа минимальное основное дерево
Построить для заданного графа минимальное основное дерево. Помогите на С++ написать задачку)...

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин)
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и...

Для заданного графа найдите минимальный остов (алгоритм Краскала)
Для заданного графа найдите минимальный остов с помощью алгоритма Краскала.


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

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

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