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

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

Войти
Регистрация
Восстановить пароль
 
Skreen
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 52
#1

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

23.05.2013, 21:58. Просмотров 1029. Ответов 0
Метки нет (Все метки)

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

вот алгоритм:
Сначала строится остов связного графа 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; 
  }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 21:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос базисные циклы в графе. остова найдены! (C++):

Как найти все циклы в неориентированном графе по ребрам? - C++
Как найти все циклы в неориентированном графе по ребрам?

Идентификаторы: createHanningWindow и phaseCorrelate не найдены - C++
Пытался скомпилировать демку #include &quot;opencv2/core/core.hpp&quot; #include &quot;opencv2/highgui/highgui.hpp&quot; #include...

Cygwin и NetBeans - В системе подходящие компиляторы не найдены - C++
Скачал cygwin и netbeans c++. Теперь пытаюсь настроить. Собственно выполняю эти действия, cygwin стал отзываться в консоли после...

Заменить в коде циклы for на циклы while - C++
int i, j, n; bool a; cin &gt;&gt; i &gt;&gt; n; for (i; i&lt;n; i++) { a = true; for (j = 2; j &lt;= i / 2; j++) if ((i%j) == 0) a =...

Найти базисные векторы системы и выразить остальные векторы через базисные - Алгебра
Привет всем. Задание такое: найти базисные векторы системы и выразить остальные векторы через базисные. Вот векторы-строки: 12, 5, 0 ...

Найти циклы в графе - Дискретная математика
Приветствую! Я не силён в графах, поэтому надеюсь на Вас.. Имеется граф(см рисунок), в котором нужно найти циклы(они пронумерованы...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2013, 21:58
Привет! Вот еще темы с ответами:

Простые циклы в графе - Алгоритмы
Добрый день. Необходимо написать программу, осуществляющую поиск максимального количества простых, нигде не пересекающихся циклов графа....

Найти все циклы в графе - C (СИ)
Я обгуглился, но найти не смог. В общем, дан граф, задан списком смежности. Нужно найти все циклы, и, если таких циклов несколько, и они...

Найти все циклы в неориентированном графе по матрице смежности - Алгоритмы
Здравствуйте. Задача в заголовке. С построением матрицы смежности проблем нет, вопрос в алгоритме нахождения циклов по этой матрице. ...

С++ превращение консольной в CLR. Нахождение минимального остова графа - C++/CLI
нахождение минимального остова графа по алгоритму Прима. int a,b,u,v,n,i,j,ne=1; int visited={0},min,mincost=0,cost; int...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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