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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Поменять в матрице 1-й столбец со 2-ым, 3-й с 4-м и т.д. http://www.cyberforum.ru/cpp-beginners/thread876393.html
Здравствуйте, великие умы!!! Прошу вас помочь мне начинающему "программисту" разобраться в задачке (С++)!!! "Программа должна запрашивать размеры матрицы и самостоятельно заполнять ее с помощью генератора случайных чисел. Верхняя граница для значения элементов матрицы также вводится с клавиатуры. Дана целочисленная квадратная матрица. 1) Поменять в ней 1-й столбец со 2-ым, 3-й с 4-м и...
C++ Описать процедуру или функцию, которая находит max элемент не пустого списка L Задание: описать процедуру или функцию, которая находит max элемент не пустого списка L (инф. часть списка содержит real) P.S.: Помогите пожалуйста, заранее благодарю :bravo: http://www.cyberforum.ru/cpp-beginners/thread876392.html
C++ Общий вид интерполированной функции двух переменных
Добрый вечер, киберфорум. Не так давно меня озадачили следующей темой: Билинейная интерполяция функции двух переменных. Сама по себе задача не сложная, если бы делал это я в каком-нибудь маткаде: по набору точек строю интерполированную функцию и отображаю её график, но на с++ все куда сложнее. К сути проблемы. В результате интерполяции, например, полиномом Лагранжа, как тут, я получу...
C++ В квадратной матрице найти сумму модулей элементов в строках, содержащих хотя бы один отрицательный элемент; определить номер 1ой строки с 0-ым элем-о
Дана целочисленная квадратная матрица. 1) Найти сумму модулей элементов в строках, содержащих хотя бы один отрицательный элемент. 2) Определить номер первой строки, содержащей нулевой элемент. Мой вариант: int mat ; int sum = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
C++ Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. http://www.cyberforum.ru/cpp-beginners/thread876365.html
Помоги написать программу по графам плиз Найти все вершины графа, к которым существует путь заданной длины (не обязательно кратчайший) от вершины, номер которой вводится с клавиатуры. Веса дуг вводятся с клавиатуры. написал код программы, а он что то не работает #include <conio.h> #include <iostream> using namespace std;
C++ Вычислить и вывести на экран значение функции F(x) на отрезке [a,b] с шагом h=0.1 с точностью ε. #include <iostream> #include <cmath> #include <iomanip> using namespace std; float fun(float x, float e, int &n) { float s=0, p=1, a=1, q=1, y=1, z=4; n=0; подробнее

Показать сообщение отдельно
Skreen
0 / 0 / 0
Регистрация: 16.03.2011
Сообщений: 52

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

23.05.2013, 21:58. Просмотров 945. Ответов 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; 
  }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 05:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru