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

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

09.03.2017, 14:00. Просмотров 960. Ответов 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
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.03.2017, 14:00
Ответы с готовыми решениями:

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

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

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

поиск в ширину
Помогите объяснить это по русски каждую строчку что тут написнао . #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