Дискретная математика

@ForEveR · Регистрация: 24.06.2010

Студворк — интернет-сервис помощи студентам

Есть три программы по дискретной математике. Выложу сюда. Может кому-то пригодиться. До конца семестра думаю будет еще 1-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
//Graph.h
#ifndef _GRAPH_H_
#define _GRAPH_H_
 
#include <vector>
 
class Graph
{
public:
   Graph(){}
   virtual ~Graph(){}
   void SetSize(int size_);
   const int GetSize() const {return size;} 
   virtual void Input()=0;
   void Output();
   void Resize();
protected:
   std::vector<std::vector<int> > VecGraph;
   int size;
};
 
class OrGraph:public Graph
{
public:
   OrGraph(){}
   ~OrGraph(){}
   void Input();
};
 
class UnOrGraph:public Graph
{
public:
   UnOrGraph(){}
   ~UnOrGraph(){}
   void Input();
};
 
#endif

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
//Graph.cpp
#include "Graph.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
//Functions for abstract Graph
void Graph::SetSize(int size_)
{
   size=size_;
   Resize();
}
 
void Graph::Output()
{
   for(int i=0; i<size; ++i)
   {
      std::copy(VecGraph[i].begin(), VecGraph[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         if(VecGraph[i][j]==1)
            std::cout<<i+1<<" node is connected with "<< j+1 <<" node.\n";
      }
   }
}
 
void Graph::Resize()
{
   VecGraph.resize(size);
   for(int i=0; i<size; ++i)
      VecGraph[i].resize(size);
}
 
//Functions for UnOrGraph
void UnOrGraph::Input()
{  
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         if(i>j)
            continue;
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node: ";
         std::cin>>VecGraph[i][j];
         if(i!=j)
            VecGraph[j][i]=VecGraph[i][j];
      }
   }
}
 
//Functions for OrGraph
void OrGraph::Input()
{
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node: ";
         std::cin>>VecGraph[i][j];
      }
   }
}

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
//Main.cpp
#include <iostream>
#include <stdexcept>
 
#include "Graph.h"
 
int main()
{
   try
   {
      int size=0;
      int state=0;
   
      Graph*pOb;
 
      std::cout<<"Enter numb of nodes: ";
      std::cin>>size;
 
      if(size<0)
         throw "Numb of nodes can`t be less then zero. End of program\n";
      else if(size==0)
      {
         std::cout<<"It is empty graph\n";
         return 0;
      }
 
      std::cout<<"Enter 1 for unor graph and 2 for or graph: ";
      std::cin>>state;
 
      if((state!=1)&&(state!=2))
      {
         throw "You can only input 1 for unor graph or two for or graph. End of program\n";
      }
 
      if(state==2)
         pOb=new OrGraph;
      else if(state==1)
         pOb=new UnOrGraph;
   
      pOb->SetSize(size);
      pOb->Input();
      pOb->Output();
   }
   
   catch(char*str)
   {
      std::cerr<<str;
      return EXIT_FAILURE;
   }
 
   system("pause");
   return 0;
}

Добавлено через 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
//Matrix_adj.h
#ifndef _MATRIX_ADJ_H_
#define _MATRIX_ADJ_H_
 
#include <vector>
 
class AdjMatr
{
public:
   AdjMatr()
   {
      VecAdj.resize(0);
      VecPath.resize(0);
   }
   ~AdjMatr(){}
   void input();
   void output(const std::vector<std::vector<int> >& Vec);
   void resize(size_t size);
   void find_path();
   void copy_matr();
   size_t set_size();
private:
   std::vector<std::vector<int> > VecAdj;
   std::vector<std::vector<int> > VecPath;
};
 
#endif /*ifndef Matrix_adj*/

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
//Matrix_adj.cpp
#include "Matrix_adj.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
void AdjMatr::resize(size_t size)
{
   VecAdj.resize(size);
   for(size_t i=0; i<size; ++i)
      VecAdj[i].resize(size);
}
 
void AdjMatr::copy_matr()
{
   VecPath.resize(VecAdj.size());
   for(size_t i=0; i!=VecAdj.size(); i++)
   {
      VecPath[i].resize(VecAdj[i].size());
      std::copy(VecAdj[i].begin(), VecAdj[i].end(), VecPath[i].begin());
   }
}
 
void AdjMatr::input()
{
   size_t size=set_size();
   resize(size);
   for(size_t i=0; i<size; ++i)
   {
      for(size_t j=0; j<size; ++j)
      {
         if(i==j)
         {
            VecAdj[i][j]=0;
            continue;
         }
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node and 0 for not\n";
         std::cin>>VecAdj[i][j];
      }
   }
   std::cout<<"Initial adj matrix\n";
   output(VecAdj);
}
 
size_t AdjMatr::set_size()
{
   size_t size;
   std::cout<<"Enter size: ";
   std::cin>>size;
   return size;
}
 
void AdjMatr::output(const std::vector<std::vector<int> >& Vec)
{
   for(size_t i=0; i<Vec.size(); ++i)
   {
      std::copy(Vec[i].begin(), Vec[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
}
 
void AdjMatr::find_path()
{
   copy_matr();
   std::cout<<"Initial path matrix\n";
   output(VecPath);
   for(size_t k=0; k<VecPath.size(); ++k)
   {
      for(size_t i=0; i<VecPath.size(); ++i)
      {
         if(VecPath[i][k]==1)
         {
            for(size_t j=0; j<VecPath.size(); ++j)
            {
               VecPath[i][j]=(VecPath[i][j]||VecPath[k][j]);
            }
         }
      }
   }
   std::cout<<"Path matrix\n";
   output(VecPath);
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Main.cpp
#include "Matrix_adj.h"
 
#include <iostream>
 
int main()
{
   AdjMatr Ob;
   Ob.input();
   Ob.find_path();
   system("pause");
   return 0;
}

Добавлено через 5 минут

Код прюфера. Кодирование/декодирование дерева. Много комментов.

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
//Prufer.h
#ifndef _PRUFER_H_//Страж включения
#define _PRUFER_H_//
 
#include <vector>//Для использования std::vector
#include <iostream>//Для использования потоков ввода/вывода/ошибки
 
class AbstractMatr//Класс-контейнер матрица
{
public:
    AbstractMatr() {}//Конструктор без параметров
    AbstractMatr(size_t n, size_t m);//Конструктор с параметрами размеров
    AbstractMatr(const AbstractMatr&Ob):Matrix(Ob.Matrix) {}//Конструктор копирования. Копируем один вектор в другой
    virtual ~AbstractMatr() {}//Виртуальный деструктор
    void SetSize(size_t n, size_t m);//Функция установки размера
    inline const size_t GetRow() const {return Matrix.size();}//Получение кол-ва строк в векторе
    inline const size_t GetCol() const {return Matrix[0].size();}//Получение кол-ва столбцов в векторе
    void swap(AbstractMatr&);//Меняем местами значения двух объектов.
protected:
    std::vector<std::vector<int> > Matrix;//Вектор векторов типа int. Исходная матрица смежности
};
 
class Prufer:public AbstractMatr//Открытое наследование
{
public:
    Prufer():AbstractMatr() {}//Конструктор без параметров, вызывающий конструктор AbstractMatr()
    Prufer(size_t n, size_t m):AbstractMatr(n, m) {}//Конструктор с параметрами размера, вызывающий констр. AbstractMatr
    Prufer(const AbstractMatr& Ob):AbstractMatr(Ob) {}//Конструктор копирования, вызывающий констр. AbstractMatr
    friend std::ostream& operator <<(std::ostream&, const Prufer&);//Перегрузка оператора вывода в поток
    friend std::istream& operator >>(std::istream&, Prufer&);//Перегрузка оператора ввода в поток
    void Code();//Функция кодирования
    void Decode();//Функция декодирования
    int Degree(int row);//Функция вычисления степени вершины
    int Adjacent(int row);//Функция получения единственной смежной вершины с данной
    bool IsMin(int elem);//Функция проверки на минимальный элемент
    void DeleteEdge(int row, int col);//Функция удаления ребра
    bool IsInPruf(int elem);//Функция проверки на присутствие в коде Прюфера
    bool IsMinNode(int elem, int row);//Функция проверки на минимальный элемент. Для Decode
private:
    std::vector<int> Pruf;//Вектор типа int. Код Прюфера
    std::vector<int> Nodes;//Вектор типа int. Вершины
    std::vector<std::pair<int, int> > Edges;//Вектор типа пары двух интовых значений. Ребра
    std::vector<int> Degrees;//Вектор типа int. Степени
};
 
#endif//

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
//Prufer.cpp
#include <vector>
#include <algorithm>//Использование стандартных алгоритмов
#include <iostream>
#include <functional>//Использование функторов
#include <stdexcept>//Использование стандартных классов исключений
 
#include "Prufer.h"
 
AbstractMatr::AbstractMatr(size_t n, size_t m)
{
    Matrix.resize(n);//Установка размера исходной матрицы
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);//Установка размера строки исходной матрицы
    }
}
 
void AbstractMatr::SetSize(size_t n, size_t m)
{
    if(GetRow()!=0&&GetCol()!=0)//Если столбцы/строки не равны нулю
        Matrix.clear();//Чистим вектор
    Matrix.resize(n);
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);
    }
}
 
void AbstractMatr::swap(AbstractMatr& Ob)
{
    Matrix.swap(Ob.Matrix);//Меняем местами значения вектора
}
 
void Prufer::Code()
{
    for(int i=0; i!=GetRow(); ++i)
        Nodes.push_back(i+1);//Записываем в вершины элемент i+1
    for(int i=0; i!=GetRow(); ++i)
        Degrees.push_back(Degree(Nodes[i]-1));//Записываем в степени степень i элемента вектора Nodes - 1
    for(int t=0; t!=GetRow()-2; ++t)//От 0 до N-2
    {
        //Проверка на то, что наличие листьев
        if(std::count_if(Degrees.begin(), Degrees.end(), std::bind2nd(std::equal_to<int>(), 1))==0)
        {
            std::cout<<"On "<< t+1 <<" step\n";//Пишем на каком шаге
            //Кидаем исключение, которое будет обработано в main(). Используем стандартный класс
            //std::invalid_argument
            throw std::invalid_argument("Can`t code this graph (tree). There are no nodes with degree 1\n");
        }
        for(int i=0; i!=Nodes.size(); ++i)//От 0 до размера вектора вершин
        {
            if(Degrees[i]==1)//Если i-ая вершина - лист
            {
                if(IsMin(Nodes[i]))//Если i-ая вершина минимальна
                {
                    int Adj=Adjacent(Nodes[i]-1);//Возвращаем смежную с i-1 вершиной вершину
                    Pruf.push_back(Adj+1);//Добавляем в вектор кода Прюфера, смежную вершину+1
                    DeleteEdge(Nodes[i]-1, Adj);//Удаляем ребро Nodes[i]-1, Adj
                    //Удаляем из вектора вершин i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Degrees.clear();//Очищаем вектор степеней
                    for(int i=0; i!=Nodes.size(); ++i)
                    {
                        Degrees.push_back(Degree(Nodes[i]-1));//Заполняем вектор степеней
                    }
                    break;//Брякаем цикл
                }
            }
        }
    }
    Edges.push_back(std::make_pair<int, int>(Nodes[0], Nodes[1]));//Записываем ребро Nodes[0]->Nodes[1] в вектор ребер
    std::cout<<"Prufer`s code\n";//Вывод в консоль строки
    std::copy(Pruf.begin(), Pruf.end(), std::ostream_iterator<int>(std::cout, " "));//Вывод в консоль вектора
    std::cout<<std::endl;//Перевод каретки+очистка буфера
}
 
void Prufer::Decode()
{
    std::pair<int, int> Temp;//Создаем временный элемент типа пары двух интовых значений
    Temp=Edges.front();//Записываем первый элемент из вектора ребер во временный элемент
    Edges.clear();//Чистим вектор ребер
    Nodes.clear();//Чистим вектор вершин
    for(int i=0; i!=Matrix.size(); ++i)
        Nodes.push_back(i+1);//Записываем i+1 вершину (дабы начиналось с 1)
    for(int t=0; t!=GetRow()-2; ++t)//До N-2
    {
        for(int i=0; i!=Nodes.size(); ++i)
        {
            if(!IsInPruf(Nodes[i]))//Если не i-тая вершина не выходит в код прюфера
            {
                if(IsMinNode(Nodes[i], i))//И если она минимальная среди вершин
                {
                    //Делаем пару интовых значений. Первый элемент вектора Прюфера и i-тую вершину.
                    //Записываем ее в вектор ребер
                    Edges.push_back(std::make_pair<int, int>(Pruf[0], Nodes[i]));
                    //Удаляем i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Pruf.erase(std::find(Pruf.begin(), Pruf.end(), Pruf[0]));//Удаляем первый элемент из в. Прюфера
                    break;//Брякаем
                }
            }
        }
    }
    Edges.push_back(Temp);//Записываем в конец вектора значение, записанное во временной переменной
    std::cout<<"Decode from Prufers`s code\nDefault tree\n";//Вывод строки
    //Цикл по итератору. От начала вектора ребер, до конца.
    for(std::vector<std::pair<int, int> >::const_iterator Iter=Edges.begin(); Iter!=Edges.end(); ++Iter)
    {
        std::cout<<"<"<<Iter->first<<','<<Iter->second<<'>'<<'\n';//Выводим в консоль <вершина из прюфера, вершина из nodes>
    }
}
 
int Prufer::Degree(int row)
{
    int cnt=0;//Счетчик
    for(int j=0; j!=GetCol(); ++j)//До кол-ва столбцов
    {
        if(Matrix[row][j]==1)//Если j-ый элемент строки row равен 1
            cnt++;//Плюсуем счетчик
    }
    return cnt;
}
 
int Prufer::Adjacent(int row)
{
    int i;
    for(i=0; i!=GetCol(); ++i)
        if(Matrix[row][i]==1)//Если i-ый элемент строки row равен 1
            break;//Брякаем
    return i;//Вернули i
}
 
bool Prufer::IsMin(int elem)
{
    int min=elem;//min=elem
    for(int i=0; i!=Degrees.size(); ++i)
    {
        if(Degrees[i]==1)//Если i-ая степень=1 
        {
            if(Nodes[i]<min)//Если i-ая вершина меньше минимума
                min=Nodes[i];//Минимум становится равен i-ой вершине
        }
    }
    return (min==elem);//Если min==elem возвращаем true, иначе false
}
 
void Prufer::DeleteEdge(int row, int col)
{
    Matrix[row][col]=0;//col-тый элемент в row-той строке равен 0
    Matrix[col][row]=0;//наоборот
}
 
std::ostream& operator <<(std::ostream& os, const Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        //Вывод на экран. Стандартный алгоритм copy
        std::copy(Ob.Matrix[i].begin(), Ob.Matrix[i].end(), std::ostream_iterator<int>(os, " "));
        os<<'\n';
    }
    return os;
}
 
std::istream& operator >>(std::istream& is, Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        for(int j=0; j!=Ob.GetCol(); ++j)
        {
            if(i>=j)//Если i>=j переходим к след итерации
                continue;
            std::cout<<"Enter 1 for connect "<< i+1 <<" and "<< j+1 <<" nodes, and 0 for not\n";
            is>>Ob.Matrix[i][j];
            if(i!=j)//Если i!=j
                Ob.Matrix[j][i]=Ob.Matrix[i][j];//
        }
    }
    return is;
}
 
bool Prufer::IsInPruf(int elem)
{
    for(int i=0; i!=Pruf.size(); ++i)
    {
        if(elem==Pruf[i])//Если элемент = Pruf[i]
        {
            return true;//Вернули true. То есть элемент присутствует в Прюфере
        }
    }
    return false;//Вернули false. Элемента нет. Все гуд
}
 
bool Prufer::IsMinNode(int elem, int row)
{
    int min=elem;//Минимум = элемент
    for(int i=row; i!=Nodes.size(); ++i)//От номера элемента в массиве до конца
    {
        if(Nodes[i]<min)
            min=Nodes[i];
    }
    return (min==elem);
}

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
//Main.cpp
#include <iostream>
 
#include "Prufer.h"
 
int main()
{
    Prufer Ob;//Создали объект
    int N;
    std::cout<<"Enter N: ";
    std::cin>>N;//Ввели размер
    Ob.SetSize(N, N);//Установили размер для квадратной матрицы
    std::cout<<"Enter matrix\n";
    std::cin>>Ob;//Ввели матрицу
    std::cout<<"Initial matrix\n";
    std::cout<<Ob;//Вывели матрицу
    try//Блок try, catch
    {
        Ob.Code();//Вызвали кодирование. Если в функции кинулось исключение - перешли в блок catch
        Ob.Decode();//Если нет - декодируем дерево
    }
    catch(const std::invalid_argument& e)//Ловим исключение типа const std::invalid_argument&
    {
        std::cout<<e.what()<<'\n';//what - функция класса invalid_argument.
    }
    system("pause");//Для release версии
    return 0;
}

@ForEveR · 12.11.2010, 23:49 **[ТС]**

Алгоритм Флойда-Уоршала. Поиск матрицы кратчайших путей. Матрица вершин через которые проходят кратчайшие пути. Поиск кратчайшего пути между двумя вершинами.

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//Floyd.h
#ifndef _FLOYD_H_
#define _FLOYD_H_
 
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
 
typedef std::vector<std::vector<int> > VM;
typedef std::stack<int> ST;
 
class MatrixAdj
{
public:
    MatrixAdj()
    {
    }
 
    virtual ~MatrixAdj()
    {
    }
 
    void SetSize(const size_t n)
    {
        Matr.resize(n);
        for(size_t i=0; i<n; ++i)
            Matr[i].resize(n);
    }
 
    void Fill()
    {
        for(size_t i=0; i<Matr.size(); ++i)
        {
            for(size_t j=0; j<Matr.size(); ++j)
            {
                if(i==j)
                    Matr[i][j]=0;
                else if(i>j)
                {
                    Matr[i][j]=Matr[j][i];
                }
                else
                {
                    std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                        <<"0 for not connect them\n";
                    std::cin>>Matr[i][j];
                    if(Matr[i][j]==0)
                        Matr[i][j]=100;
                }
            }
        }
    }
protected:
    VM Matr;
};
 
class Floyd:public MatrixAdj
{
public:
    Floyd():MatrixAdj()
    {
    }
 
    ~Floyd()
    {
    }
 
    void Initialise()
    {
        MatrPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrPath[i].resize(Matr.size());
        for(size_t i=0; i<MatrPath.size(); ++i)
        {
            for(size_t j=0; j<MatrPath.size(); ++j)
            {
                if(Matr[i][j]==100)
                    MatrPath[i][j]=100;
                else
                    MatrPath[i][j]=j;
            }
        }
        Copy();
    }
    
    void FindPathMatr()
    {
        for(size_t k=0; k<Matr.size(); ++k)
        {
            for(size_t i=0; i<Matr.size(); ++i)
            {
                for(size_t j=0; j<Matr.size(); ++j)
                {
                    int b=MatrSPath[i][k]+MatrSPath[k][j];
                    if(b<MatrSPath[i][j])
                    {
                        MatrSPath[i][j]=b;
                        MatrPath[i][j]=k;
                    }
                }
            }
        }
    }
 
    void FindPath(size_t first, size_t second)
    {
        if(first>=MatrPath.size() || second>=MatrPath.size())
            throw std::invalid_argument("One of nodes for searching is more than Matr size");
        ST Goals;
        Path.push(first);
        Goals.push(second);
        while(!Goals.empty())
        {
            int u=Path.top();
            int v=Goals.top();
            int s=MatrPath[u][v];
            if(v==s)
            {
                Path.push(v);
                Goals.pop();
            }
            else
                Goals.push(s);
        }
    }
 
    void PrintWMatr(std::ostream& os) const
    {
        PrintMatr(Matr, os);
    }
 
    void PrintSPMatr(std::ostream& os) const
    {
        PrintMatr(MatrSPath, os);
    }
 
    void PrintPMatr(std::ostream& os) const
    {
        PrintMatr(MatrPath, os);
    }
 
    void PrintSt(std::ostream& os)
    {
        while(!Path.empty())
        {
            os<<Path.top()<<' ';
            Path.pop();
        }
        os<<'\n';
    }
private:
    VM MatrPath;
    VM MatrSPath;
    ST Path;
    
    void PrintMatr(const VM& Vec, std::ostream& os) const
    {
        for(size_t i=0; i<Vec.size(); ++i)
        {
            for(size_t j=0; j<Vec.size(); ++j)
            {
                os<<std::setw(3)<<Vec[i][j]<<' ';
            }
            os<<'\n';
        }
    }
 
    void Copy()
    {
        MatrSPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrSPath[i].resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            std::copy(Matr[i].begin(), Matr[i].end(), MatrSPath[i].begin());
    }
};
 
std::ostream& operator <<(std::ostream& os, const Floyd& Ob)
{
    os<<"Weight matrix\n";
    Ob.PrintWMatr(os);
    os<<"Shortest paths matrix\n";
    Ob.PrintSPMatr(os);
    os<<"Shortest path nodes matrix\n";
    Ob.PrintPMatr(os);
    return os;
}
 
#endif

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
//Floyd.cpp
#include "Floyd.h"
 
int main()
{
    try
    {
        int n;
        std::cout<<"Enter numb of nodes: ";
        std::cin>>n;
        Floyd Ob;
        Ob.SetSize(n);
        Ob.Fill();
        Ob.Initialise();
        Ob.FindPathMatr();
        std::cout<<Ob;
        size_t first, second;
        std::cout<<"Enter first and second nodes for search path between them\n";
        std::cin>>first>>second;
        Ob.FindPath(first, second);
        std::cout<<"Shortest path between " << first <<" and "<< second <<" nodes is\n";
        Ob.PrintSt(std::cout);
    }
    catch(std::exception& e)
    {
        std::cerr<<e.what()<<'\n';
        return 1;
    }
    return 0;
}

@vvs79 · 10.06.2020, 13:19

Может я конечно поздновато.
Но, при компилировании говорит:
Ошибка C4703 используется потенциально неинициализированная локальная переменная-указатель "pOb"
В строках
pOb->SetSize(size);
pOb->Input();
pOb->Output();
Как скомпилировать ?

@DrOffset · 10.06.2020, 13:36

vvs79,

C++
1
Graph*pOb = 0;

На нуле вызова не будет, т.к. эта ситуация обрабатывается выше.

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@vvs79 1 / 1 / 0 Регистрация: 28.03.2017 Сообщений: 168
	10.06.2020, 13:19
	Может я конечно поздновато. Но, при компилировании говорит: Ошибка C4703 используется потенциально неинициализированная локальная переменная-указатель "pOb" В строках pOb->SetSize(size); pOb->Input(); pOb->Output(); Как скомпилировать ? 0