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

поиск в глубину - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Бинарное возведение матрицы в степень http://www.cyberforum.ru/cpp-beginners/thread522281.html
Подскажите, пожалуйста, как оно реализуется, причем, пишут, что если матрица размером n*n, и нужно возвести ее в степень k - сложность O( n^3 log k ). O( n^3 * k ) написать не сложно, а вот как тут применить бинарное возведение? Может я не знаю каких-то тождеств? Добавлено через 33 минуты :scratch::scratch::scratch:
C++ найти количество слов, которые имеют последнюю букву первого слова. добрый день помогите пожалуйста с задачей. надо найти количество слов, которые имеют последнюю букву первого слова. заранее благогдарен http://www.cyberforum.ru/cpp-beginners/thread522274.html
C++ Вычислить объемы тетрайда, гексаэдра и октаэдры, если длины ребер многогранников одинаковы и равны 3,55 см.
Вычислить объемы тетрайда, гексаэдра и октаэдры, если длины ребер многогранников одинаковы и равны 3,55 см.
статический вид -> динамический вид C++
Всем привет. Может кто помоч передалать данную прогу в динамический вид? #include <cstdlib> #include <iostream> using namespace std; int matrix; int n,max1,str,x1;
C++ Реализация отношений между классами is-a, has-a, uses-a в С++ http://www.cyberforum.ru/cpp-beginners/thread522236.html
Где можно найти информацию по отношениям между объектами классов is-a, has-a, uses-a и и их реализация средствами С++. В инете очень мало информации. Особенно о uses-a. Нашел слабенькое описание вопроса в книге Дж. Коплиена "Программирование на C++". Описано сложным языком, а по uses-a почти ничего :(. Как это отношение можно реализовать? Или где это описано человеческим языком?
C++ Решение СЛАУ методом Гаусса, индексы Собственно программа решает слау методом гаусса. Как найти индексы главного элемента на второй итерации? #include <iostream.h> #include <math.h> void main(void) { int N,i,j,k,l,m,ypos; cout <<"Enter N: "; // Ввод номера варианта cin >>N; подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.03.2012, 02:39     поиск в глубину
Цитата Сообщение от stiv.loh Посмотреть сообщение
всеравно не работает(((

Не по теме:

все логично, что написали, то и получилось


У Вас код не завершенный. В общем-то все правильно (создаете невзвешенный, неориентированный граф), кроме одной строчки:
Цитата Сообщение от stiv.loh Посмотреть сообщение
C++
1
dfs (n);
У Вас нет вершины с индексом n. А есть вершины с индексами от 0 до n-1.
Кроме того, сама функция, которую Вы взяли отсюда:
http://e-maxx.ru/algo/dfs
она делает поиск в глубину, но никакой задачи не выполняет. Грубо говоря если вызвать эту функцию вот так:
C++
1
dfs (0);
то при поиске в глубину будут помечены все вершины от 0 до n-1 в векторе:
C++
1
vector<bool> used;
и все. Т.е. все вершины из которых есть путь от вершины 0 будут помечены true. Остальные останутся с меткой false.
Я не знаю какую задачу Вы хотите решить (условие задачи в теме не увидел), но с помощью данного алгоритма можно например решить такую задачу: определить до скольких вершин нет пути из 1 вершины. Тогда Вам осталось подсчитать после вызова
C++
1
dfs(0);
сколько вершин осталось с меткой false в used.
Или например можно решить такую задачу: определить сколько независимых подграфов существует в заданом графе. В этом случае будет несколько вызовов
C++
1
dfs();
Добавлено через 9 минут
да еще одно, перед вызовом
C++
1
dfs();
желательно сделать:
C++
1
2
        for(int i=0; i<n; i++)
            used.push_back(false);
 
Текущее время: 03:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru