Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
BlackPrince
0 / 0 / 0
Регистрация: 13.11.2015
Сообщений: 5
#1

Длина пути (поиск в ширину) - C++

09.03.2017, 14:00. Просмотров 270. Ответов 1
Метки нет (Все метки)

В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Гарантируется, что путь существует.
Входные данные
Во входном файле записаны в первой строке число N - количество вершин в графе (1<N≤100) и M – количество ребер. Затем записаны M пар целых чисел – номера вершин определяющих ребра. Затем записаны номера двух вершин - начальной и конечной.
Выходные данные
В выходной файл выведите в первой строке - длину пути (количество ребер, которые нужно пройти), а во второй путь от начальной до конечной вершины.

Пример:
input.txt
7 6
1 2
1 5
3 4
2 3
3 6
6 7
3 5

output.txt
3
3 2 1 5
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.03.2017, 14:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Длина пути (поиск в ширину) (C++):

Длина пути между городами - C++
Прошу помощи в решении задачи. Я не могу поняты как это сделать потому прошу вашей помощи. Надо найти путь который прошел...

Графы, нахождение наименьшего пути между вершинами обходом в ширину - C++
Здравствуйте, помогите пожалуйста, нужно по заданной матрице смежности графа определить наименьший путь от вершины a до вершины b, свой...

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

Поиск в ширину - C++
Можете, пожалуйста, объяснить как понять вот этот код: vector &lt; vector&lt;int&gt; &gt; g; // граф непонятно, как описан вектор. код взят...

поиск в ширину - C++
Помогите объяснить это по русски каждую строчку что тут написнао . #include &lt;cstdio&gt; #include &lt;vector&gt; #include &lt;stack.h&gt; #include...

поиск в ширину(Рекурсивный) - C++
Программа запускается но выдает ошибку(Задача такая: Создать программу для решения задачи построения слова из некоторого множества букв...

1
art-evgeniy
6 / 6 / 3
Регистрация: 20.11.2016
Сообщений: 120
09.03.2017, 20:33 #2
ни хрена не понял;
поясните на примере!


Во входном файле записаны в первой строке число N - количество вершин в графе (1<N≤100) и M – количество ребер
Значит, относительно примера
7 вершин в графе и 6 рёбер

Затем записаны M пар целых чисел – номера вершин определяющих ребра.
1 2
1 5
3 4
2 3
3 6
6 7

Затем записаны номера двух вершин - начальной и конечной.
Значит начальная вершина 3 и конечная -5

Со вторым файлом всё понятно.

Добавлено через 3 часа 10 минут
всё, сделал -ГОТОВО.


вот верный код
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
#include <fstream>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
/*
algorythm poiska v shirinu
 
int n;
int m;
vector<int> *adj;
vector<bool> used;
queue<int> q;
 
void bfs(int v) {
    if (used[v]) {
        return;
    }
    q.push(v);
    used[v] = true;
    while (!q.empty()) {
        v = q.front();
        q.pop();
        printf("%d ", (v + 1));
                for (int i = 0; i < adj[v].size(); ++i) {
            int w = adj[v][i];
                        if (used[w]) {
                continue;
            }
            q.push(w);
            used[w] = true;
    }
}
 
 
void readData() {
    scanf("%d %d", &n, &m);
    adj = new vector<int>[n];
 
    for (int i = 0; i < m; ++i) {
        int v, w;
        scanf("%d %d", &v, &w);
        v--;
        w--;
        adj[v].push_back(w);
    }
 
       used.resize(n, false);
}
 
void run() {
    readData();
    for (int v = 0; v < n; ++v) {
        bfs(v);
    }
      for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }
    delete[] adj;
 
    used.clear();
}
*/
 
int main()
{
    setlocale(LC_ALL, "RUSSIAN");
    ifstream in("input.txt");
 
    if (in.is_open())
    {
 
        int count = 0;
        int temp;
 
        while (!in.eof())
        {
            in >> temp;
            count++;
        }
 
        in.seekg(0, ios::beg);
        in.clear();
 
        int count_space = 0;
        char symbol;
        while (!in.eof())
        {
 
            in.get(symbol);
            if (symbol == ' ') count_space++;
            if (symbol == '\n') break;
        }
 
        in.seekg(0, ios::beg);
        in.clear();
 
 
        int n = count / (count_space + 1);
        int m = count_space + 1;
        double **x;
        x = new double*[n];
        for (int i = 0; i<n; i++) x[i] = new double[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                in >> x[i][j];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                cout << x[i][j] << "\t";
            cout << "\n";
        }
        ofstream fout("output.txt");
        for( int i = 0; i < n; i++ )
        {
           for( int j = 0; j < m; j++ )
        fout << x[i][j]<<"\t";
        fout << "\n";
        }
        fout.close();
 
        for (int i = 0; i<n; i++) delete[] x[i];
        delete[] x;
 
        in.close();
    }
    else
    {
        cout << "File not found";
    }
    return 0;
}

про алгоритм подробнее можно почитать здесь
http://cybern.ru/obxod-v-shirinu-realizaciya-na-c.html

Код верный. Но комментарии за отдельную плату

Добавлено через 1 минуту
делал для обработки любых чисел в файле, так и для условий задачи.

Как на входе, так и на выхлопе - в файле оутпут.
Граф хранится в двумерном массиве.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2017, 20:33
Привет! Вот еще темы с ответами:

Поиск в ширину на графе - C++
#include &quot;stdafx.h&quot; #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; #include&lt;vector&gt; #include&lt;queue&gt; using namespace...

графы. поиск в ширину - C++
у меня такая задача: Определить, является ли неориентированный граф двудольным графом через алгоритм поиска в ширину. мне хотя бы...

Деревья (длина пути ...) - C++
Используя очередь или стэк написать функцию, которая находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины Е;...

Поиск в ширину - Неправильно выполняется программа - C++
ПОМОГИТЕ! ПОЧЕМУ НЕПРАВИЛЬНО ВЫПОЛНЯЕТСЯ ПРОГРАММА? #include&lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;queue&gt; using namespace...


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

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

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