Graph 图-邻接表法
程序员文章站
2024-01-19 13:01:52
...
用邻接表法表示的双向图(改单向容易,只要修改connect,disconect方法)。
此处只是表示数据结构,没有相关算法。
其中Vertex是辅助类表示顶点,其中包含一个boolean变量isVisited表示是否遍历过。
Graph表示图,实际存储顶点,以及顶点之间的关系,用一个数组存储顶点,另一个数组中存放与对应的顶点的相连的的顶点的下标。
大部分的代码实际是辅助代码,其中包括:
Vertex:顶点,其中包含一个Boolean变量,表示是否遍历过。
Node,Link:一个单向链表,存储与当前顶点向邻的节点的下标。(单向链表的详细描述见:Link )
Graph的另一个实现请参见Graph 。
class Vertex {
private Object value;
private boolean isVisited;
Vertex(Object value) {
this.value = value;
}
void visit() { isVisited = true; }
boolean isVisited() { return isVisited; }
}
class Node {
private int index;
private Node next;
Node(int index) { this.index = index; }
void next(Node next) { this.next = next; }
Node next() { return next; }
int index() { return index; }
}
class Link {
private Node first;
private Node current;
void add(int index) {
Node node = new Node(index);
node.next(first);
first = node;
}
boolean hasNext() {
return current == null?
first != null:
current.next() != null;
}
Node next() {
if(current == null)current = first;
else current = current.next();
return current;
}
void reset() { current = null; }
void remove(int index) {
Node previous = null;
Node current = first;
while(current != null) {
if (current.index() == index) {
if(previous == null) first = current;
else previous.next(current.next());
return;
}
previous = current;
current = current.next();
}
}
}
class Graph {
private Vertex[] vertexs;
private Link[] adjTab;
private int pos = -1;
Graph(int size) {
vertexs = new Vertex[size];
adjTab = new Link[size];
}
void add(Object obj) {
assert pos < vertexs.length;
vertexs[++pos] = new Vertex(obj);
}
void connect(int from, int to) {
adjTab[from].add(to);
adjTab[to].add(from);
}
void disConnect(int from, int to) {
adjTab[from].remove(to);
adjTab[to].remove(from);
}
}