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

Графы - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ В чём ошибка? http://www.cyberforum.ru/cpp-beginners/thread156530.html
Начал писать класс: class TGame{ public: TGame(char *WorldFileName, char *TexturesFileName); void Render(); private: TPrimitives World; TTextures Textures; TTexturesData TexturesData; ...
C++ Метод наследника? Я не очень силен в наследовании в С++... Пусть у меня есть класс наследника и есть метод такой же как и у родителя... Как мне сначала выполнить в этом методе то, что у родителя, а затем у... http://www.cyberforum.ru/cpp-beginners/thread156526.html
C++ Перегрузка оператора ++ , деструктор и конструктор копий
Привет всем! В продолжение Этой темы появились новые вопросы и непонятки. Буду признателен за советы и разъяснения ;) Начну с самого начала... Пишу class - обертку для файла. Цель -...
Объект string! C++
Нужно чтобы при вводе имени файла(даже с пробелами), или вообще других данных, они заносились в объект типа string! C помощью каких функций или операторов можно это сделать? Потому что если это...
C++ Ввод массива http://www.cyberforum.ru/cpp-beginners/thread156508.html
Помогите пожалуйста с вводом массива неизвестного размера. например мне надо ввести набор чисел 186146. И вывести. Пробовал sizeof, не получается
C++ Вопросы насчёт быстрой сортировки Здравствуйте. Объясните, пожалуйста. Есть алгоритм быстрой сортировки: Код: int shag=1; void quickSort(int arr, int left, int right, char v) { cout <<"--------" <<shag... подробнее

Показать сообщение отдельно
AKE
11 / 11 / 0
Регистрация: 09.05.2010
Сообщений: 384
30.07.2010, 20:00
Таких путей может быть несколько...Нужно рекурсивно сканировать из одной точки граф, обозревая соседние клетки до нахождения второй точки, сохраняя путь...
Вот примерный код из моей лабы, граф задаётся матрицей смежности:
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
struct QItem
{
  int node;
  int prev;
  char Path[50];
};
 
void QAdd(QItem *Q, int &R, char *Path, int node, int prev)
{
  Q[++R].node = node;
  Q[R].prev = prev;
  strcpy(Q[R].Path, Path);
}
 
QItem QGet(QItem *Q, int &L)
{
  return Q[L++];
}
 
void AddPath(char PPath[50][50], int &PPathP, char Path[])
{
  strcpy(PPath[++PPathP], Path);
}
void GetPath(int arr[], int levels[], int x, int y)
{
 //î÷åðåäü
 QItem Q[700];
 int L = 0;
 int R = -1;
 
 char PPath[50][50];// ñïèñîê âûâåäåГ*Г*ûõ ГЇГіГІГҐГ©
 int PPathP = -1; // ГіГЄГ*Г§Г*òåëü Г*Г* âåðøèГ*Гі Г±ГЇГЁГ±ГЄГ*
 
 char Pc[50];    //ГЎГіГґГҐГ° ñòðîêГ* äëÿ õðГ*Г*ГҐГ*ГЁГї
 QItem QI;
 
 levels[x] = 0;
 sprintf(Pc, "%d", x); //ñîçäГ*Г*ГЁГҐ ñòðîêè äëÿ êîðГ*Гї
 QAdd(Q, R, Pc, x, x);//äîáГ*âëåГ*ГЁГҐ êîðГ*Гї Гў î÷åðåäü
 for (int j = 0; j < 30; j++) //öèêë äëÿ äîñòГ*òî÷Г*îãî Г·ГЁГ±Г«Г* ГЁГІГҐГ°Г*öèé
 {
   if (L > R) return;  // åñëè î÷åðåäü ГЇГіГ±ГІГ* - âûéòè
   QI = QGet(Q, L);    // áåð¸ì 1-ûé ýëåìåГ*ГІ ГЁГ§ î÷åðåäè
   int node = QI.node; // Г‚ node ïîìåùГ*ГҐГ¬ Г*îìåð ГІГҐГЄГіГ№ГҐГЈГ® óçëГ*
   for (int i = 0; i < 10; i++) //ïðîâåðêГ* ГўГ±ГҐГµ ñìåæГ*ûõ óçëîâ
    {
      if ((i == node) || (QI.prev == i) || (i == x)) continue;//åñëè óçåë i ñîâïГ*Г¤Г*ГҐГІ Г± node
                                            //èëè ïðåäûäóùèé ГЄ node ñîâïГ*Г¤Г*ГҐГІ Г± 
                                       //i ГІГ® ïðåêðГ*ГІГЁГІГј ГІГҐГЄГіГ№ГіГѕ ГЁГІГҐГ°Г*öèþ.
      if (getItem(arr, node, i)) //åñëè Г±ГіГ№ГҐГ±ГІГўГіГҐГІ ðåáðî (node; i)
      {
        sprintf(Pc, "%s%d", QI.Path, i);
        if (levels[i] == -1) 
        {
          levels[i] = levels[node] + 1;       
          if (!IfPathPresent(PPath, PPathP, Pc))
          { 
            if (i==y)
            cout<<Pc<<'\n';
            AddPath(PPath, PPathP, Pc);
          } 
        } else
        {
          if (levels[i] == (levels[node]+1))
          {
            if (!IfPathPresent(PPath, PPathP, Pc))
            {
              if (i==y)
              cout<<Pc<<'\n';
              AddPath(PPath, PPathP, Pc);
            }
          }
        }
        QAdd(Q, R, Pc, i, node);
      }
   }
 }
}
 
void GetPathAll(int arr[], int x, int y)
{
 cout<<'\n';
 int levels[10];
 FillLevels(levels);
 GetPath(arr, levels, x, y);
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru