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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Xensis
5 / 5 / 0
Регистрация: 15.07.2010
Сообщений: 57
#1

Графы - C++

30.07.2010, 15:39. Просмотров 487. Ответов 1
Метки нет (Все метки)

Задана система односторонних дорог(вбивается рандомно или вручную). Найти два города и соединяющий их путь, который проходит через каждую из дорог системы только один раз.
помогите плиз, не могу понять с чего подойти.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2010, 15:39     Графы
Посмотрите здесь:

графы - C++
в ближайшие несколько дней нужна программа и блок-схема перевода матрицы инцидентности в список ребер на С++ , с языком почти не знаком.

Графы - C++
Имеется сеть автомобильных дорог. Известны расстояния всех участков дорог. Некоторые участки аварийноопасны. Требуется найти путь из пункта...

С++ и графы - C++
Доброго времени суток. Хотел бы попросить помощи в написании программы. Нужно создать программу которая будет проводить расчет сетевого...

Графы - C++
Граф задан своей матрицей смежностей. Вывести на экран все связные вершины...очень скоро нужно...извините за срочность

[C++] графы - C++
Алгоритм фронт фолны в графе Помогите.. Дана матрица Ag (Матрица смежности графа) И координаты начальной вершины i,j и кординаты...

Графы - C++
Дано прямоугольное клеточное поле; как создать матрицу смежности для графа ферзей?

Графы - C++
Помогите пожалуйста решить одну задачку. Буду очень благодарен! Спасибо заранее, огромное! Задана строка s. За один ход можно поменять...

Графы - C++
Прочитал про обход графа в глубину, посмотрел реализацию, и тут вопрос а как можно использовать этот обход в глубину?

Графы - C++
Люди скиньте пожалуйста какую нибудь программку на С++ по графам, или дайте ссылку на темку на форему...

Графы - C++
Суть задачи: дан ориентированный граф, у которого каждая вершина (не ребро) имеет вес. Нужно найти путь из любой точки в любую, но чтобы он...

графы - C++
помогите пожалуйста написать программу! Составить программу печати всех циклов ориентированного графа Добавлено через 2 часа 21...

Графы - C++
1) Построить граф, используя язык С++ (или Си), согласно данной схеме на рис.1. 2) По запросу пользователя должны удаляться: • все...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AKE
11 / 11 / 0
Регистрация: 09.05.2010
Сообщений: 384
30.07.2010, 20:00     Графы #2
Таких путей может быть несколько...Нужно рекурсивно сканировать из одной точки граф, обозревая соседние клетки до нахождения второй точки, сохраняя путь...
Вот примерный код из моей лабы, граф задаётся матрицей смежности:
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);
}
Yandex
Объявления
30.07.2010, 20:00     Графы
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru