数据结构
数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense graph）
我写的带权的稠密图所以另外定义一个类Edge:
类Edge
public class Edge {
private int a,b;
private int weight;
private boolean isEmpty;
public Edge() {
this.isEmpty=true;
}
public Edge(int a, int b, int weight) {
this.a = a;
this.b = b;
this.weight = weight;
}
public int v(){
return a;
}
public int w(){
return b;
}
public int wt(){
return weight;
}
public int other(int x){
assert(x==a||x==b);
return x==a?b:a;
}
public boolean isEmpty(){
return this.isEmpty;
}
类DenseGraph
//稠密图--邻接矩阵
public class DenseGraph{
private int n,m; //顶点，边
private boolean isdirected; //是否有向图
private ArrayList<ArrayList<Edge>> g=new ArrayList<ArrayList<Edge>>(); //二维矩阵
public DenseGraph(int n, boolean isdirected) {
this.n = n;
this.m=0; //边
this.isdirected = isdirected;
for(int i=0;i<n;i++){
ArrayList<Edge> arr=new ArrayList<Edge>(n);
for(int j=0;j<n;j++)
arr.add(j,new Edge());
g.add(arr);
}
}
public int V(){return n;}
public int E(){return m;}
//添加边
public void addEdge(int v,int w,int weight){
assert(v>=0&&v<n);
assert(w>=0&&w<n);
if(hasEdge(v,w)){
return;
}
ArrayList<Edge> arr=g.get(v);
arr.set(w, new Edge(v,w,weight));
if(!isdirected){ //若不是有向图
ArrayList<Edge> sarr=g.get(w);
sarr.set(v, new Edge(w,v,weight));
}
m++;
}
public ArrayList<Edge> getGraph(int n){
return g.get(n);
}
public boolean hasEdge(int v,int w){
assert(v>=0&&v<n);
assert(w>=0&&w<n);
ArrayList<Edge> arr=g.get(v);
Edge adge=arr.get(w);
return !adge.isEmpty();
}
public static void main(String[] args) {
int N=20; //顶点
int M=100; //边
DenseGraph sg=new DenseGraph(N,false);
for(int i=0;i<M;i++){
sg.addEdge(new Random().nextInt(N), new Random().nextInt(N),new Random().nextInt(10));//权值[0,10)
}
System.out.print(" ");
for(int i=0;i<N;i++){
String s=i>=10?(" "+i):(" "+i);
System.out.print(s);
}
System.out.println();
for(int i=0;i<N;i++){
System.out.print(i+" ");
ArrayList<Edge> srr=sg.getGraph(i);
Iterator<Edge> ite=srr.iterator();
if(i<10)
System.out.print(" ");
while(ite.hasNext()){
System.out.print(" "+ite.next().wt()+" ");
}
System.out.println();
}
}
}
实验结果:
