Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
1

Реализовать алгоритм Краскала

12.02.2016, 23:26. Просмотров 2233. Ответов 17
Метки нет (Все метки)

Добрый день, друзьяшки. Помогите пожалуйста, кому не будет трудным
Препод дал такое задание:
Напишите две компьютерные программы (На С++ и на lisp (или на F#)), решающие следующую задачу:
Связный граф задан списком ребер. Каждое ребро представляет собой тройку (вершина, вершина, длина). Граф неориентированный. Найти минимальное остовное дерево (в виде списка образующих его ребер).
Сделал это задание на C++, но лисп вобще не знаю, можете пожалуйста написать?)
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <list>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <vector>
#include <windows.h>
using namespace std;
 
#ifdef max
#undef max
#endif
 
class Graph
{
    struct edge
    {
        unsigned vertex1, vertex2, length;
    };
 
    list<edge> graph;
    unsigned vertexes, highestVertex;
 
    void correctInput(unsigned& arg)
    {
        while (!(cin >> arg))
        {
            cout << "\nНекорректный ввод, повторите попытку:" << endl;
            cin.clear();
            cin.sync();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
        }
    }
 
    void addEdge(void)
    {
        edge tempObj;
        graph.push_back(tempObj);
        system("cls");
        cout << "Производится ввод " << graph.size()
            << "-ого ребра...\n" << endl;
        cout << "Введите 1-ую вершину:" << endl;
        correctInput(graph.back().vertex1);
        cout << "Введите 2-ую вершину:" << endl;
        correctInput(graph.back().vertex2);
        cout << "Введите вес ребра:" << endl;
        correctInput(graph.back().length);
        if (graph.back().vertex1 > highestVertex)
            highestVertex = graph.back().vertex1;
        if (graph.back().vertex2 > highestVertex)
            highestVertex = graph.back().vertex2;
        system("cls");
    }
 
public:
    static struct sortFunctor
    {
        bool operator() (const edge& arg1, const edge& arg2)
        {
            return arg1.length < arg2.length;
        }
    } sortObj;
 
    Graph(void) : vertexes(0), highestVertex(0)
    {   }
 
    Graph(unsigned arg) : vertexes(arg), highestVertex(0)
    {   }
 
    friend istream& operator>>(istream&, Graph&);
    friend ostream& operator<<(ostream&, const Graph&);
};
 
Graph::sortFunctor Graph::sortObj;
 
istream& operator>>(istream& arg1, Graph& arg2)
{
    if (!arg2.vertexes)
    {
        system("cls");
        cout << "Граф пустой, введите число его ребер:" << endl;
        arg2.correctInput(arg2.vertexes);
    }
    if (arg2.vertexes)
    {
        for (unsigned i(0); i < arg2.vertexes; i++)
            arg2.addEdge();
        system("cls");
        arg2.graph.sort(Graph::sortObj);
    }
    return arg1;
}
 
ostream& operator<<(ostream& arg1, const Graph& arg2)
{
    vector<bool> table(arg2.highestVertex, false);
    system("cls");
    cout << "Ребра минимального остовного дерева:\n" << endl;
    for (unsigned i(0); i++ < 45; cout.put('-'));
    cout.put('\n');
    cout << setw(15) << "Вершина 1" << setw(3) << '|'
        << setw(12) << "Вершина 2" << setw(7) << '|'
        << setw(8) << "Вес" << endl;
    for (unsigned i(0); i++ < 45; cout.put('-'));
    cout.put('\n');
    list<Graph::edge>::const_iterator iter(arg2.graph.begin());
    for (; iter != arg2.graph.end(); iter++)
    {
        static unsigned index1, index2;
        index1 = iter->vertex1 - 1;
        index2 = iter->vertex2 - 1;
        if (!table[index1] || !table[index2])
        {
            table[index1] = true;
            table[index2] = true;
            cout << setw(15) << iter->vertex1
                << setw(3) << '|' << setw(12) << iter->vertex2
                << setw(7) << '|' << setw(8) << iter->length << endl;
        }
    }
    for (unsigned i(0); i++ < 45; cout.put('-'));
    return arg1;
}
 
int main(void)
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    Graph gr(0);
    cin >> gr;
    cout << gr << endl;
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.02.2016, 23:26
Ответы с готовыми решениями:

Реализовать Алгоритм Краскала
Нужно исправить код. Ошибки. Какой код лучше подойдёт? #include &lt;iostream&gt; #include &lt;vector&gt;...

Алгоритм Краскала
namespace GraphMethods { using System; using System.Collections.Generic; using...

Алгоритм Краскала
Народ, кто-нибудь может на естественном языке пояснить суть алгоритма Краскала? Я чето не понял,...

Алгоритм Краскала
Здравствуйте. Передо мной стоит задача реализовать алгоритм Краскала в C++ Builder. Интерфейсная...

17
1045 / 939 / 107
Регистрация: 04.11.2012
Сообщений: 971
Записей в блоге: 3
12.02.2016, 23:59 2
https://www.cyberforum.ru/post6334776.html
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
16.02.2016, 20:00 3
Мое решение (HomeLisp):

Lisp
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
;; Проверить ребро (не образует ли оно цикл)
 
(defun chk-vert (v s) ;; v - ребро; s - "лес" уже добавленных
  (let ((a1 (car v))
        (a2 (cadr v)))
    (not (forsome s (lambda (w) (and (member a1 w) (member a2 w)))))))
        
;; Добавление очередного ребра в "лес"        
        
(defun ins-vert (v w)        
  (let* ((a1 (car v))
         (a2 (cadr v))
         (w1 (remove-if-not (lambda (x) (member a1 x)) w)) 
         (w2 (remove-if-not (lambda (x) (member a2 x)) w)))
    (cond ((and (null w1) (null w2)) (cons v w))
          ((null w1) (cons (cons a1 (car w2)) (remove-if (lambda (x) (member a1 x)) w)))
          ((null w2) (cons (cons a2 (car w1)) (remove-if (lambda (x) (member a2 x)) w)))
          (t (cons (append w1 w2) (remove-if (lambda (x) (or (member a1 x) (member a2 x)) w)))))))
 
;; Очередной шаг
;; Терминирование рекурсии можно выполнить и раньше (когда лес w будет содержать все вершины)
    
(defun action (graph &optional (w nil) (r nil))
  (cond ((null graph) r)
        ((chk-vert (car graph) w) (action (cdr graph) (ins-vert (car graph) w) (append r (list (car graph))))) 
        (t (action (cdr graph) w r))))
        
(defun kruskal (graph)
  (let ((g (qsort-a graph (lambda (x) (nth 2 x))))) ;; сортировка по возрастанию -> дерево мин. веса
     (action g)))
Если ребра отсортировать по убыванию - получится дерево максимального веса.

Граф задается списком ребер с длинами:

Lisp
1
2
3
(kruskal '((a b 1) (a e 1) (a c 5) (b e 2) (b d 2) (c d 3) (c e 3) (d e 1)))
 
==> ((d e 1) (a e 1) (a b 1) (c e 3)) ;; верно
2
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
16.02.2016, 20:54  [ТС] 4
Catstail, Отлично!
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
17.02.2016, 22:27 5
Лучший ответ Сообщение было отмечено Ferrari F1 как решение

Решение

Ferrari F1, к сожалению, есть неточности... Вот проверенное решение:

Lisp
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
;; Проверить ребро
 
(defun chk-vert (v s)
  (let ((a1 (car v))
        (a2 (cadr v)))
    (not (forsome s (lambda (w) (and (member a1 w) (member a2 w)))))))
        
;; Добавление очередного ребра в "лес"        
        
(defun ins-vert (v w)        
  (let* ((a1 (car v))
         (a2 (cadr v))
         (w1 (car (remove-if-not (lambda (x) (member a1 x)) w)))
         (w2 (car (remove-if-not (lambda (x) (member a2 x)) w))))
    (cond ((and (null w1) (null w2)) (cons (butlast v) w))
          ((null w1) (cons (cons a1 w2) (remove-if (lambda (x) (member a2 x)) w)))
          ((null w2) (cons (cons a2 w1) (remove-if (lambda (x) (member a1 x)) w)))
          (t (cons (append w1 w2) (remove-if (lambda (x) (or (member a1 x) (member a2 x))) w))))))
 
 
;; Очередной шаг
    
(defun action (graph &optional (w nil) (r nil))
  (cond ((null graph) r)
        ((chk-vert (car graph) w) (action (cdr graph) (ins-vert (car graph) w) (append r (list (car graph))))) 
        (t (action (cdr graph) w r))))
        
(defun kruskal (graph)
  (let ((g (qsort-a graph (lambda (x) (nth 2 x)))))
     (action g)))
3
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
24.02.2016, 19:01  [ТС] 6
Catstail,
извините меня, но можно попросить Вас сделать побольше комментариев в Вашем коде?

Добавлено через 9 часов 48 минут
АП!
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
24.02.2016, 19:23 7
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
АП!
- это неверная тональность... Когда выберу время - напишу.
0
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
24.02.2016, 20:52  [ТС] 8
Catstail, извиняюсь сердешно

Добавлено через 1 час 26 минут
Catstail, подскажите, пожалуйста, как исправить?
Lisp
1
2
3
4
5
Файл C:\Users\Admin\Desktop\s.lsp успешно загружен
(kruskal '((a b 1) (a e 1) (a c 5) (b e 2) (b d 2) (c d 3) (c e 3) (d e 1)))
 
Внутри LET: EVFUN: Не найдена функция QSORT-A
==> ERRSTATE
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
25.02.2016, 10:56 9
Цитата Сообщение от Ferrari F1 Посмотреть сообщение
извиняюсь сердешно
- ничего страшного!

Цитата Сообщение от Ferrari F1 Посмотреть сообщение
как исправить?
- добавить qsort-a:

Lisp
1
2
3
4
5
(defun qsoet-a (x fkey) 
  (COND ((NULL x) NIL) 
        (T (APPEND (qsort-a (remove-if (FUNCTION (LAMBDA (z) (> (FUNCALL fkey z) (FUNCALL fkey (CAR x))))) (CDR x)) fkey) 
                   (LIST (CAR x)) 
                   (qsort-a (remove-if (FUNCTION (LAMBDA (z) (<= (FUNCALL fkey z) (FUNCALL fkey (CAR x))))) (CDR x)) fkey)))))
1
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
29.02.2016, 18:53  [ТС] 10
Catstail, Спасибки Вам огромное за все Ваши труды. НО! можно попросить Вас добавить на Ваш сайт свежую версию HomeLisp'a?

Поскольку я скачал версию HomeLisp 1.13.4, которая отображена как самая свежая на сайте, и у меня с Вашим кодом чуть ли не на каждом шагу выдавались ошибки компилятором из-за отстутствия многих функций.

Ситуация разрешилась добавлением библиотеки lib-k, которой НЕТ в скачанном выше дистрибутиве, а ТАКЖЕ пришлось качать вот эти файлы ([HomeLisp] Не найдена функция APPEND) и скопировать их с заменой.
1
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
29.02.2016, 18:57 11
Ferrari F1, собираюсь обновить...
0
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
29.02.2016, 19:05  [ТС] 12
Catstail, а можно еще Вас спросить немного не по теме:
А какая программа по-вашему мнению выполняется быстрее (транслируется в меньшее кол-во ассемблерных инструкций): та, что написана мною на С++ или Ваша, на лиспе?
Лишь субъективное мнение, на глаз.
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
29.02.2016, 20:42 13
Конечно, на C++ быстрее
0
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
29.02.2016, 21:02  [ТС] 14
Catstail, странно, я думал, что наоборот. Ведь операторов у Вас в коде куда меньше, чем у меня. За счет чего быстрее?
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
01.03.2016, 08:22 15
Каждый оператор Лиспа требует значительно больших затрат, чем оператор C++.
0
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
01.03.2016, 08:39  [ТС] 16
Catstail, можно ли считать, что в функциональных языках уровень абстракции выше, чем в императивных и чем больше уровень абстракции, тем медленнее работа программы на этом языке?
0
Модератор
Эксперт Python
27003 / 14173 / 2731
Регистрация: 12.02.2012
Сообщений: 23,233
Записей в блоге: 3
01.03.2016, 09:31 17
Трудно сказать насчет уровня абстракции (в продвинутых императивных языках уровень сопоставим с функциональными). Проблемой производительности ФЯ является то, что данные нельзя модифицировать (а только создавать копии). Это требует и памяти и ресурсов. Зато функциональные программы должны проще распараллеливаться.
1
800 / 530 / 157
Регистрация: 27.01.2015
Сообщений: 3,025
Записей в блоге: 1
03.03.2016, 12:30  [ТС] 18
Catstail, а можно Вас еще попросить объяснить суть алгоритма, используемого в программе? Я понял, что Вы формируете каркас, добавляя ребра (предварительно их отсортировав по весу) с мин. весом одно за другим. Но хотел бы понять более детально алгоритм.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2016, 12:30

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Алгоритм Краскала
Можете указать,в чем ошибка в данном коде,почему при вводе данных он выдает ошибку if Comp !=...

Алгоритм Прима-Краскала
Вот код, подскажите пожалуйста, какой вопрос вводить для выдачи результата? путь(X,Z,Граф,Res):- ...

Алгоритм Краскала без векторов
Помогите реализовать алгоритм Краскала без векторов на С++, могу заплатить.

Алгоритм Крускала (Краскала) на Assembler
Добрый день! Кто-то имеет программную реализацию алгоритма Крускала (Краскала) на FASM???


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

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

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