数据结构java的实现

转自:http://bea.iteye.com/blog/166347
不知道为什么copy下来发布不完整.
1 树与哈夫曼树


Java代码
package tree;     
    
public class TreeNode {     
    TreeNode llink;     
    TreeNode rlink;     
    int info;     
}    
package tree;     
    
public class Tree {     
    
    TreeNode root;     
    
    public Tree() {     
    }     
    
    public boolean isEmpty() {     
        return root == null;     
    }     
    
    // 插入     
    public void insertBinaryTree(int info) {     
        TreeNode node = new TreeNode();     
        node.info = info;     
        if (root == null) {     
            root = node;     
        } else {     
            TreeNode currentNode = root;     
            TreeNode parent;     
            while (currentNode != null) {     
                parent = currentNode;     
                if (info > currentNode.info) {     
                    currentNode = currentNode.rlink;     
                    if (currentNode == null) {     
                        parent.rlink = node;     
                    }     
                } else if (info < currentNode.info) {     
                    currentNode = currentNode.llink;     
                    if (currentNode == null) {     
                        parent.llink = node;     
                    }     
                }     
            }     
        }     
    }     
    
    // 删除     
    public void treeDelete(int info) {     
        TreeNode tNode = serach(info);     
        TreeNode deleteNode = new TreeNode();     
        TreeNode dNodeChild = new TreeNode();     
        if (tNode == null) {     
            System.out.println("node is not exists");     
        } else if (tNode.llink == null || tNode.rlink == null) {     
            deleteNode = tNode;     
        } else {     
            deleteNode = treeSuccessor(tNode);     
        }     
        if (deleteNode.llink != null) {     
            dNodeChild = deleteNode.llink;     
        } else {     
            dNodeChild = deleteNode.rlink;     
        }     
        if (getFatherNode(deleteNode) == null) {     
            root = dNodeChild;     
        } else {     
            if (deleteNode == getFatherNode(deleteNode).llink) {     
                getFatherNode(deleteNode).llink = dNodeChild;     
            } else {     
                getFatherNode(deleteNode).rlink = dNodeChild;     
            }     
        }     
        if (deleteNode != tNode) {     
            tNode.info = deleteNode.info;     
        }     
    }     
    
    // 搜索     
    public TreeNode serach(int info) {     
        return treeSerach(root, info);     
    }     
    
    // 搜索     
    public TreeNode treeSerach(TreeNode tNode, int info) {     
        if (tNode == null || tNode.info == info) {     
            return tNode;     
        }     
        if (info < tNode.info) {     
            return treeSerach(tNode.llink, info);     
        } else {     
            return treeSerach(tNode.rlink, info);     
        }     
    }     
    
    // 最大节点     
    public TreeNode treeMaxiMum(TreeNode tNode) {     
        while (tNode.rlink != null) {     
            tNode = tNode.rlink;     
        }     
        return tNode;     
    }     
    
    // 最小节点     
    public TreeNode treeMiniMun(TreeNode tNode) {     
        while (tNode.llink != null) {     
            tNode = tNode.llink;     
        }     
        return tNode;     
    }     
    
    // 找后继     
    public TreeNode treeSuccessor(TreeNode tNode) {     
        if (tNode.rlink != null) {     
            return treeMiniMun(tNode.rlink);     
        }     
        TreeNode currentNode = getFatherNode(tNode);     
        while (currentNode != null && tNode == currentNode.rlink) {     
            tNode = currentNode;     
            currentNode = getFatherNode(tNode);     
        }     
        return currentNode;     
    }     
    
    // 找前驱     
    public TreeNode treePrecursor(TreeNode tNode) {     
        if (tNode.llink != null) {     
            return treeMaxiMum(tNode.llink);     
        }     
        TreeNode currentNode = getFatherNode(tNode);     
        while (currentNode != null && tNode == currentNode.llink) {     
            tNode = currentNode;     
            currentNode = getFatherNode(tNode);     
        }     
        return currentNode;     
    }     
    
    // 找节点的父节点     
    public TreeNode getFatherNode(TreeNode tNode) {     
        TreeNode current = root;     
        TreeNode trailCurrent = null;     
        while (current != null) {     
            if (current.info == tNode.info) {     
                break;     
            }     
            trailCurrent = current;     
            if (tNode.info < current.info) {     
                current = current.llink;     
            } else {     
                current = current.rlink;     
            }     
        }     
        return trailCurrent;     
    }     
    
    // 中序遍历     
    public void inOrder(TreeNode tNode) {     
        if (tNode != null) {     
            inOrder(tNode.llink);     
            System.out.print(tNode.info + " ");     
            inOrder(tNode.rlink);     
        }     
    }     
    
    // 打印树     
    public void printTree() {     
        System.out.println("inOrder");     
        inOrder(root);     
        System.out.println();     
        System.out.println("preOrder");     
        preOrder(root);     
        System.out.println();     
        System.out.println("postOrder");     
        postOrder(root);     
        System.out.println();     
    }     
    
    // 前序遍历     
    public void preOrder(TreeNode tNode) {     
        if (tNode != null) {     
            System.out.print(tNode.info + " ");     
            preOrder(tNode.llink);     
            preOrder(tNode.rlink);     
        }     
    }     
    
    // 后序遍历     
    public void postOrder(TreeNode tNode) {     
        if (tNode != null) {     
            postOrder(tNode.llink);     
            postOrder(tNode.rlink);     
            System.out.print(tNode.info + " ");     
        }     
    }     
    
    public static void main(String[] args) {     
        Tree tree = new Tree();     
        System.out.println("insert tree start");     
        tree.insertBinaryTree(15);     
        tree.insertBinaryTree(5);     
        tree.insertBinaryTree(16);     
        tree.insertBinaryTree(3);     
        tree.insertBinaryTree(12);     
        tree.insertBinaryTree(20);     
        tree.insertBinaryTree(10);     
        tree.insertBinaryTree(13);     
        tree.insertBinaryTree(18);     
        tree.insertBinaryTree(23);     
        tree.insertBinaryTree(6);     
        tree.insertBinaryTree(7);     
        System.out.println("insert tree end");     
        System.out.println("print tree start");     
        tree.treeDelete(15);     
        tree.printTree();     
        System.out.println("print tree end");     
    
    }     
}      

package tree;  
 
public class TreeNode {  
    TreeNode llink;  
    TreeNode rlink;  
    int info;  
} 
package tree;  
 
public class Tree {  
 
    TreeNode root;  
 
    public Tree() {  
    }  
 
    public boolean isEmpty() {  
        return root == null;  
    }  
 
    // 插入  
    public void insertBinaryTree(int info) {  
        TreeNode node = new TreeNode();  
        node.info = info;  
        if (root == null) {  
            root = node;  
        } else {  
            TreeNode currentNode = root;  
            TreeNode parent;  
            while (currentNode != null) {  
                parent = currentNode;  
                if (info > currentNode.info) {  
                    currentNode = currentNode.rlink;  
                    if (currentNode == null) {  
                        parent.rlink = node;  
                    }  
                } else if (info < currentNode.info) {  
                    currentNode = currentNode.llink;  
                    if (currentNode == null) {  
                        parent.llink = node;  
                    }  
                }  
            }  
        }  
    }  
 
    // 删除  
    public void treeDelete(int info) {  
        TreeNode tNode = serach(info);  
        TreeNode deleteNode = new TreeNode();  
        TreeNode dNodeChild = new TreeNode();  
        if (tNode == null) {  
            System.out.println("node is not exists");  
        } else if (tNode.llink == null || tNode.rlink == null) {  
            deleteNode = tNode;  
        } else {  
            deleteNode = treeSuccessor(tNode);  
        }  
        if (deleteNode.llink != null) {  
            dNodeChild = deleteNode.llink;  
        } else {  
            dNodeChild = deleteNode.rlink;  
        }  
        if (getFatherNode(deleteNode) == null) {  
            root = dNodeChild;  
        } else {  
            if (deleteNode == getFatherNode(deleteNode).llink) {  
                getFatherNode(deleteNode).llink = dNodeChild;  
            } else {  
                getFatherNode(deleteNode).rlink = dNodeChild;  
            }  
        }  
        if (deleteNode != tNode) {  
            tNode.info = deleteNode.info;  
        }  
    }  
 
    // 搜索  
    public TreeNode serach(int info) {  
        return treeSerach(root, info);  
    }  
 
    // 搜索  
    public TreeNode treeSerach(TreeNode tNode, int info) {  
        if (tNode == null || tNode.info == info) {  
            return tNode;  
        }  
        if (info < tNode.info) {  
            return treeSerach(tNode.llink, info);  
        } else {  
            return treeSerach(tNode.rlink, info);  
        }  
    }  
 
    // 最大节点  
    public TreeNode treeMaxiMum(TreeNode tNode) {  
        while (tNode.rlink != null) {  
            tNode = tNode.rlink;  
        }  
        return tNode;  
    }  
 
    // 最小节点  
    public TreeNode treeMiniMun(TreeNode tNode) {  
        while (tNode.llink != null) {  
            tNode = tNode.llink;  
        }  
        return tNode;  
    }  
 
    // 找后继  
    public TreeNode treeSuccessor(TreeNode tNode) {  
        if (tNode.rlink != null) {  
            return treeMiniMun(tNode.rlink);  
        }  
        TreeNode currentNode = getFatherNode(tNode);  
        while (currentNode != null && tNode == currentNode.rlink) {  
            tNode = currentNode;  
            currentNode = getFatherNode(tNode);  
        }  
        return currentNode;  
    }  
 
    // 找前驱  
    public TreeNode treePrecursor(TreeNode tNode) {  
        if (tNode.llink != null) {  
            return treeMaxiMum(tNode.llink);  
        }  
        TreeNode currentNode = getFatherNode(tNode);  
        while (currentNode != null && tNode == currentNode.llink) {  
            tNode = currentNode;  
            currentNode = getFatherNode(tNode);  
        }  
        return currentNode;  
    }  
 
    // 找节点的父节点  
    public TreeNode getFatherNode(TreeNode tNode) {  
        TreeNode current = root;  
        TreeNode trailCurrent = null;  
        while (current != null) {  
            if (current.info == tNode.info) {  
                break;  
            }  
            trailCurrent = current;  
            if (tNode.info < current.info) {  
                current = current.llink;  
            } else {  
                current = current.rlink;  
            }  
        }  
        return trailCurrent;  
    }  
 
    // 中序遍历  
    public void inOrder(TreeNode tNode) {  
        if (tNode != null) {  
            inOrder(tNode.llink);  
            System.out.print(tNode.info + " ");  
            inOrder(tNode.rlink);  
        }  
    }  
 
    // 打印树  
    public void printTree() {  
        System.out.println("inOrder");  
        inOrder(root);  
        System.out.println();  
        System.out.println("preOrder");  
        preOrder(root);  
        System.out.println();  
        System.out.println("postOrder");  
        postOrder(root);  
        System.out.println();  
    }  
 
    // 前序遍历  
    public void preOrder(TreeNode tNode) {  
        if (tNode != null) {  
            System.out.print(tNode.info + " ");  
            preOrder(tNode.llink);  
            preOrder(tNode.rlink);  
        }  
    }  
 
    // 后序遍历  
    public void postOrder(TreeNode tNode) {  
        if (tNode != null) {  
            postOrder(tNode.llink);  
            postOrder(tNode.rlink);  
            System.out.print(tNode.info + " ");  
        }  
    }  
 
    public static void main(String[] args) {  
        Tree tree = new Tree();  
        System.out.println("insert tree start");  
        tree.insertBinaryTree(15);  
        tree.insertBinaryTree(5);  
        tree.insertBinaryTree(16);  
        tree.insertBinaryTree(3);  
        tree.insertBinaryTree(12);  
        tree.insertBinaryTree(20);  
        tree.insertBinaryTree(10);  
        tree.insertBinaryTree(13);  
        tree.insertBinaryTree(18);  
        tree.insertBinaryTree(23);  
        tree.insertBinaryTree(6);  
        tree.insertBinaryTree(7);  
        System.out.println("insert tree end");  
        System.out.println("print tree start");  
        tree.treeDelete(15);  
        tree.printTree();  
        System.out.println("print tree end");  
 
    }  
}    


Java代码
package tree;     
    
/**   
* @author B.Chen   
*/    
public class HuffmanTree {     
    
    /**   
     * 根节点   
     */    
    public TreeNode root;     
    
    /**   
     * 数组下表   
     */    
    public int nodeSize;     
    
    /**   
     * 长度   
     */    
    public int length;     
    
    /**   
     * 哈夫曼节点数组   
     */    
    public TreeNode[] nodeList;     
         
    /**   
     * 访问控制   
     */    
    public boolean[] visited;     
    
    /**   
     * @param length   
     */    
    public HuffmanTree(int length) {     
        this.length = length;     
        nodeList = new TreeNode[2 * length-1];     
        visited = new boolean[2*length-1];     
    }     
    
    /**   
     * @param info   
     */    
    public void addNode(int info) {     
        TreeNode tNode = new TreeNode();     
        tNode.info = info;     
        if (nodeSize < length) {     
            nodeList[nodeSize++] = tNode;     
        } else {     
            System.out.println("out of size");     
        }     
    }     
         
    /**   
     * 构造哈夫曼树   
     */    
    public void createHuffmanTree() {     
        int j = length;     
        while (nodeList[2*length -2] == null) {     
            TreeNode lNode = getMiniMumNode();     
            TreeNode rNode = getMiniMumNode();     
            TreeNode tNode = new TreeNode();     
            System.out.println(lNode.info + " " + rNode.info);     
            tNode.llink = lNode;     
            tNode.rlink = rNode;     
            tNode.info = lNode.info + rNode.info;     
            nodeList[j++] = tNode;     
        }     
        root = nodeList[2 * length - 2];     
    }     
         
    /**   
     * @return TreeNode   
     */    
    public TreeNode getMiniMumNode() {     
        TreeNode tNode = null;     
        int size = 0;     
        for(int i=0;i<2*length-1;i++) {     
            if(!visited[i] && nodeList[i] != null) {     
                tNode = nodeList[i];     
                size = i;     
                for(int j=0;j<2*length-1;j++) {     
                    if(!visited[j] && nodeList[j] != null) {     
                        if(tNode.info > nodeList[j].info) {     
                            tNode = nodeList[j];     
                            size = j;     
                        }     
                    }     
                }     
            }     
        }     
        visited[size] = true;     
        return tNode;     
    }     
         
    /**   
     * 中序遍历   
     *    
     * @param tNode   
     */    
    public void inOrder(TreeNode tNode) {     
        if (tNode != null) {     
            inOrder(tNode.llink);     
            System.out.print(tNode.info + " ");     
            inOrder(tNode.rlink);     
        }     
    }     
         
    /**   
     * 打印   
     */    
    public void printHuffmanTree() {     
        System.out.println("inOrder");     
        inOrder(root);     
    }     
         
    /**   
     * @param args   
     */    
    public static void main(String[] args) {     
        HuffmanTree hTree = new HuffmanTree(6);     
        hTree.addNode(4);     
        hTree.addNode(4);     
        hTree.addNode(4);     
        hTree.addNode(4);     
        hTree.addNode(5);     
        hTree.addNode(6);     
        hTree.createHuffmanTree();     
        hTree.printHuffmanTree();     
    }     
}   

package tree;  
 
/** 
* @author B.Chen 
*/ 
public class HuffmanTree {  
 
    /** 
     * 根节点 
     */ 
    public TreeNode root;  
 
    /** 
     * 数组下表 
     */ 
    public int nodeSize;  
 
    /** 
     * 长度 
     */ 
    public int length;  
 
    /** 
     * 哈夫曼节点数组 
     */ 
    public TreeNode[] nodeList;  
      
    /** 
     * 访问控制 
     */ 
    public boolean[] visited;  
 
    /** 
     * @param length 
     */ 
    public HuffmanTree(int length) {  
        this.length = length;  
        nodeList = new TreeNode[2 * length-1];  
        visited = new boolean[2*length-1];  
    }  
 
    /** 
     * @param info 
     */ 
    public void addNode(int info) {  
        TreeNode tNode = new TreeNode();  
        tNode.info = info;  
        if (nodeSize < length) {  
            nodeList[nodeSize++] = tNode;  
        } else {  
            System.out.println("out of size");  
        }  
    }  
      
    /** 
     * 构造哈夫曼树 
     */ 
    public void createHuffmanTree() {  
        int j = length;  
        while (nodeList[2*length -2] == null) {  
            TreeNode lNode = getMiniMumNode();  
            TreeNode rNode = getMiniMumNode();  
            TreeNode tNode = new TreeNode();  
            System.out.println(lNode.info + " " + rNode.info);  
            tNode.llink = lNode;  
            tNode.rlink = rNode;  
            tNode.info = lNode.info + rNode.info;  
            nodeList[j++] = tNode;  
        }  
        root = nodeList[2 * length - 2];  
    }  
      
    /** 
     * @return TreeNode 
     */ 
    public TreeNode getMiniMumNode() {  
        TreeNode tNode = null;  
        int size = 0;  
        for(int i=0;i<2*length-1;i++) {  
            if(!visited[i] && nodeList[i] != null) {  
                tNode = nodeList[i];  
                size = i;  
                for(int j=0;j<2*length-1;j++) {  
                    if(!visited[j] && nodeList[j] != null) {  
                        if(tNode.info > nodeList[j].info) {  
                            tNode = nodeList[j];  
                            size = j;  
                        }  
                    }  
                }  
            }  
        }  
        visited[size] = true;  
        return tNode;  
    }  
      
    /** 
     * 中序遍历 
     *  
     * @param tNode 
     */ 
    public void inOrder(TreeNode tNode) {  
        if (tNode != null) {  
            inOrder(tNode.llink);  
            System.out.print(tNode.info + " ");  
            inOrder(tNode.rlink);  
        }  
    }  
      
    /** 
     * 打印 
     */ 
    public void printHuffmanTree() {  
        System.out.println("inOrder");  
        inOrder(root);  
    }  
      
    /** 
     * @param args 
     */ 
    public static void main(String[] args) {  
        HuffmanTree hTree = new HuffmanTree(6);  
        hTree.addNode(4);  
        hTree.addNode(4);  
        hTree.addNode(4);  
        hTree.addNode(4);  
        hTree.addNode(5);  
        hTree.addNode(6);  
        hTree.createHuffmanTree();  
        hTree.printHuffmanTree();  
    }  
} 








在8×8的棋盘上分布着n个骑士，他们想约在某一个格中聚会。骑士每天可以像国际象棋中的马那样移动一次，可以从中间向8个方向移动，请你计算n个骑士的最早聚会地点和要走多少天，要求尽早聚会，且n个人走的总步数最少，先到聚会地点的骑士可以不再移动等待其他的骑士。
从键盘输入n（0<n<=64），然后一次输入n个其实的初始位置xi，yi（0<=xi,y<=7）。屏幕输出以空格分割的三个数，分别为聚会的点（x，y） 以及要走的天数。
　○　○　
○　　　○
　　◎
○　　　○
　○　○　
骑士走法（中间为起始位置，空为走到位置）


Java代码
package convex;     
    
public class Point {     
    
    public int x, y;     
    
    public Point(int x, int y) {     
        if (x > 7 || y > 7) {     
            throw new RuntimeException("out of matrix");     
        }     
        this.x = x;     
        this.y = y;     
    }     
    
    public String toString() {     
        return "x=" + x + ",y=" + y;     
    }     
    
}     
 
 
 
 
package convex;           
       
import java.io.BufferedReader;        
import java.io.IOException;        
import java.io.InputStreamReader;        
import java.util.StringTokenizer;        
       
import convex.Point;           
          
public class Algo {           
       
    private boolean[][] flg = new boolean[8][8];        
       
    private int[][] shortPath = new int[8][8];        
            
    //最短距离矩阵        
    public int[][] distanceSq(Point p1) {        
        djkst(p1);        
        return shortPath;        
    }        
       
    //BFS         
    private void djkst(Point p1) {        
        Point[] queue = new Point[64];        
        flg[p1.x][p1.y] = true;        
        queue[0] = p1;        
        int j=0;        
        int queueSize = 1;        
        while (j < queue.length) {        
                Point temp = queue[j];        
                Point[] list = getList(temp);        
                for(int i=0;i < list.length;i++) {        
                    if(list[i] != null) {        
                        Point w = list[i];        
                        if (!flg[w.x][w.y]) {        
                            shortPath[w.x][w.y] = shortPath[temp.x][temp.y] + 1;                                    
                            queue[queueSize++] = w;        
                            flg[w.x][w.y] = true;        
                        }        
                    }        
                }        
            j++;        
        }        
    }        
       
    //可行步数集           
    private static Point[] getList(Point point) {        
        Point[] list = new Point[8];        
        int length = 0;        
        if (point.x + 2 <= 7 && point.y + 1 <= 7) {        
            list[length++] = new Point(point.x + 2, point.y + 1);        
        }        
        if (point.x - 2 >= 0 && point.y - 1 >= 0) {        
            list[length++] = new Point(point.x - 2, point.y - 1);        
        }        
        if (point.x + 1 <= 7 && point.y + 2 <= 7) {        
            list[length++] = new Point(point.x + 1, point.y + 2);        
        }        
        if (point.x - 1 >= 0 && point.y - 2 >= 0) {        
            list[length++] = new Point(point.x - 1, point.y - 2);        
        }        
        if (point.x + 2 <= 7 && point.y - 1 >= 0) {        
            list[length++] = new Point(point.x + 2, point.y - 1);        
        }        
        if (point.x - 2 >= 0 && point.y + 1 <= 7) {        
            list[length++] = new Point(point.x - 2, point.y + 1);        
        }        
        if (point.x + 1 <= 7 && point.y - 2 >= 0) {        
            list[length++] = new Point(point.x + 1, point.y - 2);        
        }        
        if (point.x - 1 >= 0 && point.y + 2 <= 7) {        
            list[length++] = new Point(point.x - 1, point.y + 2);        
        }        
        return list;        
    }        
            
    public static int[] method(Point[] points, int i,int j,Object[] pointList) {           
        int maxDay = 0;           
        int distance = 0;        
        for(int k=0;k<pointList.length;k++) {        
            int day = ((int[][])pointList[k])[i][j];        
            distance += day;        
            if(maxDay<day) {        
                maxDay = day;        
            }        
        }        
        return new int[]{maxDay,distance};           
    }        
          
    public static void main(String[] args) throws IOException {        
        //数据输入        
        //数据输入格式：第一个数字是骑士n，第2，3个数字是第一个骑士的坐标，依次类推。        
        //每个数字之间以空格区分        
        BufferedReader stdin =         
            new BufferedReader(        
                new InputStreamReader(System.in));        
       
        String line = stdin.readLine();        
        StringTokenizer st = new StringTokenizer(line);        
        int pointLength = Integer.parseInt(st.nextToken());        
        Point[] points = new Point[pointLength];        
        for(int i=0;i<points.length;i++) {        
            int x = Integer.parseInt(st.nextToken());        
            int y = Integer.parseInt(st.nextToken());        
            points[i] = new Point(x,y);        
        }        
        Object[] pointList = new Object[points.length];        
        for (int j = 0; j < points.length; j++) {           
            pointList[j] = new Algo().distanceSq(points[j]);        
        }        
        int minDay = 999999999;        
        int minDistance = 999999999;          
        for(int i=0;i<7;i++) {        
            for(int j=0;j<7;j++) {        
                int[] result = Algo.method(points, i,j,pointList);           
                //找最短天数，最短天数相同，找最短距离        
                if (minDay > result[0]) {        
                    minDay = result[0];        
                    minDistance = result[1];        
                } else if(minDay == result[0]) {        
                    if(minDistance > result[1]) {        
                        minDistance = result[1];        
                    }        
                }        
            }        
        }        
        for(int i=0;i<7;i++) {        
            for(int j=0;j<7;j++) {        
                int[] result = Algo.method(points, i,j,pointList);      
                if(minDay == result[0] && minDistance == result[1]) {     
                    System.out.println(i+" " + j +" "+ minDay);     
                }     
            }     
        }      
    }        
}      

package convex;  
 
public class Point {  
 
    public int x, y;  
 
    public Point(int x, int y) {  
        if (x > 7 || y > 7) {  
            throw new RuntimeException("out of matrix");  
        }  
        this.x = x;  
        this.y = y;  
    }  
 
    public String toString() {  
        return "x=" + x + ",y=" + y;  
    }  
 
}  




package convex;        
    
import java.io.BufferedReader;     
import java.io.IOException;     
import java.io.InputStreamReader;     
import java.util.StringTokenizer;     
    
import convex.Point;        
       
public class Algo {        
    
    private boolean[][] flg = new boolean[8][8];     
    
    private int[][] shortPath = new int[8][8];     
         
    //最短距离矩阵     
    public int[][] distanceSq(Point p1) {     
        djkst(p1);     
        return shortPath;     
    }     
    
    //BFS      
    private void djkst(Point p1) {     
        Point[] queue = new Point[64];     
        flg[p1.x][p1.y] = true;     
        queue[0] = p1;     
        int j=0;     
        int queueSize = 1;     
        while (j < queue.length) {     
                Point temp = queue[j];     
                Point[] list = getList(temp);     
                for(int i=0;i < list.length;i++) {     
                    if(list[i] != null) {     
                        Point w = list[i];     
                        if (!flg[w.x][w.y]) {     
                            shortPath[w.x][w.y] = shortPath[temp.x][temp.y] + 1;                                 
                            queue[queueSize++] = w;     
                            flg[w.x][w.y] = true;     
                        }     
                    }     
                }     
            j++;     
        }     
    }     
    
    //可行步数集        
    private static Point[] getList(Point point) {     
        Point[] list = new Point[8];     
        int length = 0;     
        if (point.x + 2 <= 7 && point.y + 1 <= 7) {     
            list[length++] = new Point(point.x + 2, point.y + 1);     
        }     
        if (point.x - 2 >= 0 && point.y - 1 >= 0) {     
            list[length++] = new Point(point.x - 2, point.y - 1);     
        }     
        if (point.x + 1 <= 7 && point.y + 2 <= 7) {     
            list[length++] = new Point(point.x + 1, point.y + 2);     
        }     
        if (point.x - 1 >= 0 && point.y - 2 >= 0) {     
            list[length++] = new Point(point.x - 1, point.y - 2);     
        }     
        if (point.x + 2 <= 7 && point.y - 1 >= 0) {     
            list[length++] = new Point(point.x + 2, point.y - 1);     
        }     
        if (point.x - 2 >= 0 && point.y + 1 <= 7) {     
            list[length++] = new Point(point.x - 2, point.y + 1);     
        }     
        if (point.x + 1 <= 7 && point.y - 2 >= 0) {     
            list[length++] = new Point(point.x + 1, point.y - 2);     
        }     
        if (point.x - 1 >= 0 && point.y + 2 <= 7) {     
            list[length++] = new Point(point.x - 1, point.y + 2);     
        }     
        return list;     
    }     
         
    public static int[] method(Point[] points, int i,int j,Object[] pointList) {        
        int maxDay = 0;        
        int distance = 0;     
        for(int k=0;k<pointList.length;k++) {     
            int day = ((int[][])pointList[k])[i][j];     
            distance += day;     
            if(maxDay<day) {     
                maxDay = day;     
            }     
        }     
        return new int[]{maxDay,distance};        
    }     
       
    public static void main(String[] args) throws IOException {     
        //数据输入     
        //数据输入格式：第一个数字是骑士n，第2，3个数字是第一个骑士的坐标，依次类推。     
        //每个数字之间以空格区分     
        BufferedReader stdin =      
            new BufferedReader(     
                new InputStreamReader(System.in));     
    
        String line = stdin.readLine();     
        StringTokenizer st = new StringTokenizer(line);     
        int pointLength = Integer.parseInt(st.nextToken());     
        Point[] points = new Point[pointLength];     
        for(int i=0;i<points.length;i++) {     
            int x = Integer.parseInt(st.nextToken());     
            int y = Integer.parseInt(st.nextToken());     
            points[i] = new Point(x,y);     
        }     
        Object[] pointList = new Object[points.length];     
        for (int j = 0; j < points.length; j++) {        
            pointList[j] = new Algo().distanceSq(points[j]);     
        }     
        int minDay = 999999999;     
        int minDistance = 999999999;       
        for(int i=0;i<7;i++) {     
            for(int j=0;j<7;j++) {     
                int[] result = Algo.method(points, i,j,pointList);        
                //找最短天数，最短天数相同，找最短距离     
                if (minDay > result[0]) {     
                    minDay = result[0];     
                    minDistance = result[1];     
                } else if(minDay == result[0]) {     
                    if(minDistance > result[1]) {     
                        minDistance = result[1];     
                    }     
                }     
            }     
        }     
        for(int i=0;i<7;i++) {     
            for(int j=0;j<7;j++) {     
                int[] result = Algo.method(points, i,j,pointList);   
                if(minDay == result[0] && minDistance == result[1]) {  
                    System.out.println(i+" " + j +" "+ minDay);  
                }  
            }  
        }   
    }     
}    






下面开始写数据结构的基本代码：

1 节点类

Java代码
package graph;  
 
public class GraphNode {  
    public GraphNode link;  
    public int info;  
} 

package graph;

public class GraphNode {
public GraphNode link;
public int info;
}


2 邻接表表示图的链表类

Java代码
package graph;  
 
public class GraphList {  
 
    public GraphNode first;  
    public GraphNode last;  
    public boolean visitable;  
    public int getAjd(int[] ajd) {  
        GraphNode current = first;  
        int length = 0;  
        while(current != null) {  
            ajd[length++] = current.info;  
            current = current.link;  
        }  
        return length;  
    }  
    public void addNode(int v) {  
        GraphNode node = new GraphNode();  
        node.info = v;  
        if(first == null) {  
            first = node;  
            last = node;  
        } else {  
            last.link = node;  
            last = node;  
        }  
    }  
} 

package graph;

public class GraphList {

public GraphNode first;
public GraphNode last;
public boolean visitable;
public int getAjd(int[] ajd) {
GraphNode current = first;
int length = 0;
while(current != null) {
ajd[length++] = current.info;
current = current.link;
}
return length;
}
public void addNode(int v) {
GraphNode node = new GraphNode();
node.info = v;
if(first == null) {
first = node;
last = node;
} else {
last.link = node;
last = node;
}
}
}


3 图类



Java代码
package graph;  
 
public class Graph {  
    private int length;  
    private GraphList[] list;  
    public Graph(int length) {  
        this.length = length;  
        list = new GraphList[length];  
    }  
      
    public void dfs(int v) {  
        int[] ajd = new int[length];  
        int ajdlength = list[v].getAjd(ajd);  
        list[v].visitable = true;  
        System.out.print(v+" ");  
        for(int i=0;i<ajdlength;i++) {  
            int w = ajd[i];  
            if(!list[w].visitable) {  
                dfs(w);  
            }  
        }  
    }  
      
    //深度优先遍历  
    public void dfsTravel() {  
        for(int i=0;i<length;i++) {  
            list[i].visitable = false;  
        }  
        for(int i=0;i<length;i++) {  
            if(!list[i].visitable) {  
                dfs(i);  
            }  
        }  
    }  
      
    //广度优先遍历  
    public void bfsTravel() {  
        for(int i=0;i<length;i++) {  
            list[i].visitable = false;  
        }  
        bfs();  
    }  
      
    private void bfs() {  
        Queue queue = new Queue();  
        for(int index=0;index<length;index++) {  
            if(!list[index].visitable) {  
                queue.addQueue(index);  
                list[index].visitable = true;  
                System.out.print(index+" ");  
                while(!queue.isEmpty()) {  
                    int temp = queue.front();  
                    queue.deleteQueue();  
                    int[] adj = new int[length];  
                    int ajdlength = list[temp].getAjd(adj);  
                    for(int i=0;i<ajdlength;i++) {  
                        int w = adj[i];  
                        if(!list[w].visitable) {                              
                            System.out.print(w+" ");  
                            queue.addQueue(w);  
                            list[w].visitable = true;  
                        }  
                    }  
                }  
            }  
              
        }  
    }  
      
    //长度  
    public void length() {  
        System.out.println(length);  
    }  
      
    public boolean isEmpty() {  
        return length == 0;  
    }  
      
    //添加节点  
    public void addGraph(int info) {  
        for(int i=0;i<length;i++) {  
            if(list[i] == null) {  
                GraphList g = new GraphList();  
                g.addNode(info);  
                list[i] = g;  
                break;  
            }  
        }  
    }  
      
    //添加边  
    public void addSide(int vfrom,int vto) {  
        list[vfrom].addNode(vto);  
    }  
      
    //打印图  
    public void print() {  
        for(int i=0;i<length;i++) {  
            GraphNode current = list[i].first;  
            while(current != null) {  
                System.out.print(current.info+" ");  
                current = current.link;  
            }  
            System.out.println();  
        }  
    }  
      
    public static void main(String[] args) {  
        Graph graph = new Graph(11);  
        System.out.println("create graph start");  
        for(int i=0;i<11;i++) {  
            graph.addGraph(i);  
        }  
        graph.addSide(0, 1);  
        graph.addSide(0, 5);  
        graph.addSide(1, 2);  
        graph.addSide(1, 3);  
        graph.addSide(1, 5);  
        graph.addSide(2, 4);  
        graph.addSide(4, 3);  
        graph.addSide(5, 6);          
        graph.addSide(6, 8 );  
        graph.addSide(7, 3);  
        graph.addSide(7, 8 );  
        graph.addSide(8, 10);  
        graph.addSide(9, 4);  
        graph.addSide(9, 7);  
        graph.addSide(9, 10);  
        graph.print();  
        System.out.println("create graph end");  
        graph.bfsTravel();  
    }  
 
} 

package graph;

public class Graph {
private int length;
private GraphList[] list;
public Graph(int length) {
this.length = length;
list = new GraphList[length];
}

public void dfs(int v) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v+" ");
for(int i=0;i<ajdlength;i++) {
int w = ajd[i];
if(!list[w].visitable) {
dfs(w);
}
}
}

//深度优先遍历
public void dfsTravel() {
for(int i=0;i<length;i++) {
list[i].visitable = false;
}
for(int i=0;i<length;i++) {
if(!list[i].visitable) {
dfs(i);
}
}
}

//广度优先遍历
public void bfsTravel() {
for(int i=0;i<length;i++) {
list[i].visitable = false;
}
bfs();
}

private void bfs() {
Queue queue = new Queue();
for(int index=0;index<length;index++) {
if(!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index+" ");
while(!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] adj = new int[length];
int ajdlength = list[temp].getAjd(adj);
for(int i=0;i<ajdlength;i++) {
int w = adj[i];
if(!list[w].visitable) {
System.out.print(w+" ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}

}
}

//长度
public void length() {
System.out.println(length);
}

public boolean isEmpty() {
return length == 0;
}

//添加节点
public void addGraph(int info) {
for(int i=0;i<length;i++) {
if(list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}

//添加边
public void addSide(int vfrom,int vto) {
list[vfrom].addNode(vto);
}

//打印图
public void print() {
for(int i=0;i<length;i++) {
GraphNode current = list[i].first;
while(current != null) {
System.out.print(current.info+" ");
current = current.link;
}
System.out.println();
}
}

public static void main(String[] args) {
Graph graph = new Graph(11);
System.out.println("create graph start");
for(int i=0;i<11;i++) {
graph.addGraph(i);
}
graph.addSide(0, 1);
graph.addSide(0, 5);
graph.addSide(1, 2);
graph.addSide(1, 3);
graph.addSide(1, 5);
graph.addSide(2, 4);
graph.addSide(4, 3);
graph.addSide(5, 6);
graph.addSide(6, 8 );
graph.addSide(7, 3);
graph.addSide(7, 8 );
graph.addSide(8, 10);
graph.addSide(9, 4);
graph.addSide(9, 7);
graph.addSide(9, 10);
graph.print();
System.out.println("create graph end");
graph.bfsTravel();
}

}


4 队列


Java代码
package graph;  
 
public class Queue {  
    public GraphNode first;  
    public GraphNode last;  
    public int count;  
    public void addQueue(int info) {  
        GraphNode node = new GraphNode();  
        node.info = info;  
        if(first == null) {  
            first = node;  
            last = node;  
        } else {  
            last.link = node;  
            last = last.link;  
        }  
        count++;  
    }   
      
    public void deleteQueue() {  
        if(first == null) {  
            System.out.println("null queue");  
        } else {  
            first = first.link;  
            count--;  
        }  
    }  
      
    public boolean isEmpty() {  
        return count == 0;  
    }  
      
    public int front() {  
        if(first == null) {  
            return -1;  
        }  
        return first.info;  
    }  
      
    public int back() {  
        if(last == null) {  
            return -1;  
        }  
        return last.info;  
    }  
} 

package graph;

public class Queue {
public GraphNode first;
public GraphNode last;
public int count;
public void addQueue(int info) {
GraphNode node = new GraphNode();
node.info = info;
if(first == null) {
first = node;
last = node;
} else {
last.link = node;
last = last.link;
}
count++;
}

public void deleteQueue() {
if(first == null) {
System.out.println("null queue");
} else {
first = first.link;
count--;
}
}

public boolean isEmpty() {
return count == 0;
}

public int front() {
if(first == null) {
return -1;
}
return first.info;
}

public int back() {
if(last == null) {
return -1;
}
return last.info;
}
}


5 堆栈


Java代码
package graph;  
 
public class Stack {  
    public GraphNode stackTop;  
    public int count;  
    public void push(int info) {  
        GraphNode node = new GraphNode();  
        node.info = info;  
        node.link = stackTop;  
        stackTop = node;  
        count++;  
    }   
      
    public void pop() {  
        if(stackTop == null) {  
            System.out.println("null stack");  
        } else {  
            stackTop = stackTop.link;  
            count--;  
        }  
 
    }  
      
    public int top() {  
        if(stackTop == null) {  
            return -1;  
        }  
        return stackTop.info;  
    }  
 
} 

package graph;

public class Stack {
public GraphNode stackTop;
public int count;
public void push(int info) {
GraphNode node = new GraphNode();
node.info = info;
node.link = stackTop;
stackTop = node;
count++;
}

public void pop() {
if(stackTop == null) {
System.out.println("null stack");
} else {
stackTop = stackTop.link;
count--;
}

}

public int top() {
if(stackTop == null) {
return -1;
}
return stackTop.info;
}

}


6 图的最短路径算法


Java代码
package graph;  
 
public class Graph {  
    private int length;  
    private GraphList[] list;  
    private int[][] weight;  
 
    public Graph(int length) {  
        this.length = length;  
        list = new GraphList[length];  
        weight = new int[length][length];  
    }  
 
    public void dfs(int v) {  
        int[] ajd = new int[length];  
        int ajdlength = list[v].getAjd(ajd);  
        list[v].visitable = true;  
        System.out.print(v + " ");  
        for (int i = 0; i < ajdlength; i++) {  
            int w = ajd[i];  
            if (!list[w].visitable) {  
                dfs(w);  
            }  
        }  
    }  
 
    // 深度优先遍历  
    public void dfsTravel() {  
        for (int i = 0; i < length; i++) {  
            list[i].visitable = false;  
        }  
        for (int i = 0; i < length; i++) {  
            if (!list[i].visitable) {  
                dfs(i);  
            }  
        }  
    }  
 
    // 广度优先遍历  
    public void bfsTravel() {  
        for (int i = 0; i < length; i++) {  
            list[i].visitable = false;  
        }  
        bfs();  
    }  
 
    private void bfs() {  
        Queue queue = new Queue();  
        for (int index = 0; index < length; index++) {  
            if (!list[index].visitable) {  
                queue.addQueue(index);  
                list[index].visitable = true;  
                System.out.print(index + " ");  
                while (!queue.isEmpty()) {  
                    int temp = queue.front();  
                    queue.deleteQueue();  
                    int[] ajd = new int[length];  
                    int ajdlength = list[temp].getAjd(ajd);  
                    for (int i = 0; i < ajdlength; i++) {  
                        int w = ajd[i];  
                        if (!list[w].visitable) {  
                            System.out.print(w + " ");  
                            queue.addQueue(w);  
                            list[w].visitable = true;  
                        }  
                    }  
                }  
            }  
 
        }  
    }  
 
    // 最短路径  
    private int[] shortPath(int v) {  
        int[] shortPath = new int[length];  
        boolean[] weightFound = new boolean[length];  
        for (int i = 0; i < length; i++) {  
            // 趋近无穷  
            shortPath[i] = 9999;  
            weightFound[i] = false;  
        }  
        shortPath[v] = 0;  
        weightFound[v] = true;  
        Queue queue = new Queue();  
        queue.addQueue(v);  
        while (!queue.isEmpty()) {  
            int temp = queue.front();  
            queue.deleteQueue();  
            int[] ajd = new int[length];  
            int ajdlength = list[temp].getAjd(ajd);  
            for (int i = 0; i < ajdlength; i++) {  
                int w = ajd[i];  
                if (!weightFound[w]) {  
                    if (shortPath[w] > shortPath[temp] + weight[temp][w]) {  
                        shortPath[w] = shortPath[temp] + weight[temp][w];  
                    }  
                }  
            }  
            int minWeightNode = 0;  
            for (int i = 0; i < length; i++) {  
                if (!weightFound[i]) {  
                    minWeightNode = i;  
                    for (int j = 0; j < length; j++) {  
                        if (!weightFound[j]) {  
                            if (shortPath[j] < shortPath[minWeightNode]) {  
                                minWeightNode = j;  
                            }  
                        }  
                    }  
                    break;  
                }  
            }  
            if (!weightFound[minWeightNode]) {  
                weightFound[minWeightNode] = true;  
                queue.addQueue(minWeightNode);  
            }  
        }  
        return shortPath;  
    }  
 
    // 长度  
    public void length() {  
        System.out.println(length);  
    }  
 
    public boolean isEmpty() {  
        return length == 0;  
    }  
 
    // 添加节点  
    public void addGraph(int info) {  
        for (int i = 0; i < length; i++) {  
            if (list[i] == null) {  
                GraphList g = new GraphList();  
                g.addNode(info);  
                list[i] = g;  
                break;  
            }  
        }  
    }  
 
    // 添加边  
    public void addSide(int vfrom, int vto, int value) {  
        list[vfrom].addNode(vto);  
        weight[vfrom][vto] = value;  
    }  
 
    // 打印图  
    public void print() {  
        for (int i = 0; i < length; i++) {  
            GraphNode current = list[i].first;  
            while (current != null) {  
                System.out.print(current.info + " ");  
                current = current.link;  
            }  
            System.out.println();  
        }  
    }  
 
    public static void main(String[] args) {  
        Graph graph = new Graph(5);  
        System.out.println("create graph start");  
        for (int i = 0; i < 5; i++) {  
            graph.addGraph(i);  
        }  
        graph.addSide(0, 1, 16);  
        graph.addSide(0, 3, 2);  
        graph.addSide(0, 4, 3);  
        graph.addSide(3, 4, 7);  
        graph.addSide(3, 1, 12);  
        graph.addSide(4, 1, 10);  
        graph.addSide(4, 3, 5);  
        graph.addSide(4, 2, 4);  
        graph.addSide(2, 1, 3);  
        graph.addSide(1, 2, 5);  
        graph.print();  
        System.out.println("create graph end");  
        int[] shortPath = graph.shortPath(0);  
        for (int i = 0; i < shortPath.length; i++) {  
            System.out.print(shortPath[i] + " ");  
        }  
    }  
 
} 

package graph;

public class Graph {
private int length;
private GraphList[] list;
private int[][] weight;

public Graph(int length) {
this.length = length;
list = new GraphList[length];
weight = new int[length][length];
}

public void dfs(int v) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v + " ");
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
dfs(w);
}
}
}

// 深度优先遍历
public void dfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
for (int i = 0; i < length; i++) {
if (!list[i].visitable) {
dfs(i);
}
}
}

// 广度优先遍历
public void bfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
bfs();
}

private void bfs() {
Queue queue = new Queue();
for (int index = 0; index < length; index++) {
if (!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index + " ");
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
System.out.print(w + " ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}

}
}

// 最短路径
private int[] shortPath(int v) {
int[] shortPath = new int[length];
boolean[] weightFound = new boolean[length];
for (int i = 0; i < length; i++) {
// 趋近无穷
shortPath[i] = 9999;
weightFound[i] = false;
}
shortPath[v] = 0;
weightFound[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!weightFound[w]) {
if (shortPath[w] > shortPath[temp] + weight[temp][w]) {
shortPath[w] = shortPath[temp] + weight[temp][w];
}
}
}
int minWeightNode = 0;
for (int i = 0; i < length; i++) {
if (!weightFound[i]) {
minWeightNode = i;
for (int j = 0; j < length; j++) {
if (!weightFound[j]) {
if (shortPath[j] < shortPath[minWeightNode]) {
minWeightNode = j;
}
}
}
break;
}
}
if (!weightFound[minWeightNode]) {
weightFound[minWeightNode] = true;
queue.addQueue(minWeightNode);
}
}
return shortPath;
}

// 长度
public void length() {
System.out.println(length);
}

public boolean isEmpty() {
return length == 0;
}

// 添加节点
public void addGraph(int info) {
for (int i = 0; i < length; i++) {
if (list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}

// 添加边
public void addSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
weight[vfrom][vto] = value;
}

// 打印图
public void print() {
for (int i = 0; i < length; i++) {
GraphNode current = list[i].first;
while (current != null) {
System.out.print(current.info + " ");
current = current.link;
}
System.out.println();
}
}

public static void main(String[] args) {
Graph graph = new Graph(5);
System.out.println("create graph start");
for (int i = 0; i < 5; i++) {
graph.addGraph(i);
}
graph.addSide(0, 1, 16);
graph.addSide(0, 3, 2);
graph.addSide(0, 4, 3);
graph.addSide(3, 4, 7);
graph.addSide(3, 1, 12);
graph.addSide(4, 1, 10);
graph.addSide(4, 3, 5);
graph.addSide(4, 2, 4);
graph.addSide(2, 1, 3);
graph.addSide(1, 2, 5);
graph.print();
System.out.println("create graph end");
int[] shortPath = graph.shortPath(0);
for (int i = 0; i < shortPath.length; i++) {
System.out.print(shortPath[i] + " ");
}
}

}


8 普里姆最小生成树


Java代码
package graph;  
 
/** 
* @author B.Chen 
* 
*/ 
public class Graph {  
 
    /** 
     * 节点数 
     */ 
    private int length;  
 
    /** 
     * 链表 
     */ 
    private GraphList[] list;  
 
    /** 
     * 权集 
     */ 
    private int[][] weight;  
      
    /** 
     * 轻边集 
     */ 
    private int[][] lightSide;  
 
    /** 
     * @param length 
     */ 
    public Graph(int length) {  
        this.length = length;  
        list = new GraphList[length];  
        weight = new int[length][length];  
        lightSide = new int[length][length];  
    }  
 
    /** 
     * @param v 
     */ 
    public void dfs(int v) {  
        int[] ajd = new int[length];  
        int ajdlength = list[v].getAjd(ajd);  
        list[v].visitable = true;  
        System.out.print(v + " ");  
        for (int i = 0; i < ajdlength; i++) {  
            int w = ajd[i];  
            if (!list[w].visitable) {  
                dfs(w);  
            }  
        }  
    }  
 
    /** 
     * 深度优先遍历    
     */ 
    public void dfsTravel() {  
        for (int i = 0; i < length; i++) {  
            list[i].visitable = false;  
        }  
        for (int i = 0; i < length; i++) {  
            if (!list[i].visitable) {  
                dfs(i);  
            }  
        }  
    }  
 
    /** 
     * 广度优先遍历  
     */ 
    public void bfsTravel() {  
        for (int i = 0; i < length; i++) {  
            list[i].visitable = false;  
        }  
        bfs();  
    }  
 
    /** 
     * bfs 
     */ 
    private void bfs() {  
        Queue queue = new Queue();  
        for (int index = 0; index < length; index++) {  
            if (!list[index].visitable) {  
                queue.addQueue(index);  
                list[index].visitable = true;  
                System.out.print(index + " ");  
                while (!queue.isEmpty()) {  
                    int temp = queue.front();  
                    queue.deleteQueue();  
                    int[] adj = new int[length];  
                    int ajdlength = list[temp].getAjd(adj);  
                    for (int i = 0; i < ajdlength; i++) {  
                        int w = adj[i];  
                        if (!list[w].visitable) {  
                            System.out.print(w + " ");  
                            queue.addQueue(w);  
                            list[w].visitable = true;  
                        }  
                    }  
                }  
            }  
 
        }  
    }  
 
    /** 
     * 长度    
     */ 
    public void length() {  
        System.out.println(length);  
    }  
 
    /** 
     * @return boolean 
     */ 
    public boolean isEmpty() {  
        return length == 0;  
    }  
 
    /** 
     * @param info 
     */ 
    public void addGraph(int info) {  
        for (int i = 0; i < length; i++) {  
            if (list[i] == null) {  
                GraphList g = new GraphList();  
                g.addNode(info);  
                list[i] = g;  
                break;  
            }  
        }  
    }  
 
    /** 
     * 添加有向图的一条边 
     * @param vfrom 
     * @param vto 
     * @param value 权 
     */ 
    public void addSide(int vfrom, int vto, int value) {  
        list[vfrom].addNode(vto);  
        weight[vfrom][vto] = value;  
    }  
 
    /** 
     * 添加无向图的一条边 
     * @param vfrom 
     * @param vto 
     * @param value 
     */ 
    public void addDoubleSide(int vfrom, int vto, int value) {  
        list[vfrom].addNode(vto);  
        list[vto].addNode(vfrom);  
        weight[vfrom][vto] = value;  
        weight[vto][vfrom] = value;  
    }  
 
    /** 
     * 打印图    
     */ 
    public void print() {  
        for (int i = 0; i < length; i++) {  
            GraphNode current = list[i].first;  
            while (current != null) {  
                System.out.print(current.info + " ");  
                current = current.link;  
            }  
            System.out.println();  
        }  
    }  
 
    /** 
     * Dijkstra 
     *  
     * @param v 
     * @return int[] 
     */ 
    public int[] shortPath(int v) {  
        int[] shortPath = new int[length];  
        boolean[] weightFound = new boolean[length];  
        for (int i = 0; i < length; i++) {  
            // 趋近无穷  
            shortPath[i] = 9999;  
            weightFound[i] = false;  
        }  
        shortPath[v] = 0;  
        weightFound[v] = true;  
        Queue queue = new Queue();  
        queue.addQueue(v);  
        while (!queue.isEmpty()) {  
            int temp = queue.front();  
            queue.deleteQueue();  
            int[] ajd = new int[length];  
            int ajdlength = list[temp].getAjd(ajd);  
            for (int i = 0; i < ajdlength; i++) {  
                int w = ajd[i];  
                if (!weightFound[w]) {  
                    if (shortPath[w] > shortPath[temp] + weight[temp][w]) {  
                        shortPath[w] = shortPath[temp] + weight[temp][w];  
                    }  
                }  
            }  
            int minWeightNode = 0;  
            for (int i = 0; i < length; i++) {  
                if (!weightFound[i]) {  
                    minWeightNode = i;  
                    for (int j = 0; j < length; j++) {  
                        if (!weightFound[j]) {  
                            if (shortPath[j] < shortPath[minWeightNode]) {  
                                minWeightNode = j;  
                            }  
                        }  
                    }  
                    break;  
                }  
            }  
            if (!weightFound[minWeightNode]) {  
                weightFound[minWeightNode] = true;  
                queue.addQueue(minWeightNode);  
            }  
        }  
        return shortPath;  
    }  
      
    /** 
     * 普里姆最小生成树 
     *  
     * @param v 
     */ 
    public void primMST(int v) {  
        boolean[] visited = new boolean[length];  
        for (int i = 0; i < length; i++) {  
            visited[i] = false;  
            for (int j = 0; j < length; j++) {  
                lightSide[i][j] = 9999;  
            }  
        }  
        visited[v] = true;  
        Queue queue = new Queue();  
        queue.addQueue(v);  
        while (!queue.isEmpty()) {  
            int temp = queue.front();  
            queue.deleteQueue();  
            int[] ajd = new int[length];  
            int ajdlength = list[temp].getAjd(ajd);  
            for (int i = 0; i < ajdlength; i++) {  
                int w = ajd[i];  
                lightSide[temp][w] = weight[temp][w];  
            }  
            // 找到最小边  
            int minSide = 0;  
            int vfrom =0;  
            int vto = 0;  
            for (int i = 0; i < length; i++) {  
                for (int j = 0; j < length; j++) {  
                    if (visited[i] && visited[j]) {  
                        continue;  
                    }  
                    minSide = lightSide[i][j];  
                    vfrom = i;  
                    vto = j;  
                    for (int k = 0; k < length; k++) {  
                        for (int l = 0; l < length; l++) {  
                            if (visited[k] && visited[l]) {  
                                continue;  
                            }  
                            if (lightSide[k][l] < minSide) {  
                                minSide = lightSide[k][l];  
                                vfrom = k;  
                                vto = l;  
                            }  
                        }  
                    }  
                    break;  
                }  
            }  
            //将最小边的节点vto设为true，并输出vto  
            if (!visited[vto]) {  
                visited[vto] = true;  
                System.out.print(vfrom+"==>" + vto+", ");  
                queue.addQueue(vto);