／*若以二维数组存储图信息， 负责度比定为n^2, 采用链表存储*／
基础存储类型为Item(用来存储基本类型)， 需继承Iterable用以顺序访问
public class Bag<Item> implements Iterable<Item> {
private Node<Item> first;
private int n;
private static class Node<Item> { //内部类
private Item first;
private Node<Item> next; //下一个节点
}
public Bag() {
first = null;
n = 0;
}
public int size() { return n; }
public void add (Item item) { //在队首添加
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++
}
public Iterator<Item> iterator() { return new ListIterator<Item>(first) ; } 重写迭代器
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) { current = first; } ;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if(!hasnext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next ;
return item;
}
以下图为例构建无向图
形成图代码
public class Grath {
private final int V;//节点数目， 实例化时赋值
private int E;//边数目， 为0；
private Bag<Integer>[] adj; //链表结构
public Grath(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for(int i =0; i < V; i++) {
adj[V] = new Bag<Integer>();
}
private voidvalidateVertex(int v) { //节点是否有效
if(v<0|| v>V) { throw newIllegalArgumentException("vertex "+ v +" is not between 0 and "+ (V-1)); }
}
public addEdge(int v, int w) {
validateVertex(v);
validateVertex(w);
E++;
adj[v].add(w);
adj[w].add(v);//双向连接
}
public Iterable adj(int v) { //获取某一条链
validateVertex(v);
returnadj[v];
}
深度搜索
public class DepthFirstSearch { /*采用动态规划和递归的方法从一个指定节点所能访问的所有的节点， 若能访问则返回true*/
private boolean[] marked;//用来标志节点是否访问过
private int count;//指定节点所在图的所有节点数目
public DepthFirstSearch(Grapth G, int s) {
marked = new boolean[G.V()];
bfs(G, s); //深度遍历
}
private void dfs(Grapth G, int v) {
marked[v] = true;
count++;
for(int w : G.adj(v))
if(!marked[w] ) dfs (G, w);
}
public boolean marked( int w ) { return marked[w]; }
public int count() { return count; }
}
