return matchSize;

}

private void generate() {

Random random = new Random();

for (int i = 0; i < leftNodeNumber; i++) {

for (int j = 0; j < rightNodeNumber; j++) {

if (random.nextInt(10) <= 7) {

graph[i][j] = 1;

} else {

graph[i][j] = 0;

}

}

}

}

private void findMaxMatch() {

if(leftNodeNumber == 1 || rightNodeNumber == 1){

maxMatch.add(0);

matchSize = 1;

return;

}

for (int i = 0; i < rightNodeNumber; i++) {

maxMatch.add(-1);

}

for (int i = 0; i < leftNodeNumber; ++i) {

usedNodes.add(false);

kuhnAlgorithm(i);

}

}

private boolean kuhnAlgorithm(int leftNodeIndex) {

if (usedNodes.get(leftNodeIndex)) {

return false;

}

usedNodes.set(leftNodeIndex, true);

for (int i = 0; i < graph[leftNodeIndex].length; i++) {

int to = graph[leftNodeIndex][i];

if(to > rightNodeNumber){

break;

}

if (maxMatch.get(to) == -1 || kuhnAlgorithm(maxMatch.get(to))) {

maxMatch.set(to, leftNodeIndex);

matchSize++;

return true;

}

}

return false;

}

public void printInConsole() {

for (int i = 0; i < leftNodeNumber; i++) {

for (int j = 0; j < rightNodeNumber; j++) {

if (graph[i][j] == 1) {

System.out.print(1 + " ");

} else {

System.out.print(0 + " ");

}

}

System.out.println("\n");

}

}

public void printMaxMatchInConsole() {

System.out.println("Max match:\n");

for (int match : maxMatch) {

if (match != -1) {

System.out.println(match + " -> " + maxMatch.indexOf(match));

}

}

System.out.println("match size = " + matchSize);

}

}

GraphView.java

package gui;

import common.Constants;

import graph.BipartiteGraph;

import javax.swing.*;

import java.awt.*;

public class GraphView extends JPanel {

private BipartiteGraph bipartiteGraph;

private int[][] graph;

private final int leftXOffset = 20;

private final int rightXOffset = leftXOffset + 200;

private final int yOffset = 50;

public GraphView(BipartiteGraph bipartiteGraph) {

this.bipartiteGraph = bipartiteGraph;

this.graph = bipartiteGraph.getGraph();

}

@Override

protected void paintComponent(Graphics g) {

drawLeftNodes(g);

drawRightNodes(g);

drawEdges(g);

drawMatchNumber(g);

}

private void drawLeftNodes(Graphics g) {

int y;

for (int i = 0; i < bipartiteGraph.getLeftNodeNumber(); i++) {

y = yOffset * (i + 1);

g.drawOval(leftXOffset, y, Constants.NODE_WIDTH, Constants.NODE_HEIGHT);

}

}

private void drawRightNodes(Graphics g) {

int y;

for (int i = 0; i < bipartiteGraph.getRightNodeNumber(); i++) {

y = yOffset * (i + 1);

g.drawOval(rightXOffset, y, Constants.NODE_WIDTH, Constants.NODE_HEIGHT);

}

}

private void drawEdges(Graphics g) {

for (int i = 0; i < bipartiteGraph.getLeftNodeNumber(); i++) {

for (int j = 0; j < bipartiteGraph.getRightNodeNumber(); j++) {

if (graph[i][j] == 1) {

drawEdge(g, i, j);

}

}

}

for (int match : bipartiteGraph.getMaxMatch()) {

if (match != -1) {

drawEdgeColored(g, match, bipartiteGraph.getMaxMatch().indexOf(match));

}

}

}

private void drawEdge(Graphics g, int leftNodeIndex, int rightNodeIndex) {

int y1 = yOffset * (leftNodeIndex + 1) + (Constants.NODE_HEIGHT / 2);

int y2 = yOffset * (rightNodeIndex + 1) + (Constants.NODE_HEIGHT / 2);

int x1 = leftXOffset + Constants.NODE_WIDTH;

g.drawLine(x1, y1, rightXOffset, y2);

}

private void drawEdgeColored(Graphics g, int leftNodeIndex, int rightNodeIndex) {

g.setColor(Color.RED);

drawEdge(g, leftNodeIndex, rightNodeIndex);

g.setColor(Color.BLACK);

}

private void drawMatchNumber(Graphics g) {

g.drawString(Constants.MATCH_SIZE_TEXT + bipartiteGraph.getMatchSize(), 20, 20);

}

}

Заключение

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

Список литературы

двудольный граф паросочетание программа

1. Р.Стивенс - «Алгоритмы. Теория и практическое применение»

2. Ф.Новиков - «Дискретная математика»

3. Электронный ресурс https://ru.wikipedia.org/ дата обращения: 16.11.17