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

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

Войти
Регистрация
Восстановить пароль
 
kuziynia
Сообщений: n/a
#1

Обобщенный поиск на графе, основанный на очереди по приоритетам - C++

28.03.2011, 17:28. Просмотров 506. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста, дописать программу: "Обобщенный поиск на графе, основанный на очереди с приоритетами", входные данные:количество вершин графа, ребра и их вес, выход: порядок посещения вершин.
Вот исходный код:

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;


struct bahroma
{
int ishod_versh;
int versh_nazn;
int ves_rebra;
void print()
{
cout <<ishod_versh<<"\t"<<versh_nazn<<"\t"<<ves_rebra<<"\n";
}
};

template <class Item, class Key> class List
{
private:
struct node
{
Item *item;
node* next;
node(Item *x) { item=x; next=0; } //Конструктор структуры node
};
typedef node *link;
link head, tail;
link now_node;
public:
List() //Конструктор класса List
{
head=0; tail=0;
}
void add(Item *x)
{
link t = new node(x);

if(tail!=0)
{
//СПИСОК уже НЕ ПУСТ
tail->next = t;
tail = t;
} else
{
head = tail = t;
}
}
Item *iterator(int x)
{
if (!x) now_node = head;
else now_node = now_node->next;

if (now_node) return now_node->item;
return 0;
}


void print()
{
for(link i=head; i!=0; i=i->next)
i -> item -> print();
}
};

int main()
{

int n=5; //количество вершин графа
int A [n][n]; //матрица смежности и вес ребер
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
A [i][j]=rand()%2; //случайное заполнение массива 0 и 1
if (A [i][j]==1) //если элемент=1
{
A [i][j]=rand()%5+1; //присваиваем случайное значение от1 до 5
}
cout<<A[i][j]<<" "; //печать элементов строки
}
cout<<endl;
}
cout<<endl;

int s=3; //стартовая вершина обхода графа
int B [n]; //одномерный массив-вектор порядка посещения вершин
//int k; //индекс вектора обхода В
for (int k=0; k<n; k++)
{
B[k]=0; //заполняем массив нулями
//cout<<B[k]<<endl; //вывод массива
}
int c=1; //счетчик номера посещения вершины
int p=s; //индекс посещенной вершины
while (p<=n)
{
B[p]=c; //элементу массива с индексом р присваивается значение с
cout <<B[p]<<endl;
p=p+2; //изменение индекса массива
cout<<p<<endl;
c++; // счетчик посещенных вершин
cout<<c<<endl;
}

for (int p=1; p<=n; p++)
{
cout<<B[p];
}
cout<<endl;

if (s>n)
{
cout<<"Net takoj vershunu"<<endl;
return 0;
}
while (int j=s) // пока j=s
{
for (int i=1; i<=n; i++) //обход по строке
{
//cout<< A[j][i]<<endl; //печать элементов строки
if (A[j][i]!=0)
{
p=i;
if (B[p]==0)
{
for (int b=1; b<=n; b++)
{
bahroma b={j, i, A[j][i]};
List<bahroma,int> list_1;
list_1.add(&b);
list_1.print();
break;
}
}

}
}
cout<<endl;
break; //выход

}


return 0;
}
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.03.2011, 17:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обобщенный поиск на графе, основанный на очереди по приоритетам (C++):

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Обобщенный и не обобщенный класс с одинаковым именем - C#
Добрый день! Task&lt;int&gt; task = Task.Run(() =&gt; { Console.WriteLine(&quot;Foo&quot;); return 3; }); Как такое возможно? Метод Run Возвращает тип...

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

Поиск циклов в графе - C++
Как узнать что граф имеет цикл?

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

Поиск в ширину в графе - Turbo Pascal
Здравствуйте. Помогмте, пожалуйста! Суть в чем: В неориентированном графе требуется найти минимальный путь между двумя вершинами. ...

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

Поиск пути в графе - Prolog
Помогите,кто может,пожалуйста,с написанием задачи(И как ее проверять)!Очень нужно до завтра сдать,а то мне будет хана!!В прологе разбераюсь...

Поиск в ширину в графе - Алгоритмы
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и полчается список списков,в котором первые элементы -...

Поиск паросочетаний в графе - Haskell
Помогите пожалуйста, надо срочно сдать лабораторную работу но никак не могу понять как реализовать это на Haskell. Задание: найти все...

Поиск в ширину на графе - C++
#include &quot;stdafx.h&quot; #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; #include&lt;vector&gt; #include&lt;queue&gt; using namespace...


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

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

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