Завдання. Чорноморський державний університет імені Петра Могили

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Чорноморський державний університет імені Петра Могили

Факультет комп’ютерних наук

Кафедра інформаційних технологій та програмних систем

ЗВІТ

з лабораторної роботи № 8

" Алгоритм Прима-Каскаля "

Варіант № 19

Дисципліна " Теорія алгоритмів"

Спеціальність " Інтелектуальні системи прийняття рішень"

6.050101-ЛР.ПЗ.07-203.08905483

Cтудент _____________ І.В. Семененко

(підпис)

27.05.2014

(дата)

Викладач _____________ І.С.Бурлачен ко

(підпис)

_____________

(дата)

Миколаїв – 2014

Тема: Алгоритм Прима-Краскала.

Завдання

1. Програмно реалізувати алгоритм Прима-Краскала для графа, що наведений на рис 2.

Рис. 2

2. Вагу ребер обрати з таблиці 1 відповідно до свого варіанту

Таблиця 1. Варіанти завдань

3. Результати роботи програми представити у графічному вигляді.

Код програми (java):

<? xml version=" 1.0" encoding=" UTF-8"? >

< graph_data>

< graph id=" 1" >

< title> Graf< /title>

< points>

< point id=" 1" x=" 410" y=" 620" />

< point id=" 2" x=" 220" y=" 520" />

< point id=" 3" x=" 30" y=" 380" />

< point id=" 4" x=" 180" y=" 150" />

< point id=" 5" x=" 390" y=" 40" />

< point id=" 6" x=" 600" y=" 100" />

< point id=" 7" x=" 600" y=" 330" />

< point id=" 8" x=" 795" y=" 200" />

< point id=" 9" x=" 430" y=" 370" />

< point id=" 10" x=" 260" y=" 340" />

< point id=" 11" x=" 450" y=" 200" />

< /points>

< lines>

< line id=" 1" from=" 3" to=" 4" weight=" 24" />

< line id=" 2" from=" 4" to=" 5" weight=" 31" />

< line id=" 3" from=" 5" to=" 11" weight=" 58" />

< line id=" 4" from=" 4" to=" 11" weight=" 26" />

< line id=" 5" from=" 4" to=" 10" weight=" 24" />

< line id=" 6" from=" 3" to=" 10" weight=" 67" />

< line id=" 7" from=" 10" to=" 11" weight=" 4" />

< line id=" 8" from=" 9" to=" 10" weight=" 14" />

< line id=" 9" from=" 9" to=" 11" weight=" 34" />

< line id=" 10" from=" 2" to=" 3" weight=" 56" />

< line id=" 11" from=" 2" to=" 10" weight=" 49" />

< line id=" 12" from=" 2" to=" 9" weight=" 58" />

< line id=" 13" from=" 5" to=" 6" weight=" 43" />

< line id=" 14" from=" 6" to=" 8" weight=" 83" />

< line id=" 15" from=" 1" to=" 2" weight=" 5" />

< line id=" 16" from=" 1" to=" 9" weight=" 14" />

< line id=" 17" from=" 6" to=" 11" weight=" 14" />

< line id=" 18" from=" 6" to=" 7" weight=" 6" />

< line id=" 19" from=" 1" to=" 7" weight=" 65" />

< line id=" 20" from=" 7" to=" 8" weight=" 10" />

< /lines>

< /graph>

< /graph_data>

package newpackage;

/**

*

* @author Ivan

*/

import javax.xml.parsers.SAXParser;

public class Main {

public static void main(String argv[]) {

struct my = new struct(11);

Xml Xm = new Xml(" myxml.xml");

Xm.get();

for (int i = 0; i < Xm.from.length; i++) {

my.add(Xm.from[i], Xm.to[i], Xm.weight[i]);

}

my.add_t(Xm.x, Xm.y);

my.print();

frame fr = new frame(my);

fr.setDefaultCloseOperation(fr.EXIT_ON_CLOSE);

fr.setVisible(true);

}

}

package newpackage;

/**

*

* @author Ivan

*/

import java.io.File;

import javax.xml.parsers.DocumentBuilder;

import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.Document;

import org.w3c.dom.Element;

import org.w3c.dom.Node;

import org.w3c.dom.NodeList;

public class Xml {

int tagCount = 0;

String path;

int x[];

int y[];

int from[];

int to[];

int weight[];

Xml(String t) {

path = t;

}

void get() {

try {

File file = new File(path);

DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();

DocumentBuilder db = dbf.newDocumentBuilder();

Document doc = db.parse(file);

doc.getDocumentElement().normalize();

System.out.println(" Root element " + doc.getDocumentElement().getNodeName());

NodeList nodeLst = doc.getElementsByTagName(" point");

System.out.println(" Information of all employees");

x = new int[nodeLst.getLength()];

y = new int[nodeLst.getLength()];

for (int s = 0; s < nodeLst.getLength(); s++) {

Node fstNode = nodeLst.item(s);

if (fstNode.getNodeType() == Node.ELEMENT_NODE) {

Element fstElmnt = (Element) fstNode;

NodeList fstNmElmntLst = fstElmnt.getElementsByTagName(" x");

Element fstNmElmnt = (Element) fstNmElmntLst.item(0);

NodeList fstNm = fstNmElmnt.getChildNodes();

System.out.print(" (" + ((Node) fstNm.item(0)).getNodeValue() + "; ");

x[s] = Integer.parseInt(((Node) fstNm.item(0)).getNodeValue());

NodeList lstNmElmntLst = fstElmnt.getElementsByTagName(" y");

Element lstNmElmnt = (Element) lstNmElmntLst.item(0);

NodeList lstNm = lstNmElmnt.getChildNodes();

System.out.print(((Node) lstNm.item(0)).getNodeValue()+")");

System.out.print(" ");

y[s] = Integer.parseInt(((Node) lstNm.item(0)).getNodeValue());

}

}

nodeLst = doc.getElementsByTagName(" line");

from = new int[nodeLst.getLength()];

to = new int[nodeLst.getLength()];

weight = new int[nodeLst.getLength()];

System.out.println();

for (int s = 0; s < nodeLst.getLength(); s++) {

Node fstNode = nodeLst.item(s);

if (fstNode.getNodeType() == Node.ELEMENT_NODE) {

Element fstElmnt = (Element) fstNode;

NodeList fstNmElmntLst = fstElmnt.getElementsByTagName(" from");

Element fstNmElmnt = (Element) fstNmElmntLst.item(0);

NodeList fstNm = fstNmElmnt.getChildNodes();

System.out.print(" from - " + ((Node) fstNm.item(0)).getNodeValue() + " ");

from[s] = Integer.parseInt(((Node) fstNm.item(0)).getNodeValue());

NodeList lstNmElmntLst = fstElmnt.getElementsByTagName(" to");

Element lstNmElmnt = (Element) lstNmElmntLst.item(0);

NodeList lstNm = lstNmElmnt.getChildNodes();

System.out.print(" to - " +((Node) lstNm.item(0)).getNodeValue()+" ");

System.out.print(" ");

to[s] = Integer.parseInt(((Node) lstNm.item(0)).getNodeValue());

NodeList sstNmElmntLst = fstElmnt.getElementsByTagName(" weight");

Element sstNmElmnt = (Element) sstNmElmntLst.item(0);

NodeList sstNm = sstNmElmnt.getChildNodes();

System.out.print(" weight - " +((Node) sstNm.item(0)).getNodeValue());

System.out.println();

weight[s] = Integer.parseInt(((Node) sstNm.item(0)).getNodeValue());

}

}

} catch (Exception e) {

e.printStackTrace();

}

}

}

Клас struct:

package newpackage;

/**

*

* @author Ivan

*/

public class struct {

int points[][];

int t_x[];

int t_y[];

int x[];

int y[];

int count[];

int indx;

struct(int count_) {

points = new int[count_][count_];

t_x = new int[count_];

t_y = new int[count_];

x = new int[points[0].length - 1];

y = new int[points[0].length - 1];

count = new int[points[0].length - 1];

for (int i = 0; i < x.length; i++) {

x[i] = -1;

y[i] = -1;

}

indx = 0;

}

void add(int x, int y, int count) {

points[x][y] = count;

points[y][x] = count;

}

void print() {

System.out.println(" Mass: ");

System.out.println();

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

for (int j = 0; j < points[0].length; j++) {

System.out.print(points[i][j] + " ");

}

System.out.println();

}

}

void find() {

int bufer[][] = new int[points[0].length][points[0].length];

if (indx > (points[0].length - 2)) {

return;

}

if (indx == 0) {

bufer = points;

int min = 100;

int minx = 0;

int miny = 0;

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

for (int j = 0; j < points[0].length; j++) {

if ((min > points[i][j]) & & (points[i][j] > 0)) {

min = points[i][j];

minx = i;

miny = j;

}

}

}

x[0] = minx;

y[0] = miny;

count[0] = min;

del(minx);

del(miny);

} else {

int minx = 0;

int miny = 0;

int min = 83;

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

for (int j = 0; j < points[0].length; j++) {

if ((points[j][x[i]] < min) & & (points[j][x[i]]! = 0)) {

min = points[j][x[i]];

minx = j;

miny = x[i];

}

}

}

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

for (int j = 0; j < points[0].length; j++) {

if ((points[j][y[i]] < min) & & (points[j][y[i]]! = 0)) {

min = points[j][y[i]];

minx = j;

miny = y[i];

}

}

}

x[indx] = minx;

y[indx] = miny;

count[indx] = min;

del(minx);

del(miny);

}

System.out.println();

for (int i = 0; i < points[0].length - 1; i++) {

System.out.println(" (" + x[i] + "; " + y[i] + ") -> " + count[i]);

}

System.out.println();

}

void del(int x) {

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

points[x][i] = 0;

}

}

void add_t(int x[], int y[]) {

t_x = new int[x.length];

t_y = new int[y.length];

for (int i = 0; i < x.length; i++) {

t_x[i] = x[i];

t_y[i] = y[i];

}

}

}

Клас frame:

package newpackage;

/**

*

* @author Ivan */

import java.awt.Color;

import java.awt.Graphics;

import java.awt.Graphics2D;

import java.awt.event.ActionEvent;

import java.awt.event.ActionListener;

import javax.swing.JButton;

import javax.swing.JFrame;

public class frame extends JFrame {

struct my;

private JButton but2 = new JButton(" Next step: ");

frame(struct sy) {

super();

my = sy;

this.setSize(750, 500);

this.setLocation(0, 0);

this.getContentPane().setLayout(null);

ActionListener bat2_al = new ActionListener() {

public void actionPerformed(ActionEvent e) {

my.find();

my.indx++;

repaint();

}

};

but2.addActionListener(bat2_al);

but2.setBounds(5, 5, 100, 50);

this.add(but2);

}

public void paint(Graphics g) {

Graphics2D g2 = (Graphics2D) g;

for (int i=0; i< my.points.length; i++){

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

if (my.points[i][j]! =0){

g2.setColor(Color.RED);

g2.drawLine(my.t_x[i]+15, my.t_y[i]+15, my.t_x[j]+15, my.t_y[j]+15);

g2.setColor(Color.darkGray);

g2.drawString(String.valueOf(my.points[i][j]), (my.t_x[i]+my.t_x[j])/2, (my.t_y[i]+my.t_y[j])/2);

}

}

}

for (int i=0; i< my.x.length; i++){

if (my.count[i]! =0){

g2.setColor(Color.RED);

g2.drawLine(my.t_x[my.x[i]]+15, my.t_y[my.x[i]]+15, my.t_x[my.y[i]]+15, my.t_y[my.y[i]]+15);

}

}

for (int i = 0; i < my.t_x.length; i++) {

g2.setColor(Color.BLACK);

for (int j=0; j< my.count.length; j++){

if ((my.x[j] == i) || (my.y[j] == i)){

g2.setColor(Color.BLACK);

}

}

g2.fillOval (my.t_x[i], my.t_y[i], 50, 50);

g2.setColor(Color.BLACK);

for (int j=0; j< my.count.length; j++){

if ((my.x[j] == i) || (my.y[j] == i)){

g2.setColor(Color.WHITE);

}

}

g2.drawString(String.valueOf((i+1)), my.t_x[i]+10, my.t_y[i]+20);

}

}

}

Результат роботи програми:

Висновок: реалізовано программно алгоритм Прима-Краскала відповідно до варіанту. Програмним середовищем було вибрано JAVA. Найдено мінімальне дерево (каскад) загальною вагою 146 одиниць.