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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Сравнение 2-ух char массивов http://www.cyberforum.ru/cpp-beginners/thread917578.html
Помогите. Имеется 2 char массива. Один содержит слово вводимое пользователем, а второй это же слово, только наоборот. Необходимо сравнить эти два массива, и в случае, если они совпадают, вывести, к примеру сообщение "yes". Как это реализовать?
C++ Дайте задачу новичку Мне очень скучно, я уже сделал все программы на которые только фантазии хватило :) Дайте мне пожалуйста какую-то задачу, только не очень сложную, я новичёк :) http://www.cyberforum.ru/cpp-beginners/thread917565.html
Сколько слов в файле? как найти? C++
Дан файл неопределённой длины. посчитать сколько в нём слов "end". Вот что я попытался сделать, но не получилось. Помогите пожалуйста. #include <iostream> #include <conio.h> #include <cstdlib> using namespace std; // функция определения символа void prog() { string fileName, currWord, currMax = "";
Работа с одним массивом C++
подскажите как сделать так, чтобы постоянно работать с исходным массивом)вот допустим есть исходный массив, одна функция изменяет один элемент массива и выводит массив на экран, а потом вызывается след функция которая должна работать с исходным массивом а не с измененным)как это сделать, что то недогоняю)
C++ Из C# на C++ http://www.cyberforum.ru/cpp-beginners/thread917526.html
Помогите, ппожалуйста, перевести из C# на C++ public class graph { public int matr_smeznosti; public int kol_vershn; // количество вершин графа // конструктор, считывающий граф из файла public graph(string fileName) { int n, j; string line;
C++ Сортировка 2-ух массивов #include "stdafx.h" #include <iostream> using namespace std; int main( int argc, char** argv ) { const int n=5; const int m=5; подробнее

Показать сообщение отдельно
salam
159 / 140 / 12
Регистрация: 10.07.2012
Сообщений: 715
04.07.2013, 20:00     графы. поиск в глубину
не люблю я очень эти методички... прошу прощения. давайте подумаем. цикл можно найти так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int graph[SIZE][SIZE]; // матрица смежности
int color[SIZE];            // color[i] может принимать одно из трех значений {0, 1, 2}
                                 // 0 - вершина не была посещена,
                                 // 1 - мы зашли в нее, но еще не вышли,
                                 // 2 - мы уже вышли из этой вершины.
void dfs(int v) {
   color[v] = 1;                  // мы зашли в вершину v
   for(int i=0; i < SIZE; i++)
      if(i != v && graph[v][i] == true)
         if(color[i] == 1) {      // мы нашли цикл, так как пытаемся пойти из вершины 
                                      // с цветом 1 в вершину с цветом 1, то есть 
         }                           // в вершину, из которой еще не вышли
         else if(color[i] == 0)
                  dfs(i);
   color[v] = 2;
}
дальше можете делать с этим циклом, что угодно.

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

Добавлено через 2 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int graph[SIZE][SIZE]; // матрица смежности
int par[SIZE];               // массив предков 
int color[SIZE];            // color[i] может принимать одно из трех значений {0, 1, 2}
                                 // 0 - вершина не была посещена,
                                 // 1 - мы зашли в нее, но еще не вышли,
                                 // 2 - мы уже вышли из этой вершины.
void dfs(int v) {
   color[v] = 1;                  // мы зашли в вершину v
   for(int i=0; i < SIZE; i++)
      if(i != v && graph[v][i] == true)
         if(color[i] == 1) {      // мы нашли цикл, так как пытаемся пойти из вершины 
                                      // с цветом 1 в вершину с цветом 1, то есть 
         }                           // в вершину, из которой еще не вышли
         else if(color[i] == 0) {
                  par[i] = v;   // мы называем вершину v предком вершины i, 
                                   // так как обход в глубину попал в i именно из v
                  dfs(i);
         }
   color[v] = 2;
}
Добавлено через 1 минуту
надеюсь, вам это все поможет.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru