Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 16.07.2014
Сообщений: 11

Поиск пути из одной вершины графа в другую

10.12.2017, 12:42. Показов 3869. Ответов 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
class Graph {
    int numVerticles;
    int **adjMatrix;
    bool *visited;
    void dfsPr(int v1, int v2, int &len, int *&way) {
        visited[v1] = true;
            for (int i = 0;i < numVerticles;i++) {
                if (adjMatrix[v1][i] != 0 && !visited[i]) {
                    way[len] = v1;
                    len++;
                    dfsPr(i, v2, len, way);
                }
            }
    }
public:
    Graph(int verticles) : numVerticles(verticles), adjMatrix(new int*[numVerticles]), visited(new bool[numVerticles]) {    
        for (int i = 0; i < numVerticles; i++) {
            visited[i] = false;
            adjMatrix[i] = new int[numVerticles];
            for (int j = 0; j < numVerticles; j++)
                adjMatrix[i][j] = 0;
        }       
    }
    void addEdge(int from, int to) {
        if (from > numVerticles || to > numVerticles || from < 0 || to < 0){
            cout << "Invalid edge!\n";
        }
        else
            adjMatrix[from][to] = 1;
    }
    void dfs(int v1, int v2) {
        int len = 0;
        int *way = new int[numVerticles];
        dfsPr(v1, v2, len, way);
        if (len == 0)
            cout << -1;
        else {
            cout << len << endl;
            for (int i = 0; i < len; i++)
                cout << way[i] << " ";
        }
        delete way;
    }
};
Функция, выполняющая поиск, - dfsPr. В функцию dfs заносятся значения v1 и v2, после производится вывод длины и самого пути. Проблема в том, что я не пойму, как ограничить обход именно значением v2.

Добавлено через 19 часов 14 минут
Кое-что сделать удалось. Ограничил поиск вершиной v2 вот так:
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
/*
0 1 1 0 1 
1 0 0 1 1 
1 0 0 0 1 
0 1 0 0 1 
1 1 1 1 0
Найти путь из вершины 0 в 1, например.
*/
 
void dfsPr(int v1, int v2, int *&way, int &wayIndex, int &len) {
    visited[v1] = true;
    way[wayIndex] = v1;
    wayIndex++;
    if (v1 == v2)
        return;
    for (int i = 0;i < numVerticles;i++)
        if (adjMatrix[v1][i] != 0 && !visited[i]){
            len++;
            dfsPr(i, v2, way, wayIndex, len);
        }
}
void dfs(int v1, int v2) {
    int wayIndex = 0;
    int len = 0;
    int *way = new int[numVerticles];
    dfsPr(v1, v2, way, wayIndex, len);
    if (len == 0)
        cout << -1;
    else {
        cout << len << endl;
        for (int i = 0; i < wayIndex; i++)
            cout << way[i] << " ";
    }
    delete way;
}
Вывод программы такой:
4
0 1 2 4 3
, что, конечно же, не правильно. Вопрос: почему, как только v1 (передаваемое рекурсивно в цикле значение) стало равным 1, функция не прекратила свою работу? По идее она должна остановиться после того, как занесет в массив way 0 и 1, а длину (первое число вывода) должно быть 1, т.к. между вершинами 0 и 1 — одно ребро.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
10.12.2017, 12:42
Ответы с готовыми решениями:

Нахождение кратчайшего пути от одной вершины графа до другой
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include &lt;iostream.h&gt; #include...

Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа
Здравствуйте! Есть задача найти самый длинный путь от первой до последней вершины ацикличного ориентированного невзвешенного графа....

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

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
10.12.2017, 12:42
Помогаю со студенческими работами здесь

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

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

Найти вершины графа, находящихся на заданном расстоянии от данной вершины
Есть неориентированный граф задан матрицей смежности, нужно найти вершины графа находящихся на заданном расстоянии от данной вершины. Буду...

Раскрасить вершины графа, чтобы смежные вершины были окрашены в различные цвета
Добрый день. Прошу вашей помощи от безысходности. 4 дня назад выдана задача, которую требуется решить за неделю, по остаточному сроку,...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины
Здравствуйте! Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Ниже машинный перевод статьи The Thinkpad X220 Tablet is the best budget school laptop period . Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы,. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru