图之邻接多重表
package ;
import ;
/**
* @description 利用邻接多重表构建无向图
* @author sky
* @date 2016/12/30
*/
public class AdjacencyMultilistGragh {
@SuppressWarnings("unused")
private static class EdgeBox{
boolean mark; //标志域，标记边是否被搜索过
int iVex, jVex; //顶点域，指示边的两个顶点的位置
EdgeBox iLink; //边域，指示依附于顶点iVex的下一条边
EdgeBox jLInk; //边域，指示依附于顶点jVex的下一条边
int value; //边的信息，如权重
public EdgeBox(boolean mark, int iVex, int jVex, EdgeBox iLink,
EdgeBox jLInk, int value) {
super();
this.mark = mark;
this.iVex = iVex;
this.jVex = jVex;
this.iLink = iLink;
this.jLInk = jLInk;
this.value = value;
}
public boolean isMark() {
return mark;
}
public void setMark(boolean mark) {
this.mark = mark;
}
public int getiVex() {
return iVex;
}
public void setiVex(int iVex) {
this.iVex = iVex;
}
public int getjVex() {
return jVex;
}
public void setjVex(int jVex) {
this.jVex = jVex;
}
public EdgeBox getiLink() {
return iLink;
}
public void setiLink(EdgeBox iLink) {
this.iLink = iLink;
}
public EdgeBox getjLInk() {
return jLInk;
}
public void setjLInk(EdgeBox jLInk) {
this.jLInk = jLInk;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
@SuppressWarnings("unused")
private static class VexBox{
Object data; //顶点信息
EdgeBox firstEdge; //指向第一条依附于该顶点的边
public VexBox(Object data, EdgeBox firstEdge) {
super();
this.data = data;
this.firstEdge = firstEdge;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public EdgeBox getFirstEdge() {
return firstEdge;
}
public void setFirstEdge(EdgeBox firstEdge) {
this.firstEdge = firstEdge;
}
}
private int numVex; //图的当前顶点数
private int numEdge; //图的当前弧数
private VexBox[] adjMulist; //存储表头结点，通常采用顺序存储结构
public AdjacencyMultilistGragh(int numVex, int numEdge, VexBox[] adjMulist) {
super();
this.numVex = numVex;
this.numEdge = numEdge;
this.adjMulist = adjMulist;
}
/**
* @Desciption 采用邻接多重表存储表示，构造有向图
*/
public void createUDG(){
@SuppressWarnings("resource")
Scanner sc = new Scanner();
("请分别输入图的顶点数及边数");
numVex = ();
numEdge = ();
adjMulist = new VexBox[numVex];
("请分别输入图的各个顶点：");
for(int i = 0; i < numVex; i++){
adjMulist[i] = new VexBox((), null);
}
("请输入各个边的起始顶点及其权值value");
for(int k = 0; k < numEdge; k++){
int i = locateVex(()); //输入一条弧的始点，即弧尾
int j = locateVex(()); //输入一条弧的终点，即弧头
int value = (); //输入弧的权重
EdgeBox p = new EdgeBox(false, i, j, adjMulist[i].firstEdge, adjMulist[j].firstEdge, value);
adjMulist[i].firstEdge = p;
adjMulist[j].firstEdge = p;
}
}
/**
* @Desciption 返回与传入值相对应的定点位置
*/
public int locateVex(Object vex){
for(int v = 0; v < numVex; v++){
if(adjMulist[v].getData().equals(vex)){
return v;
}
}
return -1;
}
}