Поиск паросочетаний в графе

@sasha2280 · Регистрация: 05.11.2013

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

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

Имеется мое решение на С++(Именно его и не могу переписать на Haskell):

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
 
void main(){
    int a[7][7] = {
        {0, 1, 0, 1, 1, 1, 1},
        {1, 0, 1, 1, 1, 0 ,1},                  
        {0, 1, 0, 1, 1, 1, 0},
        {1, 1, 1, 0, 1, 0, 0},
        {1, 1, 1, 1, 0, 1, 1},
        {1, 0, 1, 0, 1, 0, 1},
        {1, 1, 0, 0, 1, 1, 0}
    };
 
    int res = 0;
    for (int i=0; i<7; i++){
        for (int j=0; j<7; j++){
            if (a[i][j]!=0){
                for (int k=0; k<7; k++){
                    a[i][k] = 0;
                    a[k][i] = 0;
                    a[j][k] = 0;
                    a[k][j] = 0;
                }
                res++;
            }
        }
    }
    cout << "Count of matchings: " << res << endl;
}

@Algiz · 06.11.2013, 17:03

Максимальное паросочетание или любое паросочетание?

@sasha2280 · 06.11.2013, 17:58 **[ТС]**

Любое паросочетание

В моем коде на Си эта задача решается так:
1) Берется матрица в которой представлены связи вершин графа друг с другом(1 - связь есть, 0 - нету)
2) Находится паросочетание, после чего все связи с этими 2 вершинами обнуляются
3) Идем дальше по матрице пока она не кончится или не найдется следующее паросочетание.

@Algiz · 06.11.2013, 18:45

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph = [[0, 1, 0, 1, 1, 1, 1],
         [1, 0, 1, 1, 1, 0 ,1],                  
         [0, 1, 0, 1, 1, 1, 0],
         [1, 1, 1, 0, 1, 0, 0],
         [1, 1, 1, 1, 0, 1, 1],
         [1, 0, 1, 0, 1, 0, 1],
         [1, 1, 0, 0, 1, 1, 0]]
 
normalize l = zip [0..] $ map (\l' -> [n | (n,1) <- zip [0..] l']) l
 
makePairs l = loop l [] []
    where
        loop [] _ res = res
        loop ((n,links):t) was res
            | n `elem` was || null l = loop t was res
            | otherwise = loop t (n:head l:was) ((n,head l):res)
            where l = filter (not . (`elem` was)) links
 
main = print$ makePairs$ normalize graph

@sasha2280 · 06.11.2013, 19:02 **[ТС]**

Большое спасибо, очень выручил!
Всех благ тебе)

@Catstail · 06.11.2013, 19:06

Вот функция, которая в квадратной матрице matr обнуляет строку r и столбец с

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
setZero :: [[Int]] -> Int -> Int -> [[Int]]
setZero matr r c = (take (r-1) mm) ++ [z] ++ (drop r mm)
                   where mm = map (\ x -> (take (c-1) x) ++ [0] ++ (drop c x)) matr 
                         z  = (take (length matr) (repeat 0))
 
Main> setZero [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] 1 3
 
[[0,0,0,0],[1,2,0,4],[1,2,0,4],[1,2,0,4]]
 
Main> setZero [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] 2 4
 
[[1,2,3,0],[0,0,0,0],[1,2,3,0],[1,2,3,0]]

пригодится...

@sasha2280 · 06.11.2013, 19:23 **[ТС]**

Хотя если честно не могу толком понять код(точнее вообще понять):

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph = [[0, 1, 0, 1, 1, 1, 1],
         [1, 0, 1, 1, 1, 0 ,1],                  
         [0, 1, 0, 1, 1, 1, 0],
         [1, 1, 1, 0, 1, 0, 0],
         [1, 1, 1, 1, 0, 1, 1],
         [1, 0, 1, 0, 1, 0, 1],
         [1, 1, 0, 0, 1, 1, 0]]
 
normalize l = zip [0..] $ map (\l' -> [n | (n,1) <- zip [0..] l']) l
 
makePairs l = loop l [] []
    where
        loop [] _ res = res
        loop ((n,links):t) was res
            | n `elem` was || null l = loop t was res
            | otherwise = loop t (n:head l:was) ((n,head l):res)
            where l = filter (not . (`elem` was)) links
 
main = print$ makePairs$ normalize graph

Тут берется матрица graph, видимо переформируется, а вот как происходит поиск вообще понять не могу....
Не могли бы вы его немного прокомментировать, пожалуйста?

@Algiz · 06.11.2013, 21:18

Сообщение от sasha2280

Не могли бы вы его немного прокомментировать, пожалуйста?

функция normalize преобразует граф к такому виду
[[0,0,1,1]
[0,0,0,1]
[1,0,0,1]
[1,1,1,0]]
==>
[(0,[2,3]),(1,[3]),(2,[0,3]),(3,[0,1,2])]
то есть список пар, где первое значение- вершина, второе- список вершин, с которыми данная смежна.
makePairs из такого представления графа получает пары. Работает тривиально. если список пуст - вернуть аккумулятор, если не пуст, то если текущая вершина использована или все смежные к текущей вершины использованы, то игнорируем ее и идем дальше по списку, иначе берем первую неиспользованную смежную вершину. Эти две вершины(текущую и смежную) помещаем в список использованных и в аккумулятор(в паре, конечно же).

normalize работает еще проще:
на вход список где номер элемента - вершина, значение - список смежных
1) нумеруем список
2) нумеруем каждый подсписок список
3) из подсписков убираем все пары где второй элемент - 0
4) приводим подсписки из такого вида [(0,[(1,1),(3,1)]),(1[(0,1)])...] в такой [(0,[1,3]),(1[0])...]

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Algiz 165 / 164 / 23 Регистрация: 23.02.2011 Сообщений: 347
	06.11.2013, 17:03
	Максимальное паросочетание или любое паросочетание? 0

@sasha2280 0 / 0 / 0 Регистрация: 05.11.2013 Сообщений: 4
	06.11.2013, 17:58 [ТС]
	Любое паросочетание В моем коде на Си эта задача решается так: 1) Берется матрица в которой представлены связи вершин графа друг с другом(1 - связь есть, 0 - нету) 2) Находится паросочетание, после чего все связи с этими 2 вершинами обнуляются 3) Идем дальше по матрице пока она не кончится или не найдется следующее паросочетание. 0

@sasha2280 0 / 0 / 0 Регистрация: 05.11.2013 Сообщений: 4
	06.11.2013, 19:02 [ТС]
	Большое спасибо, очень выручил! Всех благ тебе) 0

Поиск паросочетаний в графе

Решение