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

базисные циклы в графе. остова найдены! - C++

Восстановить пароль Регистрация
 
Skreen
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 52
23.05.2013, 21:58     базисные циклы в графе. остова найдены! #1
сделал программу для подсчета остовов в графе, но как реализовать нахождение базисных циклов, я не знаю...уже все перепробывал.

вот алгоритм:
Сначала строится остов связного графа G=(V,E) с перенумерованными ребрами, а затем базис циклов.


Алгоритм построения остова.

1. Выбрать первое ребро и занести в список.
2. Выбрать следующее по номеру ребро.
3. Если выбранное ребро образует цикл с какими-либо из ранее занесенных в список, то переходим к п.4, если это не так, то к п.5.
4. Если номер выбранного ребра меньше |E|, то переходим к п.2, если нет, то к п.6.
5. Занести ребро в список. Перейти к п.4
6. Вывести список ребер.


Алгоритм построения базиса циклов произвольного графа.

1. Выделить связные компоненты.
2. В каждой компоненте связности выделить остов и построить базис циклов.
3. Объединить полученные базисы.

вот код нахождения остовов:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// ConsoleApplicationOstov1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <windows.h>
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef struct L *Lref; // Тип: указатель на заголовочный узел.
typedef struct T *Tref; // Тип: указатель на дуговой узел.
 
using namespace std;
//Описание типа заголовочного узла.
typedef struct L 
{ 
  int Key; //Имя заголовочного узла.
  int Count; //Количество предшественников.
  Boolean Flag; //Флаг посещения узла при обходе.
  Tref Trail; //Указатель на список смежности.
  Lref Next; //Указатель на следующий узел в списке заголовочных узлов.
} Leader;
 
//Описание типа дугового узла.
typedef struct T 
{ 
  Lref Id; 
  Tref Next; 
} Trailer;
 
//Описание типа узла стека.
typedef Tref TipElement;
typedef struct Zveno *svqz;
typedef struct Zveno 
{ 
  TipElement Element; //Указатель на список смежности.
  svqz Sled; 
} St;
 
class Spisok
{
  private:
    Lref Head; //Указатель на голову списка заголовочных узлов.
    Lref Tail; //Указатель на фиктивный элемент 
               // в конце списка заголовочных узлов.
    void SearchGraph (int, Lref *);
  public:
    Spisok() {//Инициализация списка заголовочных узлов.
              Head = Tail =  new (Leader); }
    Lref GetHead() { return Head; }
    Lref GetTail() { return Tail; }
    void MakeGraph ();
    void Ostov_Depth (Lref);
    void PrintGraph ();
};
 
void main ()
{
  setlocale(LC_ALL, "Russian");
  Spisok A;
  Lref t; //Рабочий указатель для перемещения 
          // по списку заголовочных звеньев.
  //Построение графа и вывод его структуры Вирта.
  A.MakeGraph ();
  A.PrintGraph (); cout<<endl;
  //Построение стягивающего дерева (остова).
  cout<<"Остов: ";
  t = A.GetHead();
  while (t!=A.GetTail())
    { (*t).Flag = TRUE; t = (*t).Next; }
  A.Ostov_Depth (A.GetHead()); cout<<endl;
} 
 
void Spisok::SearchGraph (int w, Lref *h)
//Функция возвращает указатель на заголовочный узел 
//с ключом w в графе, заданном структурой Вирта с указателем Head. 
{
  *h = Head; (*Tail).Key = w;
  while ((**h).Key!=w) *h = (**h).Next;
  if (*h==Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
  { Tail = new (Leader); (**h).Count = 0; 
    (**h).Trail = NULL; (**h).Next = Tail; }
}
 
void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  setlocale(LC_ALL, "Russian");
  int x,y;
  Lref p,q; //Рабочие указатели.
  Tref t,r; //Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.
  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
     cout<<"Вводите конечную вершину дуги: "; cin>>y;
     //Определим, существует ли в графе дуга (x,y)?
     SearchGraph (x, &p); SearchGraph (y,&q);
     r = (*p).Trail; Res = FALSE; 
     while ((r!=NULL)&&(!Res)) 
       if ((*r).Id==q) Res = TRUE; 
       else r = (*r).Next; 
     if (!Res) //Если дуга отсутствует, то поместим её в граф.
      { t = new (Trailer); (*t).Id = q; 
        (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } 
     cout<<"Вводите начальную вершину дуги: "; cin>>x;
  }
}
 
void Spisok::PrintGraph ()
//Вывод структуры Вирта, заданной указателем 
//Head и соответствующей ориентированному графу.
{
  Lref p; //Рабочий указатель.
  Tref q; //Рабочий указатель.
 
  p = Head;
  while (p!=Tail)
  {
     cout<<"("<<(*p).Key; q = (*p).Trail; 
     while (q!=NULL) 
      { cout<<(*(*q).Id).Key; q = (*q).Next; } 
     cout<<")"; p = (*p).Next; cout<<" ";
  }
}
 
void Spisok::Ostov_Depth (Lref r)
//Рекурсивный обход графа в глубину, соединенный с
//нахождением ребра остовного дерева.
//r - указатель на структуру Вирта.
{
  Tref t;
  Lref s;
 
  s = r;
  t = (*r).Trail; (*r).Flag = FALSE;
  while (t!=NULL)
  { if ((*(*t).Id).Flag) 
    { cout << "(" << s->Key << "," << t->Id->Key << ") ";
      Ostov_Depth ((*t).Id);
    }
    t = (*t).Next; 
  }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 21:58     базисные циклы в графе. остова найдены!
Посмотрите здесь:

C++ поиск циклов в графе
Поиск на графе C++
К-ый путь в графе(ДП) C++
Посчитать кол-во элементов между максимальным и минимальным значением элементов двумерного массива( подразумевается, что эти значения уже найдены) C++
Расстояние на графе C++
Cygwin и NetBeans - В системе подходящие компиляторы не найдены C++
C++ Идентификаторы: createHanningWindow и phaseCorrelate не найдены
Пути на графе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 02:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru