响应式中文网站模板,wordpress和vue哪个好,百度教育小程序,免费个人业务网站制作文章目录 带权图1.1带权图的实现1.2 完整代码 带权图 1.1带权图的实现
在无向无权图的基础上#xff0c;增加边的权。
使用TreeMap存储边的权重。
遍历输入文件#xff0c;创建TreeMap adj存储每个节点。每个输入的adj节点链接新的TreeMap#xff0c;存储相邻的边和权重 … 文章目录 带权图1.1带权图的实现1.2 完整代码 带权图 1.1带权图的实现
在无向无权图的基础上增加边的权。
使用TreeMap存储边的权重。
遍历输入文件创建TreeMap adj存储每个节点。每个输入的adj节点链接新的TreeMap存储相邻的边和权重
private TreeMapInteger, Integer[] adj;adj new TreeMap[V];for(int i 0; i V; i )adj[i] new TreeMapInteger, Integer();两条边相连则分别把权重加入各自的邻接表中
adj[a].put(b, weight);
adj[b].put(a, weight);判断两点之间是否有边
public boolean hasEdge(int v, int w){validateVertex(v);validateVertex(w);return adj[v].containsKey(w);
}求相邻的所有节点
public IterableInteger adj(int v){validateVertex(v);return adj[v].keySet();
}求两点的权值
public int getWeight(int v, int w){if(hasEdge(v, w)) return adj[v].get(w);throw new IllegalArgumentException(String.format(No edge %d-%d, v, w));
}移除边
public void removeEdge(int v, int w){validateVertex(v);validateVertex(w);if(adj[v].containsKey(w)) E --;adj[v].remove(w);adj[w].remove(v);
}复制一个图
public Object clone(){try{WeightedGraph cloned (WeightedGraph) super.clone();cloned.adj new TreeMap[V];for(int v 0; v V; v ){cloned.adj[v] new TreeMapInteger, Integer();for(Map.EntryInteger, Integer entry: adj[v].entrySet())cloned.adj[v].put(entry.getKey(), entry.getValue());}return cloned;}catch (CloneNotSupportedException e){e.printStackTrace();}return null;
}1.2 完整代码
package Chapter09_Weight_Graph;import java.io.File;
import java.io.IOException;
import java.util.Map;
import java.util.TreeMap;
import java.util.Scanner;/// 暂时只支持无向带权图
public class WeightedGraph implements Cloneable{private int V;private int E;private TreeMapInteger, Integer[] adj;public WeightedGraph(String filename){File file new File(filename);try(Scanner scanner new Scanner(file)){V scanner.nextInt();if(V 0) throw new IllegalArgumentException(V must be non-negative);adj new TreeMap[V];for(int i 0; i V; i )adj[i] new TreeMapInteger, Integer();E scanner.nextInt();if(E 0) throw new IllegalArgumentException(E must be non-negative);for(int i 0; i E; i ){int a scanner.nextInt();validateVertex(a);int b scanner.nextInt();validateVertex(b);int weight scanner.nextInt();if(a b) throw new IllegalArgumentException(Self Loop is Detected!);if(adj[a].containsKey(b)) throw new IllegalArgumentException(Parallel Edges are Detected!);adj[a].put(b, weight);adj[b].put(a, weight);}}catch(IOException e){e.printStackTrace();}}public void validateVertex(int v){if(v 0 || v V)throw new IllegalArgumentException(vertex v is invalid);}public int V(){return V;}public int E(){return E;}public boolean hasEdge(int v, int w){validateVertex(v);validateVertex(w);return adj[v].containsKey(w);}public IterableInteger adj(int v){validateVertex(v);return adj[v].keySet();}public int getWeight(int v, int w){if(hasEdge(v, w)) return adj[v].get(w);throw new IllegalArgumentException(String.format(No edge %d-%d, v, w));}public int degree(int v){validateVertex(v);return adj[v].size();}public void removeEdge(int v, int w){validateVertex(v);validateVertex(w);if(adj[v].containsKey(w)) E --;adj[v].remove(w);adj[w].remove(v);}Overridepublic Object clone(){try{WeightedGraph cloned (WeightedGraph) super.clone();cloned.adj new TreeMap[V];for(int v 0; v V; v ){cloned.adj[v] new TreeMapInteger, Integer();for(Map.EntryInteger, Integer entry: adj[v].entrySet())cloned.adj[v].put(entry.getKey(), entry.getValue());}return cloned;}catch (CloneNotSupportedException e){e.printStackTrace();}return null;}Overridepublic String toString(){StringBuilder sb new StringBuilder();sb.append(String.format(V %d, E %d\n, V, E));for(int v 0; v V; v ){sb.append(String.format(%d : , v));for(Map.EntryInteger, Integer entry: adj[v].entrySet())sb.append(String.format((%d: %d) , entry.getKey(), entry.getValue()));sb.append(\n);}return sb.toString();}public static void main(String[] args){WeightedGraph g new WeightedGraph(gw1.txt);System.out.print(g);}
}
