Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
BlackPrince
0 / 0 / 0
Регистрация: 13.11.2015
Сообщений: 5
#1

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

09.03.2017, 14:00. Просмотров 337. Ответов 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
http://www.cyberforum.ru/cpp-beginners/thread1074997.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.03.2017, 14:00
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Длина пути (поиск в ширину) (C++):

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

Поиск в ширину
Нужно написать программу поиска в ширину на с++ .

поиск в ширину
Помогите объяснить это по русски каждую строчку что тут написнао . #include...

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

Поиск в ширину
Здравствуйте, я ознакомился с поиском в ширину в общем виде, знаю принцип...

1
art-evgeniy
6 / 6 / 9
Регистрация: 20.11.2016
Сообщений: 120
09.03.2017, 20:33 #2
Лучший ответ Сообщение было отмечено BlackPrince как решение

Решение

ни хрена не понял;
поясните на примере!


Во входном файле записаны в первой строке число 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
Привет! Вот еще темы с решениями:

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

Поиск в ширину на графе
#include &quot;stdafx.h&quot; #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include...

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

Деревья (длина пути ...)
Используя очередь или стэк написать функцию, которая находит в непустом дереве...


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

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

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