import java.util.*;
public class Vertex {
String name;
ArrayList<Edge> edges;
int degree;
public Vertex (String name) {
this.name = name;
this.edges = new ArrayList<Edge>();
this.degree = 0;
}
public String toString() {
return this.name + "(" + degree + ")";
}
public void add_edge(Edge edge) {
edges.add(edge);
degree ++;
}
public static void main (String[] args) {
Graph g = new Graph();
g.add_vertex("A");
g.add_vertex("B");
g.add_vertex("C");
g.add_vertex("D");
g.add_edge("A","B");
g.add_edge("A","B");
g.add_edge("A","D");
g.add_edge("C","B");
g.add_edge("C","B");
g.add_edge("C","D");
g.add_edge("B","D");
System.out.println(g);
}
}
import java.util.*;
public class Edge {
public Vertex vertex1, vertex2;
int weight;
public Edge (Vertex vertex1, Vertex vertex2) {
this.vertex1 = vertex1;
this.vertex2 = vertex2;
this.weight = 1;
}
public Edge (Vertex vertex1, Vertex vertex2, int weight) {
this.vertex1 = vertex1;
this.vertex2 = vertex2;
this.weight = weight;
}
public void setWeight (int weight) {
this.weight = weight;
}
public int getWeight () {
return weight;
}
public boolean containsVertex(Vertex v) {
if (this.vertex1 == v || this.vertex2 == v)
return true;
else
return false;
}
public String toString() {
return this.vertex1.toString() + "←—→" + this.vertex2.toString();
}
}
import java.util.*;
public class Graph {
private HashMap<String, Vertex> vertices;
private ArrayList<Edge> edges;
public Graph() {
this.vertices = new HashMap<String,Vertex>();
this.edges = new ArrayList<Edge>();
}
public void add_vertex(String name) {
if (!vertices.containsKey(name)) {
Vertex vertex = new Vertex(name);
vertices.put(name, vertex);
}
}
public void add_edge (String v1_name, String v2_name) {
Edge edge = new Edge(vertices.get(v1_name),vertices.get(v2_name));
edges.add(edge);
vertices.get(v1_name).add_edge(edge);
vertices.get(v2_name).add_edge(edge);
}
public void add_edge (String v1_name, String v2_name, int weight) {
Edge edge = new Edge(vertices.get(v1_name),vertices.get(v2_name),weight);
edges.add(edge);
vertices.get(v1_name).add_edge(edge);
vertices.get(v2_name).add_edge(edge);
}
public ArrayList<Edge> kruskal() {
this.sortEdges();
ArrayList<Vertex> visited = new ArrayList<Vertex>();
ArrayList<Edge> collected = new ArrayList<Edge>();
for (Edge e : edges) {
if ( visited.indexOf(e.vertex1) == -1 || visited.indexOf(e.vertex2) == -1 ) {
collected.add(e);
if ( visited.indexOf(e.vertex1) == -1 ) visited.add(e.vertex1);
if ( visited.indexOf(e.vertex2) == -1 ) visited.add(e.vertex2);
}
if (visited.size() == vertices.size()) return collected;
}
}
public void sortEdges() {
ArrayList<Edges> temp = new ArrayList<Edges>();
while(edges.size()>0) {
int min = Integer.MAX_VALUE;
int min_index = -1;
for(int i = 0; i < edges.size(); i ++ ) {
if (edges.get(i) < min) {
min = edges.get(i);
min_index = i;
}
}
temp.add( edges.get(min_index) );
edges.remove(min_index);
}
edges.addAll(temp);
}
public String toString() {
String str = "Vertices: ";
for (Map.Entry m :vertices.entrySet())
str += m.getValue() + " ";
str += "\nEdges: ";
for (Edge e : edges) {
str += e.toString() + " ";
}
return str;
}
}
