Nurmuhammedov Muhammadali 4-5-laboratoriya ishlari

Nurmuhammedov Muhammadali
4-5-laboratoriya ishlari

Kruskal algorithms

import java.util.*;

import java.io.*;

public class Kruskal {

public static void main(String[] args) {
ArrayList graphEdges = new ArrayList(); //edge list, not adjacency list
graphEdges.add(new Edge(3, 5, 2));
graphEdges.add(new Edge(6, 7, 5));
graphEdges.add(new Edge(3, 4, 6));
graphEdges.add(new Edge(4, 8, 7));
graphEdges.add(new Edge(1, 2, 9));
graphEdges.add(new Edge(4, 5, 11));
graphEdges.add(new Edge(1, 6, 14));
graphEdges.add(new Edge(1, 7, 15));
graphEdges.add(new Edge(5, 8, 16));
graphEdges.add(new Edge(3, 6, 18));
graphEdges.add(new Edge(3, 8, 19));
graphEdges.add(new Edge(7, 5, 20));
graphEdges.add(new Edge(2, 3, 24));
graphEdges.add(new Edge(7, 8, 44)); //Edges created in almost sorted order, only the last 2 are switched but this is unnecessary as edges are sorted in the algorithm
graphEdges.add(new Edge(6, 5, 30));

int nodeCount = 8; //how many nodes. NODE COUNT MUST BE ENTERED MANUALLY. No error handling between nodeCount and graphEdges

Kruskal graph = new Kruskal(); //CAREFUL: nodeCount must be correct. No error checking between nodeCount & graphEdges to see how many nodes actually exist
graph.kruskalMST(graphEdges, nodeCount);
}

public void kruskalMST(ArrayList graphEdges, int nodeCount){

String outputMessage="";

Collections.sort(graphEdges); //sort edges with smallest weight 1st

ArrayList mstEdges = new ArrayList(); //list of edges included in the Minimum spanning tree (initially empty)

DisjointSet nodeSet = new DisjointSet(nodeCount+1); //Initialize singleton sets for each node in graph. (nodeCount +1) to account for arrays indexing from 0

for(int i=0; i Edge currentEdge = graphEdges.get(i);
int root1 = nodeSet.find(currentEdge.getVertex1()); //Find root of 1 vertex of the edge
int root2 = nodeSet.find(currentEdge.getVertex2());
outputMessage+="find("+currentEdge.getVertex1()+") returns "+root1+", find("+currentEdge.getVertex2()+") returns "+root2; //just print, keep on same line for union message
String unionMessage=",\tNo union performed\n"; //assume no union is to be performed, changed later if a union DOES happen
if(root1 != root2){ //if roots are in different sets the DO NOT create a cycle
mstEdges.add(currentEdge); //add the edge to the graph
nodeSet.union(root1, root2); //union the sets
unionMessage=",\tUnion("+root1+", "+root2+") done\n"; //change what's printed if a union IS performed
}
outputMessage+=unionMessage;
}

outputMessage+="\nFinal Minimum Spanning Tree ("+mstEdges.size()+" edges)\n";

int mstTotalEdgeWeight=0;
for(Edge edge: mstEdges){
outputMessage+=edge +"\n"; //print each edge
mstTotalEdgeWeight += edge.getWeight();
}
outputMessage+="\nTotal weight of all edges in MST = "+mstTotalEdgeWeight;

System.out.println(outputMessage);

try (PrintWriter outputFile = new PrintWriter( new File("06outputMST.txt") ); ){
outputFile.println(outputMessage);
System.out.println("\nOpen \"06outputMST.txt\" for backup copy of answers");
} catch (FileNotFoundException e) {
System.out.println("Error! Couldn't create file");
}
}
}

class Edge implements Comparable{

private int vertex1; //an edge has 2 vertices & a weight
private int vertex2;
private int weight;

public Edge(int vertex1, int vertex2, int weight){

this.vertex1=vertex1;
this.vertex2=vertex2;
this.weight=weight;
}

public int getVertex1(){

return vertex1;
}

public int getVertex2(){

return vertex2;
}

public int getWeight(){

return weight;
}

@Override

public int compareTo(Edge otherEdge) { //Compare based on edge weight (for sorting)
return this.getWeight() - otherEdge.getWeight();
}

@Override

public String toString() {
return "Edge ("+getVertex1()+", "+getVertex2()+") weight="+getWeight();
}
}

// DisjointSet class

//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union(root1, root2) --> Merge two sets
// int find(x) --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed
// http://users.cis.fiu.edu/~weiss/dsaajava3/code/DisjSets.java

/**
* Disjoint set class, using union by rank and path compression

* Elements in the set are numbered starting at 0
* @author Mark Allen Weiss
*/
class DisjointSet{
private int[] set; //the disjoint set as an array

public int[] getSet(){ //mostly debugging method to print array

return set;
}

/**
* Construct the disjoint sets object.

* @param numElements the initial number of disjoint sets.
*/
public DisjointSet(int numElements) { //constructor creates singleton sets
set = new int [numElements];
for(int i = 0; i < set.length; i++){ //initialize to -1 so the trees have nothing in them
set[i] = -1;
}
}

/**
* Union two disjoint sets using the height heuristic.

* For simplicity, we assume root1 and root2 are distinct
* and represent set names.
* @param root1 the root of set 1.
* @param root2 the root of set 2.
*/
public void union(int root1, int root2) {
if(set[root2] < set[root1]){ // root2 is deeper
set[root1] = root2; // Make root2 new root
}
else {
if(set[root1] == set[root2]){
set[root1]--; // Update height if same
}
set[root2] = root1; // Make root1 new root
}
}

/**
* Perform a find with path compression.

* Error checks omitted again for simplicity.
* @param x the element being searched for.
* @return the set containing x.
*/
public int find(int x) {
if(set[x] < 0){ //If tree is a root, return its index
return x;
}
int next = x;
while(set[next] > 0){ //Loop until we find a root
next=set[next];
}
return next;
}

}

Prim algorithm

import sys # Library for INT_MAX
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
# A utility function to print the constructed MST stored in parent[]
def printMST(self, parent):
print ("Edge \tWeight")
for i in range(1, self.V):
print (parent[i], "-", i, "\t", self.graph[i][parent[i]])
# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minKey(self, key, mstSet):
# Initialize min value
min = sys.maxsize
for v in range(self.V):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v
return min_index
# Function to construct and print MST for a graph
# represented using adjacency matrix representation
def primMST(self):
# Key values used to pick minimum weight edge in cut
key = [sys.maxsize] * self.V
parent = [None] * self.V # Array to store constructed MST
# Make key 0 so that this vertex is picked as first vertex
key[0] = 0
mstSet = [False] * self.V
parent[0] = -1 # First node is always the root of
for cout in range(self.V):
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minKey(key, mstSet)
# Put the minimum distance vertex in
# the shortest path tree
mstSet[u] = True
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for v in range(self.V):
# graph[u][v] is non zero only for adjacent vertices of m
# mstSet[v] is false for vertices not yet included in MST
# Update the key only if graph[u][v] is smaller than key[v]
if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
self.printMST(parent)
g = Graph(5)
g.graph = [ [0, 5, 0, 0, 0, 8],
[5, 0, 7, 0, 9, 0],
[0, 7, 0, 10, 6, 0],
[0, 9, 10, 0, 0, 12],
[0, 9, 6, 0, 0, 4],
[8, 0, 0, 12, 4, 0]]
g.primMST();