图算法， 无向图

／*若以二维数组存储图信息， 负责度比定为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; }

}