Форум программистов, компьютерный форум, киберфорум
Наши страницы

Обход графа в глубину - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Игра Космобой http://www.cyberforum.ru/cpp-beginners/thread285334.html
#include <iostream> #include <conio.h> #include <windows.h> #include <fstream> using namespace std; int main() { char c; int i,n;
C++ Массив Дано "r.w" незнаю как записать в массив {r,w} и одновременно сравнить есть ли там такая буква http://www.cyberforum.ru/cpp-beginners/thread285333.html
Двоичный фаил C++
люди помогите пожалуйста ни как не могу понять что за двоичный фаил сделал прогу с обычным фаилом а препад говорит что нужен двоичный... ни как не пойму вот сама задача В конец двоичного файла...
C++ Найти самое короткое слово в строке
суть задачи такова: нужно найти самое короткое слово в введённой пользователем строке и записать его в обратном порядке,то есть,например : мама -> амам. По нахождению короткого слова идеи есть,но ещё...
C++ Использование функций http://www.cyberforum.ru/cpp-beginners/thread285315.html
Даны три действительных числа x, y, z. Получить A= arccos((x^2+y^2-z^2)/(2xy)) - arccos(z^2*y/(x+z*y)) где arccos(a) = arctg ((sqrt(1-a^2))/a) помогитеб пожалуйста!!!
C++ Чтение и запись в файл Текст находится в файле, имя которого вводится с клавиатуры. Вывод результата также осуществляется одновременно в файл, имя которого вводится с клавиатуры, и на экран монитора. Дана... подробнее

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

Обход графа в глубину - C++

28.04.2011, 19:57. Просмотров 1981. Ответов 0
Метки (Все метки)

Дана бинарная матрица (1-между вершинами есть ребро, 0-между вершинами нет ребра соответственно) и две вершины. Необходимо найти путь между этими вершинами с помощью обхода в глубину. Может кто-нибудь помочь или поделиться материалом? Проблема в том, что не знаю, как связать сам двоичный массив и функцию, в которой работа идет с вектором.

Вот, например, нашел алгоритм

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector < vector<int> > g; // граф
int n; // число вершин
 
vector<int> color; // цвет вершины (0, 1, или 2)
 
vector<int> time_in, time_out; // "времена" захода и выхода из вершины
int dfs_timer = 0; // "таймер" для определения времён
 
void dfs (int v) {
    time_in[v] = dfs_timer++;
    color[v] = 1;
    for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
        if (color[*i] == 0)
            dfs (*i);
    color[v] = 2;
    time_out[v] = dfs_timer++;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru