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

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

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

Алгоритмы на графах - C++

07.12.2010, 17:38. Просмотров 932. Ответов 0
Метки нет (Все метки)

Помогите пожалуйста выполнить вот это вот задание:
a) Нарисовать матрицу смежности графа.
Б) Создать файл “graf.txt”.
в) Вставить промежуточную печать и выполнить трассировку программы,
чтобы увидеть обход графа в ширину.
На каждом шаге распечатывать массив меток и СД «очередь»
Вот листинг который прилагается к заданию
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
int i,j,k,p,cur;
int Start, N, M;
int main()
{int **Graf; // объявляем матрицу смежности
int *Label; // объявляем массив меток
int *FIFO; // объявляем СД очередь
ifstream input(“graf.txt);
2
input>>N>>M>>Start; // читаем из файла
Label= new int [N];
FIFO= new int [N];
Graf= new int * [N];
for(i=0;i<N;i++) {Graf[i]= new int [N];}
for(k=0;k<M;k++)
{input>>i>>j; // читаем номера смежных вершин
Graf[i][j]=1; // матрица смежности
}
for(i=0;i<M;i++){FIFO[i]=0;Label[i]=32767;}
p=0; // указатель на начало очереди
k=1; // указатель на конец очереди
FIFO[p]=Start;Label[Start]=0; while (p!=k) {
cur=FIFO[p]; p++; for(i=0;i<N;i++)
if(Graf[cur][i]==1 && Label[i]>Label[cur]+1)
{FIFO[k]=i; // выделяем очередную вершину из очереди
k++; // сдвигаем указатель начала на 1
Label[i]=Label[cur]+1; //помечаем вершину
}
}
// вывод результата
for(i=0;i<N;i++) cout<<Label[i]<<” ” ;
getch();
return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2010, 17:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритмы на графах (C++):

Алгоритмы на графах - C++
Изолированные города В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько...

Вопросы о графах - C++
Всем привет! Появилось несколько вопросов о графах: 1) Как представить граф в C++? 2) Как найти самый краткий путь между двумя...

Игры на графах - C++
Помогите пожалуйста 😊 Имя входного файла: стандартный ввод Имя выходного файла: Стандартный вывод Ограничение по времени:1 секунда ...

"Поиск путей на графах". С++ - C++
Задача. Для некоторого ориентированного графа задана матрица весов W. С помощью алгоритма Форда-Беллмана вычислить веса кратчайших...

Алгоритмы С++ - C++
Написать программу календарь, которая при вводе даты выдает день недели

Алгоритмы на C++ - C++
Вот решил приобрести себе такую ​​книгу. http://www.ozon.ru/context/detail/id/5531965/ Книга вроде не плохая, но там нет описания всех...

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

Алгоритмы - C++
case 2:{ int n1; int n2; do{ cout &lt;&lt; &quot;Введите номер словаря в который хотите добавить ячейку: ...

Циклические алгоритмы - C++
Как реализовать данную функцию для каждого x, изменяющегося от a до b с шагом h. Значения a, b, h и n вводятся с клавиатуры. Работу...

Жадные алгоритмы - C++
По 5 клеточному полю, клетки которой расположены по координатам (-1,0), (0,0), (0,1), (0,1), (0,-1), перемещается одно из двух тел(не...

Циклические алгоритмы - C++
Дано число D (&gt; 0). Последовательность чисел AN определяется следую- щим образом: A1 = 2, AN = 2 + 1/AN–1, N = 2, 3,... Найти первый из ...


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

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

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