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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Шифрование текста путем замены символов http://www.cyberforum.ru/cpp-beginners/thread1171120.html
Здравствуйте, уважаемые участники форума! Вот озадачился вопросом о создании программы шифровании текста путем замены символов. Задача, которую я себе поставил, очень сходна с вопросом пользователя vveronikka, с некоторой модификацией задачи, связанной с тем, что предполагается загрузка исходного текста из файла (стандартно - расширение doc). Также хотелось бы реализовать возможность замены...
C++ Сколько раз встречается неразрывный набор символов в строке Всем привет ! У меня есть программа, которая определяет, есть ли неразрывный набор символов в строке или нет. Подскажите, пожалуйста, что добавить в данный код, чтобы программа считала, сколько раз данный набор символов встречается в строке. Вот мой код: bool AllCharsInStr(const char *string1, char *string2) { int len = strlen(string2); // находим длину строки for (int i = 0; string1... http://www.cyberforum.ru/cpp-beginners/thread1171108.html
C++ Написать с помощью дочернего класса программу, получающую указанную последовательность
Даны натуральное число n, целочисленная квадратная матрица порядка n, получить b1, ...,bn, где bi это наименьшее из значений элементов, находящихся в начале i-й сроки матрицы до элемента, принадлежащей главной диагонали, включительно. Написать с помощью дочернего класса. Кто может выслать код написанный простым языком с коментами? У меня не получается, что бы выводил наименьшие число ниже...
Заменить последовательности пробелов в заданной строке одним пробелом C++
Добрый вечер! Подскажите пожалуйста, что не так? Задача программы: Заменить последовательности пробелов в заданной строке одним пробелом. #include<iostream>; #include<fstream>; #include<iomanip>; using namespace std; const int N=100;
C++ Почему для поиска по массиву берется значение его первого элемента, а не ноль? http://www.cyberforum.ru/cpp-beginners/thread1171099.html
Свем доброго времени суток и всех с праздником! #include "stdafx.h" #include <iostream> #include <cmath> using namespace std; int main() { setlocale ( LC_ALL,"Rus" ); const int n = 10;
C++ Перевод числа из p-ичной системы Вот ещё одно задание. Дана символьная строка, представляющая собой запись натурального числа в p-ичной системе счисления (2 ≤ р ≤ 9). Составить программу для перевода этого числа в десятичную систему счисления. #include <iostream> #include <string> using namespace std; //<type> <name> (,,...) //{<body>} подробнее

Показать сообщение отдельно
Ma3au
0 / 0 / 0
Регистрация: 05.02.2014
Сообщений: 14

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

09.05.2014, 23:56. Просмотров 238. Ответов 0
Метки (Все метки)

Задание следующее "Задана система двусторонних дорог, где для любой пары городов есть соединяющий их путь. Найти город с минимальной суммой расстояний до остальных городов". Нужно использовать поиск в ширину, либо поискв глубину.

Вот всё что сделал.
Пример входного файла:
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;
}
А вот как организовать нахождение пути, ума не хватает
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru