数据结构与算法1


排序算法

算法复杂度

相关术语解释:

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
  • 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
  • 内排序:所有排序操作都在内存中完成;
  • 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 时间复杂度: 一个算法执行所耗费的时间。
  • 空间复杂度:运行完一个程序所需内存的大小。
  • n:数据规模
  • k: “桶”的个数
  • In-place: 不占用额外内存
  • Out-place :占用额外内存

选择排序

/**
 * 选择排序
 */
public class SelectSort {

    public void sort(Comparable[] sequence){
        //升序排序
        for (int i=0;i<sequence.length;i++)&#123;
            int min = i;
            for (int j=i+1;j<sequence.length;j++)&#123;
                if (!less(sequence[i],sequence[j]))&#123;
                    min = j;
                &#125;
            &#125;
            exchange(sequence,i,min);
        &#125;
    &#125;

    private void exchange(Comparable[] sequence,int j,int k)&#123;
        Comparable tmp = sequence[j];
        sequence[j] = sequence[k];
        sequence[k] = tmp;
    &#125;

    private boolean less(Comparable j,Comparable k)&#123;
        return j.compareTo(k)<=0;
    &#125;

    public static void main(String[] args) &#123;
        int[] sequence = new int[]&#123;
                10,9,8,7,6,5,4,3,2,1,0
        &#125;;
    &#125;
&#125;

冒泡排序

package com.javabull;

/**
 * 冒泡排序
 * 从小到大排序
 */
public class BubbleSort&#123;
    int[] sequence;

    private boolean less(Integer key1,Integer key2)&#123;
        return key1.compareTo(key2)<=0;
    &#125;

    public void bubbleSort(int[] sequence)&#123;
        //升序排序
        //不断将大的数放在末尾
        this.sequence = sequence;
        if (sequence!=null)&#123;
            for (int i=0;i<sequence.length;i++)&#123;
                for (int j=0;j<sequence.length-i-1;j++)&#123;
                    if (!less(sequence[j],sequence[j+1]))&#123;
                        exchange(sequence,j,j+1);
                    &#125;
                &#125;
            &#125;
        &#125;
    &#125;

    private void exchange(int[] sequence,int j,int k)&#123;
        Integer tmp = sequence[j];
        sequence[j] = sequence[k];
        sequence[k] = tmp;
    &#125;

    public static void main(String[] args) &#123;
        int[] ints = new int[]&#123;
          10,9,8,7,6,5,4,3,2,1,0
        &#125;;
        BubbleSort sort = new BubbleSort();
        sort.bubbleSort(ints);
        for (int num:ints) &#123;
            System.out.println(num);
        &#125;
    &#125;
&#125;

插入排序

package com.javabull;

/**
 * 插入排序:向前面排好的序列中插入未排的数据
 */
public class InsertSort &#123;

    private boolean less(Comparable j,Comparable k)&#123;
        return j.compareTo(k)<=0;
    &#125;

    //升序排序
    public void sort(Comparable[] sequence)&#123;
        for (int i=1;i<sequence.length;i++)&#123;
            //保存未排序的值
            Comparable tmp = sequence[i];
            int j = i;
            for (;j>=1&&less(tmp,sequence[j-1]);j--)&#123;
                //向后移动数据
                sequence[j] = sequence[j-1];
            &#125;
            sequence[j] = tmp;
        &#125;
    &#125;

    public static void main(String[] args) &#123;
        int[] sequence = new int[]&#123;
                12,11,10,9,8,7,6,5,4,3,2,1,0
        &#125;;
        Integer[] integers = new Integer[sequence.length];
        for (int i=0;i<sequence.length;i++)&#123;
            integers[i] = sequence[i];
        &#125;
        InsertSort sort = new InsertSort();
        sort.sort(integers);
        for (Integer integer:integers)&#123;
            System.out.println(integer);
        &#125;
    &#125;
&#125;

希尔排序(基于插入排序的快速排序算法)

package com.javabull;

/**
 * 希尔排序
 * ①后移版
 * ②交换版
 */
public class ShellSort &#123;

    private boolean less(Comparable j,Comparable k)&#123;
        return j.compareTo(k)<=0;
    &#125;

    public void sort(Comparable[] a)&#123;
        int N = a.length;
        int h=N/2;
        while (h >= 1)&#123;
            //分成h组
            for (int i = 0; i<h; i++)&#123;
                //遍历第i组,实现插入排序
                for (int k=i+h;k<N;k+=h)&#123;
                    int j=k;
                    Comparable tmp = a[j];
                    for (;j>=h&&less(tmp,a[j-h]); j-=h) &#123;
                        //tmp比它前面的数要小,后移数据
                        a[j] = a[j-h];
                    &#125;
                    a[j] = tmp;
                &#125;
            &#125;
            h = h/2;
        &#125;
    &#125;

    private void exchange(Comparable[] sequence,int j,int k)&#123;
        Comparable tmp = sequence[j];
        sequence[j] = sequence[k];
        sequence[k] = tmp;
    &#125;

    public static void main(String[] args) &#123;
        int[] sequence = new int[]&#123;
                23,11,10,9,8,7,6,5,4,3,2,1,0
        &#125;;
        Integer[] integers = new Integer[sequence.length];
        for (int i=0;i<sequence.length;i++)&#123;
            integers[i] = sequence[i];
        &#125;
        ShellSort shellSort = new ShellSort();
        shellSort.sort(integers);
        for (Integer integer:integers)&#123;
            System.out.println(integer);
        &#125;
    &#125;
&#125;

归并排序

package com.javabull;

/**
 * ①优先级队列
 * 二叉堆,堆的顶端为小数
 * ②堆排序
 * @param <Key>
 */
public class PriorityQueue<Key extends Comparable<Key>> &#123;

    private Key[] pq;
    private int N = 0;//数组的第0个位置不使用

    public PriorityQueue(int maxsize)&#123;
        pq = (Key[]) new Comparable[maxsize+1];
    &#125;

    //元素交换
    void exchange(int i, int j) &#123;
        Key tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    &#125;

    //元素比较
    boolean less(int i, int j)&#123;
        return pq[i].compareTo(pq[j])<=0;
    &#125;

    //元素上升
    void swim(int k)&#123;
        while(k>1 && !less(k/2,k))&#123;
            exchange(k/2,k);
            k=k/2;
        &#125;
    &#125;

    //元素下沉
    void sink(int k)&#123;
        while(2*k<=N)&#123;
            int tmp = 2*k;
            if (tmp+1<N&&!less(tmp,tmp+1)) tmp++;
            if (!less(k,tmp))&#123;
                exchange(k,tmp);
                k=tmp;
            &#125;else&#123;
                break;
            &#125;
        &#125;
    &#125;

    public void insert(Key key)&#123;
        if (N<=pq.length)&#123;
            pq[++N] = key;
            //从最后插入,上浮
            swim(N);
        &#125;
    &#125;

    public Key deleteMin()&#123;
        //将第一个与最后一个交换,删除第一个,下沉
        Key key = pq[1];
        exchange(1,N);
        pq[N] = null;
        N--;
        sink(1);
        return key;
    &#125;

    //第一个最小的数与最后一个数交换,同时,N--
    public void asArray()&#123;
        exchange(1,N);
        N--;
        sink(1);
    &#125;

    public int size()&#123;
        return N;
    &#125;

    public boolean isEmpty()&#123;
        return N==0;
    &#125;

    public Key pop()&#123;
        return deleteMin();
    &#125;

    //原地排序
    public void sort()&#123;
        int tmp = N;
        while (!isEmpty())&#123;
            asArray();
        &#125;
        N = tmp;
    &#125;

    public Key[] getArray()&#123;
        return pq;
    &#125;

    public static void main(String[] args) &#123;
        PriorityQueue<Integer> queue = new PriorityQueue<>(10);
        queue.insert(1);
        queue.insert(100);
        queue.insert(5);
        queue.insert(50);
        queue.insert(1000);
        queue.insert(90);
        queue.insert(235);
        queue.insert(15);
        queue.insert(451);
        queue.insert(20);

        //从大到小排序,堆排序
//        queue.sort();
//        Object[] array = queue.getArray();
//        for (int i=1;i<array.length;i++)&#123;
//            System.out.println(array[i]);
//        &#125;

        while(!queue.isEmpty())&#123;
            Integer num = queue.deleteMin();
            System.out.println(num);
        &#125;

        System.out.println("Queue is empty? "+queue.isEmpty());
    &#125;
&#125;

堆排序(优先级队列)

package com.javabull;

/**
 * 归并排序
 * 思想:分治模式
 */
public class MergeSort &#123;

    //合并排序
    /**
     * @param sequence
     * @param p
     * @param q
     * @param r:下标
     */
    void merge(int[] sequence,int p,int q,int r)&#123;
        //数组赋值
        int[] tmpA = new int[q-p+1];
        int[] tmpB = new int[r-q];
        for (int i=0;i<tmpA.length;i++)&#123;
            tmpA[i] = sequence[p+i];
        &#125;
        for (int i=0;i<tmpB.length;i++)&#123;
            tmpB[i] = sequence[q+i];
        &#125;
        //排序,合并tmpA 与tmpB,形成sequence
        for (int i=0,j=0,k=0;i<r-p+1;i++)&#123;
            //两个数组都没有到最后一个数据,正常执行
            if (k<tmpB.length && j<tmpA.length)&#123;
                if(tmpA[j]<=tmpB[k])&#123;
                    sequence[p+i] = tmpA[j];
                    j++;
                &#125;else&#123;
                    sequence[p+i] = tmpB[k];
                    k++;
                &#125;
            &#125;else &#123;
                //tmpB到达最后一个数据,将tmpA中的所有数据复制到sequence
                if (k>=tmpB.length)&#123;
                    for(;j<tmpA.length;j++)&#123;
                        sequence[p+i] = tmpA[j];
                        j++;
                        i++;
                    &#125;
                &#125;
                //tmpA到达最后一个数据
                if (j>=tmpA.length)&#123;
                    for(;k<tmpB.length;k++)&#123;
                        sequence[p+i] = tmpB[k];
                        k++;
                        i++;
                    &#125;
                &#125;
            &#125;
        &#125;
    &#125;

    //分离序列
    /**
     * @param sequence
     * @param p
     * @param r:下标
     */
    public void mergeSort(int[] sequence,int p,int r)&#123;
        if (p<r)&#123;
            int tmp = (p+r)/2;
            mergeSort(sequence,p,tmp);
            mergeSort(sequence,tmp+1,r);
            merge(sequence,p,tmp,r);
        &#125;
    &#125;

    public static void main(String[] args) &#123;
        int[] sequence = new int[]&#123;
            10,9,8,7,6,5,4,3,2,1,0
        &#125;;
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(sequence,0,sequence.length-1);
        for (int num:sequence) &#123;
            System.out.println(num);
        &#125;
    &#125;
&#125;

快速排序

package com.javabull;

/**
 * 快速排序
 * 思想:分治模式
 * 最坏的情况下:n2
 * 平均:nlogn
 */
public class QuickSort &#123;
    /**
     * @param sequence
     * @param lo:下标
     * @param hi:下标
     */
    public void quickSort(int[] sequence ,int lo,int hi)&#123;
        if(lo<hi)&#123;
            int tmp = partition(sequence,lo,hi);
            quickSort(sequence,lo,tmp-1);
            quickSort(sequence,tmp+1,hi);
        &#125;
    &#125;

    public int partition(int[] sequence,int lo,int hi)&#123;
        int i = lo;//左游标
        int j = hi+1;//右游标
        int v = sequence[lo];//中间数
        while(true)&#123;
            //移动左游标
            while (less(sequence[++i],v)) if (i==hi) break;
            //移动右游标
            while (less(v,sequence[--j])) if (j==lo) break;
            if (i>=j) break;
            exchange(sequence,i,j);
        &#125;
        exchange(sequence,lo,j);//将v放在中间
        return j;
    &#125;

    public void exchange(int[] sequence,int i,int j)&#123;
        int tmp = sequence[i];
        sequence[i] = sequence[j];
        sequence[j] = tmp;
    &#125;

    public boolean less(int num1,int num2)&#123;
        return num1<=num2;
    &#125;

    public static void main(String[] args) &#123;
        int[] sequence = new int[]&#123;
                10,9,8,7,6,5,4,3,2,1,0
        &#125;;
        QuickSort sort = new QuickSort();
        sort.quickSort(sequence,0,sequence.length-1);
        for (int num:sequence)&#123;
            System.out.println(num);
        &#125;
    &#125;
&#125;

数据结构

  • 稀疏数组
  • 队列
    • 队列是一个有序列表,可以用数组或者链表来实现
    • 遵循先入先出的原则
  • 链表
    • 链表是以节点的方式来存储,是链式结构
    • 每个节点包含data区域和next区域(指向下一个节点)
    • 有单向链表和双向链表
    • 先入后出(LIFO)
    • 有序列表,线性表
    • 栈是限制线性表中的元素插入和删除只能在线性表的同一端进行的一种特殊的线性表。允许插入和删除的一端,为变化的一端,称为栈顶,另一端为固定的一段,称为栈底
    • push与pop
  • 二叉树

散列表

二叉查找树

package com.javabull;

/**
 * 二叉查找树
 */
public class BSTree<Key extends Comparable<Key>,Value> &#123;
    private Node root;

    class Node&#123;
        private Key key;            //键
        private Value value;        //值
        private Node left,right;    //指向子树的链接
        private int N;              //以该节点为根的子树中的结点总数

        public Node(Key key,Value value,int N)&#123;
            this.key = key;
            this.value = value;
            this.N = N;
        &#125;
    &#125;

    public int size()&#123;
        return size(root);
    &#125;

    private int size(Node node)&#123;
        if (node == null) return 0;
        else return node.N;
    &#125;

    public boolean less(Key key1,Key key2)&#123;
        return key1.compareTo(key2)<=0;
    &#125;

    private Value get(Node node,Key key)&#123;
        Value value = null;
        if (node!=null)&#123;
            int tmp = node.key.compareTo(key);
            if (tmp==0) value = node.value;
            else if (tmp<0)&#123;
                value = get(node.right,key);
            &#125;else&#123;
                value = get(node.left,key);
            &#125;
        &#125;
        return value;
    &#125;

    public Value get(Key key)&#123;
        return get(root,key);
    &#125;

    private Node put(Node tmp,Key key,Value value)&#123;
        /**
         * 如果key存在,则更新它的值
         * 否则将以key和value为键值对的新节点插入到该子树中
         */
        if (tmp==null) tmp = new Node(key,value,1);//创建一个新节点
        int tmpv = tmp.key.compareTo(key);
        if (tmpv<0) &#123;
            tmp.right = put(tmp.right,key,value);
        &#125; else if (tmpv>0)&#123;
            tmp.left = put(tmp.left,key,value);
        &#125;else &#123;
            tmp.value = value;//修改value的值
        &#125;
        tmp.N = size(tmp.right)+size(tmp.left)+1;
        return tmp;
    &#125;

    public void put(Key key,Value value) &#123;
        root = put(root,key,value);
    &#125;

    public Key min()&#123;
        Node node = root;
        while (node!=null)&#123;
            if (node.left!=null)&#123;
                node  = node.left;
            &#125;else &#123;
                return node.key;
            &#125;
        &#125;
        return null;
    &#125;

    public Key max()&#123;
        Node node = root;
        while(node!=null)&#123;
            if (node.right!=null)&#123;
                node = node.right;
            &#125;else &#123;
                return node.key;
            &#125;
        &#125;
        return null;
    &#125;

    public Key floor(Key key)&#123;
        Node node = floor(root,key);
        if (node!=null)&#123;
            return node.key;
        &#125;
        return null;
    &#125;

    private Node floor(Node node,Key key) &#123;
        if (node == null) return null;
        int tmpv = node.key.compareTo(key);
        if (tmpv == 0) return node;
        if (tmpv > 0) &#123;
            return floor(node.left, key);
        &#125;
        Node t = floor(node.right, key);
        if (t != null) return t;
        else return node;
    &#125;

    public void deleteMin()&#123;
        Node node = root;
        Node tmp = node;
        while(node!=null)&#123;
            if (node.left!=null)&#123;
                tmp = node;
                node = node.left;
            &#125;else &#123;
                if (node == tmp) &#123;
                    //头节点
                    root = root.right;
                &#125;
                if (node.right!=null)&#123;
                    //当要删除节点存在右子树
                    tmp.left = node.right;
                &#125;else &#123;
                    //不存在右子树
                    tmp.left = null;
                &#125;
                break;
            &#125;
        &#125;
        tmp.N = size(tmp.left)+size(tmp.right)+1;
    &#125;

    public void deleteMax()&#123;

    &#125;

    //k从0开始
    public Key select(int k)&#123;
        Node node = select(root,k);
        if (node!=null)&#123;
            return node.key;
        &#125;
        return null;
    &#125;

    private Node select(Node node,int k)&#123;
        if (node!=null)&#123;
            int tmp = size(node.left);
            if (k<tmp) return select(node.left,k);
            else if (k>tmp) return select(node.right,k-tmp-1);
            else return node;
        &#125;
        return null;
    &#125;

    public int rank(Key key)&#123;
        return rank(key,root);
    &#125;

    private int rank(Key key,Node node)&#123;
        //以x为根结点的子树中小于x.key的键的数量
        if (node==null) return 0;
        int cmp = key.compareTo(node.key);
        if (cmp<0) return rank(key,node.left);
        else if (cmp>0) return 1+size(node.left)+rank(key,node.right);
        else return size(node.left);
    &#125;

    public void delete(Key key)&#123;
        root = delete(root,key);
    &#125;

    private Node delete(Node node,Key key)&#123;

        return null;
    &#125;

    //范围查找
    public void keys()&#123;
        
    &#125;

    public static void main(String[] args) &#123;
        BSTree tree = new BSTree<Integer,String>();
        tree.put(1,"hello");
        tree.put(2,"hello world");
        tree.put(0,"min");
        tree.put(-1,"ni hao");
        System.out.println(tree.get(1));
        System.out.println(tree.get(2));
//        tree.deleteMin();
//        tree.deleteMin();
//        System.out.println("max=" + tree.max());
//        System.out.println("min="+tree.min());
        System.out.println(tree.select(0));
    &#125;
&#125;

平衡查找树

红黑二叉查找树

package com.javabull;

/**
 * 平衡红黑二叉树
 * @param <Key>
 * @param <Value>
 */
public class RedBlackBSTree<Key extends Comparable<Key>,Value>&#123;
    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node&#123;
        Key key;
        Value value;
        Node left,right;
        int N;
        boolean color;

        Node(Key key,Value value,int N,boolean color)&#123;
            this.key = key;
            this.value = value;
            this.N = N;
            this.color = color;
        &#125;
    &#125;

    private boolean isRed(Node node)&#123;
        return node.color==RED;
    &#125;

    //todo
    
&#125;

图是一种数据结构,其中节点可以有0个或者多个相邻元素。两个节点之间的连接称为边

图的常用概念

  • 顶点
  • 路径
  • 无向图

无向图(简单连接)

有向图 (连接有方向性)

加权图 (连接带有权值)

加权有向图(连接既有方向性,又带有权值)

图的表示方式

二维数组表示(邻接矩阵)

代码实现

package com.javabull.graph;        

import java.util.ArrayList;
import java.util.Arrays;

public class Graph &#123;
// 描述图的二维数组,保存图的权值,0表示没有连接
        int edges;
      // 边的数目
        int numOfEdges = 0;
      // 顶点
        ArrayList<String> vertex;
    public Graph(int n) &#123;
        assert(true);
        vertex = new ArrayList<String>();
        edges = new int[n][n];
        for(int i=0;i<n;i++) &#123;
            for(int j=0;j<n;j++) &#123;
                edges[i][j]=0;                
            &#125;
        &#125;
    &#125;
    
    //添加顶点
    public void insertVertex(String vertexName) &#123;
        vertex.add(vertexName);
    &#125;
    
    //添加顶点边的关系
    public void addEdges(int v1,int v2,int weight) &#123;
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    &#125;
    
    //将图输出
    public void showGraph() &#123;
        for(int[] edge:edges) &#123;
            System.out.println(Arrays.toString(edge));
        &#125;
    &#125;
    
    //查找两个顶点的权值
    public int getWeight(int v1,int v2) &#123;
        if(v1<vertex.size()&&v1>=0) &#123;
            return edges[v1][v2];    
        &#125;else &#123;
            return -1;
        &#125;
    &#125;
    
    //获取边的总数
    public int getNumOfEdge() &#123;
        return numOfEdges;
    &#125;
    
    public static void main(String[] args) &#123;
        Graph graph = new Graph(6);
        for(int i=0;i<5+1;i++) &#123;
            graph.insertVertex(String.format("%d",i));
        &#125;
        graph.addEdges(0, 1, 1);
        graph.addEdges(0, 4, 1);
        graph.addEdges(0, 2, 1);
        graph.addEdges(0, 3, 1);
        graph.addEdges(1, 4, 1);
        graph.addEdges(2, 4, 1);
        graph.addEdges(4, 5, 1);
        graph.addEdges(2, 5, 1);
        graph.addEdges(3, 5, 1);
        
        graph.showGraph();
    &#125;
&#125;

图的深度优先遍历(优先考虑从纵向遍历,是一个递归过程)

/**
    1)访问初始结点v,并标记结点v为已访问。

    2)查找结点v的第一个邻接结点w。

    3)若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。

    4)若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。

    5)查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

*/
package com.javabull.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class Graph &#123;
    // 描述图的二维数组,保存图的权值,0表示没有连接
    int[][] edges;
    // 边的数目
    int numOfEdges = 0;
    // 顶点
    ArrayList<String> vertex;
    // 标记节点是否访问
    boolean[] isVisted;

    public Graph(int n) &#123;
        assert (true);
        vertex = new ArrayList<String>();
        edges = new int[n][n];
        for (int i = 0; i < n; i++) &#123;
            for (int j = 0; j < n; j++) &#123;
                edges[i][j] = 0;
            &#125;
        &#125;
        isVisted = new boolean[n];
    &#125;

    // 添加顶点
    public void insertVertex(String vertexName) &#123;
        vertex.add(vertexName);
    &#125;

    // 添加顶点边的关系
    public void addEdges(int v1, int v2, int weight) &#123;
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    &#125;

    // 将图输出
    public void showGraph() &#123;
        for (int[] edge : edges) &#123;
            System.out.println(Arrays.toString(edge));
        &#125;
    &#125;

    // 查找两个顶点的权值
    public int getWeight(int v1, int v2) &#123;
        if (v1 < vertex.size() && v1 >= 0) &#123;
            return edges[v1][v2];
        &#125; else &#123;
            return -1;
        &#125;
    &#125;

    // 获取边的总数
    public int getNumOfEdge() &#123;
        return numOfEdges;
    &#125;

    // 获取该节点的邻接节点
    private int getFirstNeighbor(int index) &#123;
        for (int i = 0; i < vertex.size(); i++) &#123;
            if (edges[index][i] > 0) &#123;
                return i;
            &#125;
        &#125;
        return -1;
    &#125;

    // 通过前一个邻接节点获取下一个邻接节点
    /**
     * @param v 节点头
     * @param i 当前邻接节点
     * @return 如果存在,则返回下标,否则返回-1
     */
    private int getNextNeighbeor(int v, int i) &#123;
        for (int j = i + 1; j < vertex.size(); j++) &#123;
            if (edges[v][j] > 0) &#123;
                return j;
            &#125;
        &#125;
        return -1;
    &#125;
    
    private void dfs(boolean[] isVisted,int index) &#123;
        //访问初始节点 index,标记已经访问
        System.out.print(vertex.get(index)+"-->");
        isVisted[index] = true;
        //查找节点 index的第一个邻接节点
        int w=getFirstNeighbor(index);
        while(w!=-1) &#123;
            if (!isVisted[w]) &#123;
                dfs(isVisted,w);
            &#125;
            w = getNextNeighbeor(index, w);
        &#125;
    &#125;
    
    //图的深度算法(Depth First Search )
    public void dfs() &#123;
        for(int i=0;i<isVisted.length;i++) &#123;
            if (!isVisted[i]) &#123;
                dfs(isVisted,i);
            &#125;
        &#125;
    &#125;
    
    public static void main(String[] args) &#123;
        Graph graph = new Graph(6);
        for (int i = 0; i < 5 + 1; i++) &#123;
            graph.insertVertex(String.format("%d", i));
        &#125;
        graph.addEdges(0, 1, 1);
        graph.addEdges(0, 4, 1);
        graph.addEdges(0, 2, 1);
        graph.addEdges(0, 3, 1);
        graph.addEdges(1, 4, 1);
        graph.addEdges(2, 4, 1);
        graph.addEdges(4, 5, 1);
        graph.addEdges(2, 5, 1);
        graph.addEdges(3, 5, 1);

        graph.showGraph();
        
        graph.dfs();
    &#125;
&#125;

图的广度优先搜索(优先考虑从横向进行搜索)

/*
访问初始结点v并标记结点v为已访问。
结点v入队列
当队列非空时,继续执行,否则算法结束。
出队列,取得队头结点u。
查找结点u的第一个邻接结点w。
若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
6.1 若结点w尚未被访问,则访问结点w并标记为已访问。 
6.2 结点w入队列 
6.3 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6
*/
    public void bfs() &#123;
        isVisted = new boolean[vertex.size()];
        for (int i = 0; i < isVisted.length; i++) &#123;
            if (!isVisted[i]) &#123;
                bfs(isVisted, i);
            &#125;
        &#125;
    &#125;

    // 图的广度优先算法
    private void bfs(boolean[] isVisted, int index) &#123;
        System.out.print( vertex.get(index)+ "==>");
        isVisted[index] = true;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        int w = getFirstNeighbor(index);
        if(w!=-1) queue.add(w);
        
        while(!queue.isEmpty()) &#123;
            while(w!=-1) &#123;
                //若存在下一个邻接节点,循环访问
                if(!isVisted[w]) &#123;
                    queue.addLast(w);
                    System.out.print( vertex.get(w)+ "==>");
                    isVisted[w] = true;
                &#125;
                w = getNextNeighbeor(index, w);
            &#125;
            w = queue.removeFirst();
        &#125;
    &#125;

链表表示(邻接表)

代码实现


马踏棋盘

package com.javabull.knight;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * 马踏棋盘
 * 图的深度优先
 */
public class KnightTour &#123;
    // 表示棋盘的行
    private int X;
    // 表示棋盘的列
    private int Y;
    // 棋盘上的点是否被访问过
    private boolean[] isvisted;
    //棋盘
    private int[][] board;
    //是否完成任务
    private boolean finished;
    
    public KnightTour(int X, int Y ) &#123;
        this.X = X;
        this.Y = Y;
        isvisted = new boolean[X * Y];
        board = new int[X][Y];
    &#125;

    public ArrayList<Point> getNextPoints(Point curPoint) &#123;
        // 创建一个ArrayList
        ArrayList<Point> ps = new ArrayList<Point>();
        // 创建一个Point
        Point p1 = new Point();
        // 表示马儿可以走5这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走6这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走7这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走0这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走1这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走2这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走3这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走4这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        return ps;
    &#125;
    
    public void knighttour(Point first,int step) &#123;
        ArrayList<Point> nextPoints = getNextPoints(first);
        //标记当前点被访问了
        isvisted[first.x*Y+first.y] = true;
        //记录步数
        board[first.x][first.y] = step;
        
        while(!nextPoints.isEmpty()) &#123;
            Point p1 = nextPoints.remove(0);
            //判断p1是否访问
            if (!isvisted[p1.x*Y+p1.y]) &#123;
                knighttour(p1,step+1);
            &#125;
        &#125;
        
        //finished是为了使得所有的函数都返回
        if(step < X * Y && !finished ) &#123;
            board[first.x][first.y] = 0;
            isvisted[first.x*Y+first.y] = false;
        &#125; else &#123;
            finished = true;
        &#125;
    &#125;

    public void showStep() &#123;
        for(int[] b:board) &#123;
            System.out.println(Arrays.toString(b));
        &#125;
    &#125;
    
    public static void main(String[] args) &#123;
        KnightTour tour = new KnightTour(6, 6);
        tour.knighttour(new Point(1,1), 1);
        tour.showStep();
    &#125;
&#125;

算法优化

package com.javabull.knight;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 马踏棋盘
 * 图的深度优先
 */
public class KnightTour &#123;
    // 表示棋盘的行
    private static int X;
    // 表示棋盘的列
    private static int Y;
    // 棋盘上的点是否被访问过
    private boolean[] isvisted;
    //棋盘
    private int[][] board;
    //是否完成任务
    private boolean finished;
    
    public KnightTour(int X, int Y ) &#123;
        this.X = X;
        this.Y = Y;
        isvisted = new boolean[X * Y];
        board = new int[X][Y];
    &#125;

    public static ArrayList<Point> getNextPoints(Point curPoint) &#123;
        // 创建一个ArrayList
        ArrayList<Point> ps = new ArrayList<Point>();
        // 创建一个Point
        Point p1 = new Point();
        // 表示马儿可以走5这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走6这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走7这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走0这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走1这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走2这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走3这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        // 判断马儿可以走4这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) &#123;
            ps.add(new Point(p1));
        &#125;
        return ps;
    &#125;
    
    public void knighttour(Point first,int step) &#123;
        ArrayList<Point> nextPoints = getNextPoints(first);
        //标记当前点被访问了
        isvisted[first.x*Y+first.y] = true;
        //记录步数
        board[first.x][first.y] = step;
        sort(nextPoints);
        while(!nextPoints.isEmpty()) &#123;
            Point p1 = nextPoints.remove(0);
            //判断p1是否访问
            if (!isvisted[p1.x*Y+p1.y]) &#123;
                knighttour(p1,step+1);
            &#125;
        &#125;
        
        //finished是为了使得所有的函数都返回
        if(step < X * Y && !finished ) &#123;
            board[first.x][first.y] = 0;
            isvisted[first.x*Y+first.y] = false;
        &#125; else &#123;
            finished = true;
        &#125;
    &#125;

    public void showStep() &#123;
        for(int[] b:board) &#123;
            System.out.println(Arrays.toString(b));
        &#125;
    &#125;
    
    public static void sort(ArrayList<Point> ps) &#123;
        ps.sort(new Comparator<Point>() &#123;
            @Override
            public int compare(Point o1, Point o2) &#123;
                // TODO Auto-generated method stub
                //获取到o1的下一步的所有位置个数
                int count1 = getNextPoints(o1).size();
                //获取到o2的下一步的所有位置个数
                int count2 = getNextPoints(o2).size();
                if(count1 < count2) &#123;
                    return -1;
                &#125; else if (count1 == count2) &#123;
                    return 0;
                &#125; else &#123;
                    return 1;
                &#125;
            &#125;
        &#125;);
    &#125;
    
    public static void main(String[] args) &#123;
        KnightTour tour = new KnightTour(8, 8);
        tour.knighttour(new Point(1,1), 1);
        tour.showStep();
    &#125;
&#125;

常用算法

分治算法

分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题

解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

合并:将各个子问题的解合并为原问题的解。

汉洛塔

package com.javabull.hantower;

/**
 * 分治法解决汉罗塔
 */
public class Tower &#123;
    
    public static void tower(int num,char a,char b,char c) &#123;
        if (num==1) &#123;
            System.out.println("第"+num+"个盘移动 "+a+"->"+c);
        &#125;else &#123;
            //a->b
            tower(num-1, a,c,b);
            //a->c
            System.out.println("第"+num+"个盘移动 "+a+"->"+c);
            //b->c
            tower(num-1, b, a, c);
        &#125;
    &#125;

    public static void main(String[] args) &#123;
        tower(3, 'A', 'B', 'C');
    &#125;
&#125;

动态规划

核心是记住已经求过的解

使用要求是问题存在最优解

解法:①自顶向下(类似于树,递归式) ②自底向上(非递归)

问题一:斐波那契

解法一 :Fib(n)=Fib(n−1)+Fib(n−2)

package com.javabull.dynamicprogramming;

public class Problem1 &#123;        
    public static int fib(int index) &#123;
        if(index<=2) return 1;
        else &#123;
            return fib(index-2)+fib(index-1);
        &#125;
    &#125;
    
    public static void main(String[] args) &#123;
        //求斐波那契数列的第6个数
        System.out.println(fib(6));
    &#125;
&#125;

解法二:自底向上

package com.javabull.dynamicprogramming;

public class Problem1 &#123;
    
    public static int fib2(int index) &#123;
        int result = 1;
        if(index > 2) &#123;
            int tmp = 1;
            while(index>2) &#123;
                //tmp为第i个数,result为第i+1个数,tmp2为第i+1个数
                int tmp2 = result;
                result = tmp +result;
                index--;
                tmp = tmp2;
            &#125;
        &#125;
        return result;
    &#125;
    
    public static void main(String[] args) &#123;
        System.out.println(fib2(6));
    &#125;
&#125;

1

问题二:背包问题 (0..1),使背包中物品的价值最大化。

01背包的状态转换方程 f[i,j] = Max{ f[ i,j-w[i] ]+Pi( j >= w[i] ), f[i-1,j] }

代码如下

package com.javabull.dynamicprogramming;

public class Bag &#123;
    public static void main(String[] args) &#123;
        int max = 10;// 背包最大承受的重量
        int[] w = &#123; 2,2,6,5,4 &#125;;//商品的重量
        int[] v = &#123; 600,300,500,400,600 &#125;;//商品的价值
        int[][] p = new int[w.length + 1][max + 1];

        for (int i = 1; i < p.length; i++) &#123;
            for (int j = 1; j < p[0].length; j++) &#123;
                if (w[i-1]>j) &#123;
                    p[i][j] = p[i-1][j]; 
                &#125;else &#123;
                    if (p[i-1][j] > v[i-1]+p[i-1][j-w[i-1]]) &#123;
                        p[i][j] = p[i-1][j];
                    &#125;else &#123;
                        p[i][j] = v[i-1]+p[i-1][j-w[i-1]];
                    &#125;
                &#125;
            &#125;
        &#125;

        for (int i = 1; i < p.length; i++) &#123;
            for (int j = 1; j < p[0].length; j++) &#123;
                System.out.print(p[i][j] + " ");
            &#125;
            System.out.println();
        &#125;
    &#125;
&#125;

0n背包

代码如下

package com.javabull.dynamicprogramming;

public class Bag &#123;
    public static void bag01(int max,int[] w,int[] v) &#123;
        int[][] p = new int[w.length + 1][max + 1];
        for (int i = 1; i < p.length; i++) &#123;
            for (int j = 1; j < p[0].length; j++) &#123;
                if (w[i-1]>j) &#123;
                    p[i][j] = p[i-1][j];
                &#125;else &#123;
                    if (p[i-1][j] > v[i-1]+p[i-1][j-w[i-1]]) &#123;
                        p[i][j] = p[i-1][j];
                    &#125;else &#123;
                        p[i][j] = v[i-1]+p[i-1][j-w[i-1]];
                    &#125;
                &#125;
            &#125;
        &#125;
        show(p);
    &#125;
    
    public static void bag0n(int max,int[] w,int[] v) &#123;
        int[][] p = new int[w.length + 1][max + 1];
        for (int i = 1; i < p.length; i++) &#123;
            for (int j = 1; j < p[0].length; j++) &#123;
                if (w[i-1]>j) &#123;
                    p[i][j] = p[i-1][j];
                &#125;else &#123;
                    if (p[i-1][j] > v[i-1]+p[i][j-w[i-1]]) &#123;
                        p[i][j] = p[i-1][j];
                    &#125;else &#123;
                        p[i][j] = v[i-1]+p[i][j-w[i-1]];
                    &#125;
                &#125;
            &#125;
        &#125;
        show(p);
    &#125;
    
    public static void show(int[][] p) &#123;
        for (int i = 1; i < p.length; i++) &#123;
            for (int j = 1; j < p[0].length; j++) &#123;
                System.out.print(p[i][j] + " ");
            &#125;
            System.out.println();
        &#125;
    &#125;
    
    public static void main(String[] args) &#123;
        int max = 10;// 背包最大承受的重量
        int[] w = &#123;2,2,2,1&#125;;//商品的重量
        int[] v = &#123; 150,250,200,100 &#125;;//商品的价值
        bag01(max, w, v);
        System.out.println();
        bag0n(max, w, v);
    &#125;
&#125;

问题三:有数组 {3,6,7,9,1,0,2}; 求不相邻元素的最大和

非递归式 (利用一个数组,保存计算的中间值,即保存求过的解)

package com.javabull.dynamicprogramming;

public class Problem1 &#123;
    // 非递归式
    public static int nores(int[] sequence) &#123;
        int length = sequence.length;
        if (length==1) &#123;
            return sequence[0];
        &#125;else if (length==2) &#123;
            return Integer.max(sequence[0],sequence[1]);
        &#125;
        int[] result = new int[sequence.length];
        result[0] = sequence[0];
        result[1] = sequence[1];
        result[2] = sequence[2] + result[0];
        int i = 3;
        while (i < sequence.length) &#123;
            result[i] = Integer.max(result[i - 2], result[i - 3]) + sequence[i];
            i++;
        &#125;
        return result[result.length - 1];
    &#125;

    public static void main(String[] args) &#123;
        int[] ints = &#123; 1, 2, 2,4,2,3,6,10,1,3 &#125;;
        int result = nores(ints);
        System.out.println(result);
    &#125;
&#125;

递归式

package com.javabull.dynamicprogramming;

public class Problem1 &#123;
    // 递归式
    public static int res(int[] sequence, int index) &#123;
        int result = 0;
        if (index < 2)
            result = sequence[index];
        else &#123;
            result = Integer.max(res(sequence, index - 1), sequence[index] + res(sequence, index - 2));
        &#125;
        return result;
    &#125;

    public static void main(String[] args) &#123;
        int[] ints = &#123; 1, 2, 2,4,2,3,6,10,1,3 &#125;;
        int result = res(ints, ints.length - 1);
        System.out.println(result);
    &#125;
&#125;

KMP算法

KMP是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置的经典算法

第一个版本 (效率低)

package com.javabull.kmp;

import java.util.HashSet;
import java.util.Set;

public class KMPalgorithm &#123;
    // 1.获取字符串匹配表
    public static int[] table(String str) &#123;
        int length = str.length();
        int[] table = null;
        if (length >= 1) &#123;
            table = new int[length];
            table[0] = 0;
            for (int i = 2; i <= table.length; i++) &#123;
                String subStr = str.substring(0, i);
                // 分割出前缀
                Set<String> setpre = new HashSet<String>();
                for (int j = 1; j < subStr.length(); j++) &#123;
                    setpre.add(subStr.substring(0, j));
                &#125;
                // 后缀
                Set<String> setaft = new HashSet<String>();
                for (int j = 1; j < subStr.length(); j++) &#123;
                    setaft.add(subStr.substring(j, subStr.length()));
                &#125;
                int count = 0;
                // 比较前缀和后缀,便利前缀
                for (String string : setpre) &#123;
                    if (setaft.contains(string)) &#123;
                        //匹配字符的长度
                        count+=string.length();
                    &#125;
                &#125;
                // 写入匹配表
                table[i - 1] = count;
            &#125;
        &#125;
        return table;
    &#125;

    /**
     * @param table:字符串匹配表
     * @param str1:待匹配的字符串
     * @param str2:匹配字符串
     * @return:第一个匹配的位置
     */
    public static int match(int[] table, String str1, String str2) &#123;
        int ret = -1;
        int p = 0;
        // str1的长度要大于str2的长度
        int N = str1.length() - str2.length();
        if (N > 0) &#123;
            //遍历str1
            while (p <= N) &#123;
                char c = str1.charAt(p);
                if(c==str2.charAt(0)) &#123;
                    //遍历str2
                    int i=1;
                    for(;i<str2.length();i++) &#123;
                        c = str1.charAt(p+i);
                        //没有匹配成功
                        if (!(c==str2.charAt(i))) break;
                        //匹配成功,继续匹配下一个,直到匹配完全
                    &#125;
                    if(i==str2.length()) return p;
                    p += i-table[i-1];
                &#125;else &#123;
                    p++;
                &#125;
            &#125;
        &#125;
        return ret;
    &#125;

    public static void main(String[] args) &#123;
        String str1 = "你好,China中国";
        String str2 = "中国";
        int[] tables = table(str2);
        System.out.println(match(tables,str1,str2));
    &#125;
&#125;

第二个版本二

package com.javabull.kmp;

public class KMPalgorithm &#123;
    public static void main(String[] args) &#123;
        String str1 = "你好,China中国";
        String str2 = "中国";
        int[] tables = kmpNext(str2);
        System.out.println(kmpSearch(str1,str2,tables));
    &#125;
    
    /**
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表,是子串对应的部分匹配表
     * @return 如果是-1,说明没有匹配到,否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1,String str2,int[] next) &#123;
        for(int i=0,j=0;i<str1.length();i++) &#123;
            while(j>0&&str1.charAt(i)!=str2.charAt(j)) &#123;
                j=next[j-1];
            &#125;
            if(str1.charAt(i)==str2.charAt(j)) j++;
            //找到了
            if(j==str2.length()) return i-j+1;
        &#125;
        return -1;
    &#125;
    
    public static int[] kmpNext(String dest)&#123;
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 0,j=0; i < dest.length(); i++) &#123;
            while(j>0 && dest.charAt(i)!=dest.charAt(j)) &#123;
                j = next[j-1];
            &#125;
            if(dest.charAt(i)==dest.charAt(j)) j++;
            next[i] = j;
        &#125;
        return next;
    &#125;
&#125;

###贪心算法

整体最优解可以通过一系列局部最优

普利姆算法

求解最小生成树的一种算法

问题描述

某乡有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通

各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里

如何修路保证各个村庄都能连通,并且总的修建公路总里程最短?

package com.javabull.prim;

import java.util.ArrayList;

/**
 * 有胜利乡有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通 各个村庄的距离用边线表示(权) ,比如 A – B 距离
 * 5公里 问:如何修路保证各个村庄都能连通,并且总的修建公路总里程最短?
 */
public class Prim &#123;

    public static void main(String[] args) &#123;
        char[] map = &#123; 'A', 'B', 'C', 'D', 'E', 'F', 'G' &#125;;// 下标 与 字符的对应
        int[][] vertexs = &#123;
            &#123;0, 2, 7&#125;,
            &#123;0, 6, 2&#125;,
            &#123;0, 1, 5&#125;,
            &#123;1, 6, 3&#125;,
            &#123;1, 3, 9&#125;,
            &#123;3, 5, 4&#125;,
            &#123;5, 6, 6&#125;,
            &#123;4, 5, 5&#125;,
            &#123;4, 3, 8&#125;,
            &#123;4, 6, 4&#125;
        &#125;;
        
        MinTree minTree = new MinTree(7,vertexs,map);
        minTree.prim(0);
    &#125;
&#125;

class MinTree &#123;
    // 描述图的二维数组,保存图的权值,0表示没有连接
    int[][] edges;
    // 边的数目
    int numOfEdges = 0;
    // 顶点
    ArrayList<String> vertex;

    public MinTree(int n,int[][] vertexs,char[] vtxNames) &#123;
        vertex = new ArrayList<String>();
        edges = new int[n][n];
//        for (int i = 0; i < n; i++) &#123;
//            for (int j = 0; j < n; j++) &#123;
//                edges[i][j] = 0;
//            &#125;
//        &#125;
        for (int i = 0; i < vertexs.length; i++) &#123;
            edges[vertexs[i][0]][vertexs[i][1]] = vertexs[i][2];
            edges[vertexs[i][1]][vertexs[i][0]] = vertexs[i][2];
        &#125;
        for(int i=0;i<vtxNames.length;i++)&#123;
            vertex.add(String.format("%c", vtxNames[i]));
        &#125;
//        for (int[] edge:edges) &#123;
//            System.out.println(Arrays.toString(edge));
//        &#125;
    &#125;
    
    public void prim(int index) &#123;
        boolean[] isvisted  = new boolean[vertex.size()];
        int v1=-1;
        int v2=-1;
        int minWeight = Integer.MAX_VALUE;
        isvisted[index] = true;
        
        for(int k=1;k<vertex.size();k++) &#123;
            for(int i=0;i<vertex.size();i++) &#123;
                for(int j=0;j<vertex.size();j++) &#123;
                    //i表示已访问,j代表未访问,edges[i][j]>0表示有连接的,
                    if (isvisted[i] && !isvisted[j] && edges[i][j]>0 && edges[i][j]<minWeight) &#123;
                        v1 = i;
                        v2 = j;
                        minWeight = edges[i][j];
                    &#125;
                &#125;
            &#125;
            System.out.println("边<" + vertex.get(v1) + "," + vertex.get(v2) + "> 权值:" + minWeight);
            minWeight = Integer.MAX_VALUE;
            isvisted[v2] = true;
        &#125;
        
    &#125;
&#125;

克鲁斯卡尔算法

kruskal

求解最小生成树的另一种算法

基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路

具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止

package com.javabull.kruskal;

import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 * 求最小生成树
 */
public class Kruskal &#123;
    public static final int INF=Integer.MAX_VALUE;
    //边总数
    int numOfEdges;
    //邻接矩阵
    int[][] matrix;
    //顶点
    char[] vertex;
    
    public Kruskal(int[][] matrix,char[] vertex) &#123;
        this.vertex = new char[vertex.length];
        this.matrix = new int[vertex.length][vertex.length];
        
        for (int i = 0; i < vertex.length; i++) &#123;
            this.vertex[i]=vertex[i];
        &#125;
        for(int i=0;i<matrix.length;i++) &#123;
            for (int j = 0; j < matrix[0].length; j++) &#123;
                this.matrix[i][j] = matrix[i][j];
                if (matrix[i][j]!=INF && matrix[i][j]!=0) &#123;
                    numOfEdges++;
                &#125;
            &#125;
        &#125;
        numOfEdges/=2;
    &#125;
    
    //打印邻接矩阵
    public void show() &#123;
        System.out.println("邻接矩阵为: \n");
        for(int i = 0; i < vertex.length; i++) &#123;
            for(int j=0; j < vertex.length; j++) &#123;
                System.out.printf("%12d", matrix[i][j]);
            &#125;
            System.out.println();//换行
        &#125;
        System.out.println("边数为:"+numOfEdges);
    &#125;
    
    //获取边
    public EData[] getEdges() &#123;
        EData[] datas = new EData[numOfEdges];
        int count = 0;
        for (int i = 0; i < vertex.length; i++) &#123;
            for (int j = i+1; j < vertex.length; j++) &#123;
                if(matrix[i][j]!=INF) &#123;
                    datas[count++] = new EData(vertex[i], vertex[j], matrix[i][j]);
                &#125;
            &#125;
        &#125;
        return datas;
    &#125;
    
    //对边进行排序
    public void sortEdges(EData[] datas) &#123;
        //选择排序
        for (int i = 0; i < datas.length; i++) &#123;
            for (int j = i+1; j < datas.length; j++) &#123;
                if (datas[i].weight>datas[j].weight) &#123;
                    EData tmp = datas[i];
                    datas[i] = datas[j];
                    datas[j] = tmp;
                &#125;
            &#125;
        &#125;
        
        //冒泡排序
//        for (int i = 0; i < datas.length; i++) &#123;
//            for(int j=0;j < datas.length-1-i; j++) &#123;
//                if (datas[j].weight>datas[j+1].weight) &#123;
//                    EData tmp = datas[j+1];
//                    datas[j+1] = datas[j];
//                    datas[j] = tmp;
//                &#125;
//            &#125;
//        &#125;
        
        //插入排序
//        for (int i = 1; i < datas.length; i++) &#123;
//            EData cur = datas[i];
//            int j=i-1;
//            //不断后移,直到前面的数不比当前数大
//            while(j>=0) &#123;
//                if(datas[j].weight>cur.weight) &#123;
//                    datas[j+1] = datas[j];
//                    j--;
//                &#125;else &#123;
//                    break;
//                &#125;
//            &#125;
//            datas[j+1] = cur;
//        &#125;
    &#125;
    
    /**
     * 
     * @param ch 顶点的值,比如'A','B'
     * @return 返回ch顶点对应的下标,如果找不到,返回-1
     */
    private int getPosition(char ch) &#123;
        for(int i = 0; i < vertex.length; i++) &#123;
            if(vertex[i] == ch) &#123;//找到
                return i;
            &#125;
        &#125;
        //找不到,返回-1
        return -1;
    &#125;
    
    /**
     * 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同
     * @param ends : 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中,逐步形成
     * @param i : 表示传入的顶点对应的下标
     * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解
     */
    private int getEnd(int[] ends, int i) &#123; // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
        while(ends[i] != 0) &#123;
            i = ends[i];
        &#125;
        return i;
    &#125;
    
    //克鲁斯卡尔算法
    public void kruskal() &#123;
        int[] ends = new int[numOfEdges];
        int index = 0;
        //最终生成的边的集合
        EData[] rets = new EData[numOfEdges];
        
        EData[] edges = getEdges();
        sortEdges(edges);
        for(int i=0;i<numOfEdges;i++) &#123;
            //获取顶点
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);
            int m = getEnd(ends, p1);
            int n = getEnd(ends, p2);
            if(m!=n) &#123;
                ends[m] = n;
                rets[index++] = edges[i];
            &#125;
        &#125;
        
        //<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
        //统计并打印 "最小生成树", 输出  rets
        System.out.println("最小生成树为");
        for(int i = 0; i < index; i++) &#123;
            System.out.println(rets[i]);
        &#125;
    &#125;
    
    public static void main(String[] args) &#123;
        char[] vertexs = &#123;'A', 'B', 'C', 'D', 'E', 'F', 'G'&#125;;
        //克鲁斯卡尔算法的邻接矩阵  
        int matrix[][] = &#123;
          /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
    /*A*/ &#123;   0,  12, INF, INF, INF,  16,  14&#125;,
    /*B*/ &#123;  12,   0,  10, INF, INF,   7, INF&#125;,
    /*C*/ &#123; INF,  10,   0,   3,   5,   6, INF&#125;,
    /*D*/ &#123; INF, INF,   3,   0,   4, INF, INF&#125;,
    /*E*/ &#123; INF, INF,   5,   4,   0,   2,   8&#125;,
    /*F*/ &#123;  16,   7,   6, INF,   2,   0,   9&#125;,
    /*G*/ &#123;  14, INF, INF, INF,   8,   9,   0&#125;&#125;; 
          //大家可以在去测试其它的邻接矩阵,结果都可以得到最小生成树.
        Kruskal kruskalCase = new Kruskal(matrix, vertexs);
        kruskalCase.show();
        EData[] edges = kruskalCase.getEdges();
        System.out.println(Arrays.toString(edges));
        kruskalCase.sortEdges(edges);
        System.out.println(Arrays.toString(edges));
        kruskalCase.kruskal();
    &#125;
&#125;

//创建一个类EData ,它的对象实例就表示一条边
class EData &#123;
    char start; //边的一个点
    char end; //边的另外一个点
    int weight; //边的权值
    //构造器
    public EData(char start, char end, int weight) &#123;
        this.start = start;
        this.end = end;
        this.weight = weight;
    &#125;
    //重写toString, 便于输出边信息
    @Override
    public String toString() &#123;
        return "EData [<" + start + ", " + end + ">= " + weight + "]";
    &#125;
&#125;

文章作者: 风儿吹 羊儿肥
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 风儿吹 羊儿肥 !
  目录