Курсовой проект «Комбинаторные алгоритмы. Поиск кратчайшего пути на графе.»

Приложение 2. Генерация перестановок из n элементов


Программа
#include "stdafx.h"
#include
using namespace std;
int X[100];
int N;
void Swap(int a,int b)
{
int t=X[a];
X[a]=X[b];
X[b]=t;
}
void Generate(int k)
{
if (k==N)
{
for(int i=0;icout<cout<<"\n";
}
else
{
for(int j=k;j{
Swap(k,j);
Generate(k+1);
Swap(k,j);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<"N=";
cin>>N;
for(int i=0;iX[i]=i+1;
Generate(0);
cout<<"Press any button";
cin.get();
return 0;
}

Приложение 3. Построение эйлерова цикла на графе

#include "stdafx.h"

#include
#include
using namespace std;
int main()
{
stack stackArray;

const int N=3;

cout<<"Enter the adjacency matrix for 3 elements"<<'\n';
int vertexArray[N]; // массив вершин
bool adjacencyArray[N][N]; // матрица смежности
for(int i=0; i{
int k=0;
for(int j=0; j{
cin>>adjacencyArray[i][j];
if (adjacencyArray[i][j]!=0) k++;
}
vertexArray[i]=k;
}
for(int i=0; iif (vertexArray[i]%2!=0)
{
cout<<"There is no Euler tour."; // Если кол-во единиц нечетно - пути Эйлера нет
return 0;
}
cout<<"The Euler tour is:"<<'\n'; // Если четно - путь есть, выводим на экран сам путь
stackArray.push(0); // Принцип работы стека - последний зашел - первый вышел
while (!stackArray.empty())
{
int topOfStack=stackArray.top();
if (vertexArray[topOfStack]==0)
{
stackArray.pop();
cout<}
else
{
int i=0; while (adjacencyArray[topOfStack][i]==0) i++;
stackArray.push(i);
adjacencyArray[topOfStack][i]=adjacencyArray[i][topOfStack]=0;
vertexArray[topOfStack]--; vertexArray[i]--;
}
}
int ab;
std::cin >> ab;
return 0;
}

Приложение 4. Поиск кратчайшего пути на графе. Алгоритм Дейкстры

Исходный код программы на языке программирования C++

#include "StdAfx.h"
#include
using namespace std;
int i, j, n, num, start_pos, end_pos;
int infinity = 99999;
int visit[15];
int matrix[15][15];
int lenght[15];
char s[100];
char path[100][15];
void _tmain()
{
setlocale(LC_ALL,"Russian");
cout<<"Введите количество вершин: ";
cin>>n;
cout<<"\n";
for(i=0;ifor(j=0;jfor(i=0;ifor(j=i+1;j{
cout<<"Расстояние от "<cin>>matrix[i][j];
}
cout<<"\n\n ";
for(i=0;icout<cout<<"\n";
for(i=0;i{
printf("X%d",i+1);
for(j=0;j{
printf("%6d",matrix[i][j]);
matrix[j][i]=matrix[i][j];
}
printf("\n\n");
}
for(i=0;ifor(j=0;jif(matrix[i][j]==0) matrix[i][j]=infinity;
cout<<"\n";
for(;;)
{
cout<<"Введите начальную вершину: ";
cin>>start_pos;
if(start_pos<1 || start_pos>n)
{
cin.clear();
fflush(stdin);
cout<<"Некорректный ввод. Введите номер вершины в интервале от 1 до "<}
else break;
}
start_pos--;
for(;;)
{
cout<<"Введите конечную вершину: ";
cin>>end_pos;
if(end_pos<1 || end_pos>n)
{
cin.clear();
fflush(stdin);
cout<<"Некорректный ввод. Введите номер вершины в интервале от 1 до "<}
else break;
}
end_pos--;
cout <<"\n";
if(start_pos==end_pos)
{
cout<<"Начальная и конечная точка совпадают\n"<return;
}
for(i=0;i{
visit[i]=0;
lenght[i]=infinity;
}
lenght[start_pos]=0;
visit[start_pos]=1;
num=start_pos;
itoa(start_pos+1,s,10);
for(i=1;i<=n;i++)
{
strcpy(path[i],"X");
strcat(path[i],s);
}
do
{
for(i=0;iif((matrix[num][i]!=infinity)&&(!visit[i])&&(i!=num))
{
if(lenght[i]>lenght[num]+matrix[num][i])
{
itoa(i+1,s,10);
strcpy(path[i+1],path[num+1]);
strcat(path[i+1],"-X");
strcat(path[i+1],s);
}
if(lenght[i]>lenght[num]+matrix[num][i]) {
lenght[i] = lenght[num]+matrix[num][i];
}
}
for(i=0;iif(!(visit[i])) num=i;
for(i=0;iif((lenght[num]>lenght[i])&&(!visit[i])) num=i;
visit[num]=1;
}
while(num!=end_pos);
if(lenght[num]!=infinity)
{
cout<<"Путь: "<
cout<<"Длина пути: "<}
else
cout<<"Такого пути не существует"<}