1
這是針對java中的數據結構類，我需要創建一個讀取文本輸入的圖形，將此信息轉換爲圖形，然後從那裏打印鄰接列表並打印一個最大生成樹，我已經完成了。然而，最後一個方面是查找圖表和打印路由的最短路徑表
您的程序必須產生的完整路由表將有網絡中每臺計算機對[i，j]（i！= j），第一臺計算機處於最佳狀態從i到j的路線。如果我和j有直接連接，那麼j將是該路線（對[i，j]）的結果（表格條目）。如果從i到j的最佳路線是i→a→b→j，那麼a將是該路線的結果（表格條目）。然後可以通過查看[i，j]（= a），然後[a，j]（= b），然後[b，j]（= j）的值來構建路線。
所以基本上是Dijksta的算法。但是，我不能使用任何處理圖的Java API（所有其他的都是允許的）。到目前爲止，我有
import java.util.ArrayList;
//import java.util.Stack;
public class Graph2 {
ArrayList<Vertex> vert = new ArrayList<Vertex>();
private static int counter = 0;
private int edges;
private Edge[] allEdges = new Edge[50];
private class Vertex{
String ip;
private int id;
ArrayList<Edge> nb = new ArrayList<Edge>();
/**
* Constructor for Vertex
* @param String of IP
*/
public Vertex(String s){
ip = s;
id = counter;
counter++;
}
/**
* Gets the ID of a vertex
* @return unique ID
*/
public int getId(){
return id;
}
/*
public boolean isSame(Vertex v){
if(this.ip.equals(v.getIp()))
return true;
else
return false;
}
*/
/**
* Gets the IP of a vertex
* @return the IP of the vertex
*/
public String getIp(){
return this.ip;
}
/**
* Adds an edge to nb
* @param edge to be added
*/
public void addList(Edge e){
nb.add(e);
}
/**
* Determines if an edge exists
* @param edge to be checked
* @return true if exists, false if not
*/
public boolean exists(Edge e){
if(nb.indexOf(e) != -1){
return true;
}
else
return false;
}
/**
* Gets the size of an edge
* @return size of edge
*/
public int edgeSize(){
return nb.size();
}
/**
* Gets the edges
* @return String of edges
*/
public String getEdges(){
String all = "";
Edge e;
for(int i = 0; i < nb.size(); i++){
e = nb.get(i);
int ti = this.getId();
int fin = e.getFinish().getId();
if(ti == fin)
all += e.getStart().getId() + " ";
else
all += e.getFinish().getId() + " ";
}
return all;
}
/**
* Overrides toString method
* @return ID and IP of vertex
*/
public String toString(){
return id + " " + " " + ip;
}
}
private class Edge{
int weight;
Vertex finish;
Vertex start;
/**
* Constructor of Edge
* @param vertex 1, start vertex
* @param vertex 2, endpoint vertex
* @param weight of edge
*/
public Edge(Vertex v, Vertex v2, int w){
start = v;
finish = v2;
weight = w;
}
/**
* Gets the start of an edge
* @return edge start
*/
public Vertex getStart(){
return start;
}
/**
* Gets the endpoint of an edge
* @return endpoint of edge
*/
public Vertex getFinish(){
return finish;
}
/**
* Gets the weight of an edge
* @return weight of edge
*/
public int getWeight(){
return weight;
}
/**
* Overrides toString
* @return start of edge and endpoint of edge
*/
public String toString(){
return start + " " + finish;
}
}
/**
* Adds an edge to 2 verticies
* @param s, starting vertex IP
* @param t, enpoint vertex IP
* @param w, weight of edge
*/
public void add(String s, String t, int w){
Vertex v3, v4;
v3 = exists(new Vertex(s));
v4 = exists(new Vertex(t));
Edge e;
if(v3 == null && v4 == null){
v3 = new Vertex(s);
v4 = new Vertex(t);
vert.add(v3);
vert.add(v4);
e = new Edge(v3, v4, w);
v3.addList(e);
v4.addList(e);
}
else if(v3 != null && v4 == null){
counter--;
v4 = new Vertex(t);
vert.add(v4);
e = new Edge(v3, v4, w);
v3.addList(e);
v4.addList(e);
}
else if(v3 == null && v4 !=null){
counter--;
v3 = new Vertex(s);
vert.add(v3);
e = new Edge(v3, v4, w);
v3.addList(e);
v4.addList(e);
}
else{
counter -= 2;
e = new Edge(v3, v4, w);
if(!v3.exists(e)){
v3.addList(e);
v4.addList(e);
}
}
allEdges[edges] = e;
edges++;
}
/**
* Determines if an edge already exists
* @param vertex to be checked
* @return vertex if exists, null if not
*/
public Vertex exists(Vertex v){
for(int i = 0; i < vert.size(); i++){
if(v.getIp().equals(vert.get(i).getIp()))
return vert.get(i);
}
counter--;
return null;
}
/**
* Puts vert ArrayList into an array
* @return String array of vert
*/
public String[] toArray(){
String[] all = new String[vert.size()];
for(int i = 0; i < vert.size(); i++){
all[i] = vert.get(i).toString();
}
return all;
}
/**
* Determines if a vertex is adjacent to another vertex
* @return String array of adjacent verticies
*/
public String[] adjaceny(){
String[] all = new String[vert.size()];
Vertex v1;
for(int i = 0; i < vert.size(); i++){
v1 = vert.get(i);
all[i] = v1.getEdges();
}
return all;
}
/**
* Determines which vertex is in which cluster
* @return String array of clusters
*/
/*
public String[] cluster(){
Vertex[] temp = (Vertex[]) vert.toArray();
Sorter sort = new Sorter();
sort.heapsort(temp);
String[] cluster = new String[vert.size()];
int[] verts = new int[vert.size()];
for(int i = 0; i < vert.size();i++)
verts[i] = i;
return null;
}
*/
/**
* Gets the max spanning tree of the graph
* @return spanning tree of graph
*/
public String[] maxTree(){
sortEdges();
String[] max = new String[vert.size() -1];
Edge e;
for(int i = 0; i < vert.size()-1; i++){
e = allEdges[i];
max[i] = e.getStart().getId() + ", " + e.getFinish().getId() + ", " + e.getWeight();
}
return max;
}
/**
* Sorts edges by max weight
*/
private void sortEdges(){
Sorter sort = new Sorter();
sort.heapsort(allEdges);
}
public class Sorter{
/**
* Heapsorts the Object array
* @param Object array to be sorted
*/
public void heapsort(Object[] a)
{
for(int i = edges/2; i >= 0; i--) /* buildHeap */
percDown(a, i, edges);
for(int i = edges - 1; i > 0; i--)
{
swapReferences(a, 0, i); /* deleteMax */
percDown(a, 0, i);
}
}
/**
* Performs swapping of elements
* @param Object array
* @param index1
* @param index2
*/
public void swapReferences(Object[] a, int index1, int index2)
{
if(a[0] instanceof Edge){
Edge tmp = (Edge)a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
else if(a[0] instanceof Vertex){
Vertex temp = (Vertex)a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
}
/**
* Internal method for heapsort.
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private int leftChild(int i)
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* @param a an array of Comparable items.
* @int i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private void percDown(Object[] a, int i, int n)
{
int child;
if(a[0] instanceof Edge){
Edge tmp;
for(tmp = (Edge) a[i]; leftChild(i) < n; i = child)
{
child = leftChild(i);
if(child != n - 1 && ((Edge)a[child]).getWeight() - ((Edge)(a[child + 1])).getWeight() > 0)
child++;
if(tmp.getWeight() - ((Edge)a[child]).getWeight() > 0)
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
else if(a[0] instanceof Vertex){
Vertex temp;
for(temp = (Vertex) a[i]; leftChild(i) < n; i = child){
child = leftChild(i);
if(child != n-1 && ((Vertex)a[child]).edgeSize() - ((Vertex)a[child+1]).edgeSize() > 0)
child++;
if(temp.edgeSize() - ((Vertex)a[child]).edgeSize() > 0)
a[i] = a[child];
else
break;
}
a[i] = temp;
}
}
}
}
}
隨着主要包括：
import java.util.*;
import java.io.*;
public class pg6main {
public static void main(String[] args) throws IOException{
String filename;
String first, second;
int weight;
Graph2 graph = new Graph2();
Scanner kb = new Scanner(System.in);
boolean go = false;
Scanner infile = null;
PrintWriter outfile = new PrintWriter(new FileWriter("results.txt"));
do{
try{
System.out.print("Enter a file to read from: ");
filename = kb.nextLine();
infile = new Scanner(new FileReader(filename));
}catch(Exception e){
go = true;
System.out.println("file doesn't exist");
}
}while(go);
while(infile.hasNext()){
first = infile.next().trim();
second = infile.next().trim();
weight = Integer.parseInt(infile.nextLine().trim());
graph.add(first, second, weight);
}
outfile.println("IP and their unique IDs: ");
String[] a = graph.toArray();
for(int i = 0; i < a.length; i++)
outfile.println(a[i]);
outfile.println("Adjaceny List: ");
String[] adj = graph.adjaceny();
for(int j = 0; j < adj.length; j++)
outfile.println(j + ": " + adj[j]);
outfile.println("Max spanning tree: ");
String[] max = graph.maxTree();
for(int k = 0; k < max.length; k++)
outfile.println("(" + max[k] + ") ");
/*
//Attempting to do clusters based on length of string of neighbors, does not work
for(int x = 0; x < adj.length; x++){
if(adj[x].length() > adj[x+1].length()){
outfile.println("WHAT I DID: " + adj[x]);
}
else if(adj[x].length() == adj[x+1].length()){
adj[x] = adj[x+1];
outfile.println("WHAT I DID: " + adj[x]);
}
else if(adj[x].length() < adj[x+1].length()){
adj[x] = adj[x+1];
outfile.println("WHAT I DID: " + adj[x]);
}
*/
/*//Attempted to do neighbors slighly different way
String[] cluster = graph.cluster();
for(int x = 0; x < cluster.length; x++){
if(cluster[x] != null)
outfile.println(cluster[x]);
*/
outfile.close();
}//end main
}//end pg6main
我在想，如果有人可以幫助，我從來沒有使用圖形工作直到今天。到目前爲止，我相信我的代碼可以按照預期工作，但是我的邏輯可能會有一些錯誤。基本上我的問題是Dijkstra的大部分實現都有參數作爲圖形，我不確定這實際上是我應該如何做的。謝謝你的幫助。
所以你想讓別人檢查你的作業嗎？ – PengOne 2011-12-15 23:43:44
不，我很確定我有什麼作品;我只是不知道Dijkstra的使用verticies/edges作爲參數的正確實現 – xgbpackersx 2011-12-15 23:45:28