Java数据结构——十字链表+邻接多重表
package graph;
/**
* 十字链表
*
* 邻接表，逆邻接表
* @author 己千之
*/
public class OLGraph {
int vexNum;
int arcNum;
vexNode[] vexs;
class arcNode {
int tailVex;
int headVex;
arcNode headLink;
arcNode tailLink;
int weight;
}
class vexNode {
char data;
arcNode firstIn;
arcNode firstOut;
}
static class Edge {
char start;
char end;
int weight;
public Edge(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
/**
* 构造方法，构造有向图
*
* @param vertex
* @param edge
*/
public OLGraph(char[] vertex, Edge[] edge) {
// 1.初始成员变量
vexNum = vertex.length;
arcNum = edge.length;
vexs = new vexNode[vexNum];
// 1.1 初始化顶点数组
for(int i=0; i<vexNum; i++) {
vexs[i] = new vexNode();
vexs[i].data = vertex[i];
vexs[i].firstIn = null;
vexs[i].firstOut = null;
}
// 1.2 初始化边
for(int i=0; i<arcNum; i++) {
// 1.2.1 计算两个顶点的位置（弧头，弧尾）
char start = edge[i].start;
char end = edge[i].end;
int index1 = indexOfVex(start);
int index2 = indexOfVex(end);
// 1.2.2 声明两个arcNode型的结点,eg:A-->B
arcNode node1 = new arcNode();
arcNode node2 = new arcNode();
// 1.2.3 链接node1
// 1.2.3.1 tailVex,headVex 指示弧头，弧尾在图中的位置
node1.tailVex = index1;
node1.headVex = index2;
// 1.2.3.2
// tailLink: 指向弧尾相同的下一条弧
// firstout: 指向以该顶点为弧尾的第一个弧结点
node1.tailLink = vexs[index1].firstOut;
vexs[index1].firstOut = node1;
// 1.2.4 链接node2,同理
node2.tailVex = index1;
node2.headVex = index2;
node2.headLink = vexs[index2].firstIn;
vexs[index2].firstIn = node2;
}
} // structure
/**
* 定位顶点的位置
*
* @param v
* @return
*/
public int indexOfVex(char v) {
// 定位顶点的位置
for (int i = 0; i < vexs.length; i++) {
if (vexs[i].data == v)
return i;
}
return -1;
} // indexOfVex
/**
* 打印
* 邻接表，逆邻接表
*/
public void printOLGraph() {
// 邻接表
System.out.println("邻接表：（出度）");
for(int i=0; i<vexNum; i++) {
// 1.打印顶点
System.out.print(vexs[i].data + "--->");
// 2.打印挂接链表(eg:A-->B)
// 2.1 firstout: 指向以该顶点为弧尾的第一个弧结点(A-->)
if(vexs[i].firstOut != null) {
// 2.1.1 打印vexs[i]所指的那个结点的data
// headVex: 以它为弧头的顶点的下标
// :(就是B的下标)
arcNode tempNode = new arcNode();
tempNode = vexs[i].firstOut;
System.out.print(vexs[tempNode.headVex].data + "-->");
// 2.1.2 后移(eg:A--->B-->C,挂接了两个顶点)
// tailLink: 指向弧尾相同的下一条弧(B-->C)
while(tempNode.tailLink != null) {
tempNode = tempNode.tailLink;
System.out.print(vexs[tempNode.headVex].data + "-->");
} // end while
System.out.print("NULL");
System.out.println();
} // end if
else {
System.out.println();
}
} // end for
// 逆邻接表,同理
System.out.println("逆邻接表：（入度）");
for(int i=0; i<vexNum; i++) {
// 1.打印顶点
System.out.print(vexs[i].data + "<---");
// 2.打印挂接链表
if(vexs[i].firstIn != null) {
arcNode tempNode = new arcNode();
tempNode = vexs[i].firstIn;
System.out.print(vexs[tempNode.tailVex].data + "<--");
while(tempNode.headLink != null) {
tempNode = tempNode.headLink;
System.out.print(vexs[tempNode.tailVex].data + "<--");
} // end while
System.out.print("NULL");
System.out.println();
} // end if
else {
System.out.println();
}
} // end for
} // printOLGraph
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
// 1.顶点集
char[] vexs = { 'A', 'B', 'C', 'D'};
// 2.边集
Edge[] edges = {
new Edge('A', 'B', 10),
new Edge('A', 'C', 10),
new Edge('A', 'D', 10),
new Edge('B', 'D', 20),
new Edge('C', 'D', 30)
};
OLGraph olgraph = new OLGraph(vexs, edges);
// 打印图的邻接表
olgraph.printOLGraph();
}
} // OLGraph