Форум программистов, компьютерный форум CyberForum.ru

Графы.Поиск в глубину и в ширину - C++

Восстановить пароль Регистрация
 
Ma3au
0 / 0 / 0
Регистрация: 05.02.2014
Сообщений: 14
09.05.2014, 23:56     Графы.Поиск в глубину и в ширину #1
Задание следующее "Задана система двусторонних дорог, где для любой пары городов есть соединяющий их путь. Найти город с минимальной суммой расстояний до остальных городов". Нужно использовать поиск в ширину, либо поискв глубину.

Вот всё что сделал.
Пример входного файла:
5
0 3 4 1 5
22 0 4 5 4
2 3 0 1 5
22 3 4 0 4
1 5 1 5 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
#include <iostream>
#include <clocale>
#include <cstdlib>
#include <fstream>
#include <iomanip>
 
using namespace std;
 
 
struct Row
{
    int Num; // Номер вершины
    Row *Next; // Указатель на следующую вершину по порядку
    Row *Colum; // Указатель на вершину,в которую существует путь
};
int** get_matrix(){
    ifstream input("input.txt");
    if(!input){ 
        cout << "Файл не существует, либо заблокирован\n";
        system("pause");
        return 0;
    }
 
    int size;
    char var; 
 
    input >> size;
    int **adjac_matrix = new int *[size];   
    for(int i = 0; i < size; i++){
        adjac_matrix[i] = new int [size];
    }
 
    for(int i = 0; i < size; i++){
        for(int j = 0; j < size; j++){
            input >> adjac_matrix[i][j];
        }
    }
    input.close();
    return adjac_matrix;
}
Row *Convert(int **A, int N, Row *Top)
{
    int i, j;
    Row *P, *T, *C;
    // Построение очереди из вершин графа по порядку нумерации
    // Построение первого узла очереди
    P = new Row;
    P->Num = 0;
    P->Next = NULL;
    P->Colum = NULL;
    Top = P; // Сохраняем вершину очереди
    // Построение остальных узлов очереди 
    for (i = 1; i < N; i++)
    {
        T = new Row;
        T->Num = i;
        T->Next = NULL;
        T->Colum = NULL; // Сюда будем присоединять вершины в которые существует путь
        P->Next = T;
        P = T;
    }
    cout << '\n' << "Распечатаем очередь вершин" << '\n';
    P = Top;
    while (P != NULL)
    {
        cout << '\n' << P->Num;
        P = P->Next;
    }
    // Построение списков существующих путей из каждой вершины
    T = Top; P = Top;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (A[i][j] != 0) // Проверка существования пути
            {
                C = new Row; // Добавляем новый узел по указателю
                C->Num = j; // Заносим туда номер вершины, куда есть путь
                C->Next = NULL;
                C->Colum = NULL;
                P->Colum = C;
                P = C;
            }
        }
        T = T->Next; // Переходим к следующей вершине
        P = T;
    }
    return Top;
}
 
int main(){
    setlocale(LC_ALL, "Russian");
 
    int **adjac_matrix = get_matrix();  
    if(adjac_matrix == 0)
        return 0;
    Row *Top = new Row;
    Top = Convert(adjac_matrix, 5, Top);
    system("pause");
    return 0;
}
А вот как организовать нахождение пути, ума не хватает
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2014, 23:56     Графы.Поиск в глубину и в ширину
Посмотрите здесь:

Поиск в глубину C++
C++ поиск в глубину
Алгоритмы поиска в глубину и ширину C++
C++ графы,поиск в глубину
графы. поиск в глубину C++
C++ графы. поиск в ширину
C++ Графы, нахождение наименьшего пути между вершинами обходом в ширину
C++ Поиск в глубину

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru