图和树

作者: 随时学丫 | 来源:发表于2018-02-06 21:02 被阅读11次

图

图的两种表示方法：邻接表和邻接矩阵，既可以表示有向图，也可以表示无向图

通常使用邻接表表示法，这种方法表示稀疏图（图中的边数远小于点个数）比较紧凑。但当遇到稠密图（|E|接近|V|^2）或必须很快辨别两个给定顶点是否有邻接边时，通常使用邻接矩阵。

求最短路径，采用邻接矩阵

邻接表的不足：若要确定图中边(U,V)是否存在，只能在顶点U邻接表中搜索V。

邻接矩阵可以弥补这个不足，但是需要占用更多的存储空间。

完全图：每个顶点之间恰有一条边的简单图，

若G是无向图，边e和顶点n的关系 0<=e<=n(n-1)/2，恰有n(n-1)/2条边的无向图称为无向完全图

若G是有向图，边e和顶点n的关系 0<=e<=n(n-1)，恰有n(n-1)条边的无向图称为有向完全图
有向图：图的边有方向，边一般用尖括号表示<>

顶点度的和 = 2x顶点入度之和 = 2x顶点出度之和 = 顶点入度之和+顶点出度之和 = 边数的2倍
```
V(G1)={v1，v2，v3}
E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}
```
无向图：图的边没有方向，边一般用圆括号表示()

没有入度和出度之分，顶点度数之和 = 边数 * 2
```
V(G2)={v1，v2，v3，v4}
E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}
```
连通图：图的每两个顶点之间有路径连接

连通图至少n-1条边，有4个顶点至少需要4条边就可组成一个连通图

广度优先搜索（BFS）

广度优先搜索使用队列的数据结构，先进先出

广度优先搜索从一个源顶点出发，通过对其邻接表进行遍历，可以发现所有和源顶点邻接的顶点，依次类推，不断向外扩展，进而发现与源顶点的邻接点相邻接的顶点。

求源节点到当前节点的最短路径，适用于有向图和无向图，无加权

遍历过程

将A节点入队，queue(A)
将A节点弹出，同时将A的子节点B，C插入队列中，此时B在队列首，C在队列尾部，queue(B,C)
将B节点弹出，同时将B的子节点D，E入队，此时C在队列首部，E在队列尾部，queue(C,D,E)
将C节点弹出，同时将C的子节点F，G，H插入队列，此时D在队列首部，H在队列尾部，queue(D,E,F,G,H)
……直到遍历完成

其过程对每一层节点依次访问，访问完一层进入下一层，并且每个节点只能访问一次。

时间复杂度

邻接表存储时间复杂度O(V+E)
邻接矩阵存储时间复杂度O(V^2)

public static void breadthFirstSearch() {
        Deque<Map<String, Object>> nodeDeque = new ArrayDeque<>();
        Map<String, Object> node = new HashMap<>();
        nodeDeque.add(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.peekFirst();
            List<Map<String, Object>> children = getChildren(node);
            if (children!=null&&!children.isEmpty()) {
                for(Map child:children) {
                    nodeDeque.add(child);
                }
            }
        }
    }

深度优先搜索（DFS）

深度优先搜索使用堆的数据结构，先进后出

遍历过程

将A节点压入堆，stack(A)
将A节点弹出，同时将A的子节点C，B压入堆中，此时B在堆的顶部，stack(B,C)
将B节点弹出，同时将B节点的子节点E，D压入堆中，此时D在堆的顶部，stack(D,E,C)
将D节点弹出，没有子节点压入，此时E在堆的顶部，stack(E,C)
将E节点弹出，同时将E的子节点I压入，此时I在堆的顶部，stack(I,C)
…...直到遍历完成

其过程是对每个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

时间复杂度

邻接表存储时间复杂度O(V+E)
邻接矩阵存储时间复杂度O(V^2)

public static void depthFirstSearch() {
        Stack<Map<String, Object>> nodeStack = new Stack<>();
        Map<String, Object> node = new HashMap<>();
        nodeStack.add(node);
        while (!nodeStack.isEmpty()) {
            node = nodeStack.pop();
            List<Map<String, Object>> children = getChildren(node);
            if (children!=null&&!children.isEmpty()) {
                for(Map child:children) {
                    nodeStack.push(child);
                }
            }
        }
        
    }

动态规划

Dijkstra算法

每次找到离源点最近的一个点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

不允许负权边，有向无环加权图

时间复杂度O((M+N)logn)

//Dijkstra算法核心语句
        for(i=1;i<=n-1;i++)
        {
            //找到离1号顶点最近的顶点
            min=inf;
            for(j=1;j<=n;j++)
            {
                if(book[j]==0 && dis[j]<min)
                {
                    min=dis[j];
                    u=j;
                }
            }
            book[u]=1;
            for(v=1;v<=n;v++)
            {
                if(e[u][v]<inf)
                {
                    if(dis[v]>dis[u]+e[u][v])
                        dis[v]=dis[u]+e[u][v];
                }
            }
        }

Floyd算法

解决任意两点间最短路径的一种算法。

可以正确处理有向图和负权图（不可存在负权回路）的最短路径问题。

时间复杂度O(n³)

空间复杂度O(n²)

for(k=1;k<=n;k++)
       for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])
                e[i][j]=e[i][k]+e[k][j];

树

树是连通的无环图

二叉树有两种特殊的树：满二叉树和完全二叉树

满二叉树每个内部节点都有两个儿子，一个深度为h的满二叉树有2^(h+1)-1个节点

完全二叉树除了h层以外，其余各层节点数都达到最大，一个完全二叉树有N个节点，高度就为log2n，最多log2n+1个节点

完全二叉树的应用就是堆，如果父节点都比子节点小，称为最小堆，反之则为最大堆。

二叉树的存储

顺序存储：数组和链表串列

二叉链表存储

二叉树中根到叶子的路径

public void routeOfTree(Node node) {
        if (node == null) {
            return;
        }
        queue.offer(node);// 将当前节点入队
        if (node.lChild == null && node.rChild == null) {// 如果左右子节点为空，即左右节点均为叶子节点，则遍历并且打印节点
            Iterator<Node> iterator = queue.iterator();
            while (iterator.hasNext()) {
                System.out.print(iterator.next().data + "====>");
            }
            System.out.println();
        }
        // 否则继续遍历左右子节点，直到遍历到叶子节点
        routeOfTree(node.lChild);
        routeOfTree(node.rChild);
        // 将该节点出队
        queue.poll();
    }

二叉树的深度

如果只有一个节点，深度为1，如果只有左节点，深度为左节点深度+1，如果只有右节点，深度为右边节点深度+1，如果都有，则比较左右子节点深度，较大的+1

public int getTreeDepth(Node node) {
        if (node.lChild == null && node.rChild == null) {
            return 1;
        }
        int left = 0, right = 0;
        if (node.lChild != null) {
            left = getTreeDepth(node.lChild);
        }
        if (node.rChild != null) {
            right = getTreeDepth(node.rChild);
        }
        return Math.max(left, right) + 1;
}

二叉树的宽度

使用队列，层次遍历二叉树，在上一层遍历完之后，下一层所有节点都已经放入队列中，此时队列中元素个数就是下一层的宽度

public int getMaxTreeWidth(Node root) {
        if (root==null) {
            return 0;
        }
        int maxWidth = 1;
        queue.add(root);//入队
        while (true) {
            int len = queue.size();//当前层的节点个数
            if (len==0) {
                break;
            }
            while (len > 0) {//如果当前层还有节点
                Node node = queue.poll();
                len--;
                if (node.lChild!=null) {
                    queue.add(node.lChild);//下一层左节点入队
                }
                if (node.rChild!=null) {
                    queue.add(node.rChild);//下一层右节点入队
                }
            }
            maxWidth = Math.max(maxWidth, queue.size());
        }
        return maxWidth;
    }

二叉树的层次遍历

按照从上到下，从左到右的次序进行遍历，遍历完一层再遍历下一层，又叫广度优先搜索，需要用到队列。

public static void levelTerator(BiTree root) {
        if (root == null) return;
        LinkedList<BiTree> queue = new LinkedList<>();
        BiTree current = null;
        queue.offer(root);// 将根节点入队
        while (!queue.isEmpty()) {
            current = queue.poll();// 出对对头元素并访问
            if (current.left != null) {
                queue.offer(current.left);// 如果当前节左节点不为空，则入队
            }
            if (current.right != null) {
                queue.offer(current.right);// 如果当前右边节点不为空，则入队
            }
        }
}

class BiTree {
    BiTree left;
    BiTree right;
    int val;
    public BiTree(int val) {
        this.val = val;
    }
}

二叉树节点个数

左节点和右节点个数之和再+1

public int numOfTree(Node node) {
        if (node == null) {
            return 0;
        }
        return numOfTree(node.lChild) + numOfTree(node.rChild) + 1;
}

两棵树是否相同

都为空，返回true，一个为空另一个不为空，返回false，两个当前节点不相等，返回false，遍历两个数的左右子树判断是否相等。

public boolean judgeSame(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if ((node1 == null && node2 != null) || (node1 != null && node2 == null)) {
            return false;
        }
        if (node1.data != node2.data) {
            return false;
        }
        return judgeSame(node1.lChild, node2.lChild) && judgeSame(node1.rChild, node2.rChild);
}

二叉树的转换

使用临时二叉树存储，将左右子树交换，并递归调用遍历左子树和右子树进行转换

public void reverse(Node node) {
        if (node==null) {
            return ;
        }
        Node temp = null;
        temp = node.rChild;
        node.rChild = node.lChild;
        node.lChild = temp;
        reverse(node.lChild);
        reverse(node.rChild);
    }

有序数组转换成二叉搜索树

红黑树

红黑树本质是一棵二叉查找树

二叉查找树

又称有序树和排序二叉树，指一棵空树或者具有某些性质的二叉树

若任意节点的左子树不空，则左子树上所有节点均小于根节点的值
若任意右子树不空，则右子树上所有节点均大于根节点的值
任意节点的左，右子树分别为二叉查找树
没有键值相等的节点

一棵n个节点的二叉查找树高度为logn，时间复杂度为O(logn)

红黑树通过一些性质使得树相对平衡，使得最终查找，插入，删除时间复杂度最坏情况下依然为O(logn)

红黑树

红黑树本质上是一棵二叉查找树，在此基础上增加了着色和相关性质使得红黑树相对平衡，从而保证红黑树的查找，插入，删除的时间复杂度最坏为O(logn)

一棵n个节点的红黑树保持高度始终为logn

每个节点要么红，要么黑
根节点是黑的
每个叶节点（树尾端NIL指针或者NULL节点）是黑的
如果一个节点是红的，那么他的儿子节点都是黑的
任一节点，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点

叶节点和NULL节点不包含数据，只是充当树在此结束的指示

红黑树的插入和插入修复：

首先查找节点要插入的位置，然后进行插入，插入完成之后还要保持红黑树的平衡，进行插入修复操作。

插入：如果要插入的节点比当前遍历到的节点小，则在他的左子树继续查找，否则在其右子树中查找，当找到要插入的位置时，如果还是比当前节点小，则作为它的左节点，否则作为它的右节点。

修复：

http://www.cnblogs.com/skywang12345/p/3624343.html

https://tech.meituan.com/redblack-tree.html

http://www.jianshu.com/p/30ab2a7fa5a3

http://www.voidcn.com/article/p-snsywpzh-tr.html

二叉搜索树

任意节点值大于左节点值，小于右节点值，使用中序遍历

每次插入的都是叶子节点

查找二叉搜索树中最大值和最小值

public static Node SearchMax(Node node) {
        if (node==null) {
            return null;
        }
        while ( node.rChild!=null) {
            node = node.rChild;
        }
        return node;
    }
    public static Node searchMin(Node node) {
        if (node==null) {
            return null;
        }
        while ( node.lChild!=null) {
            node = node.lChild;
        }
        return node;
    }

二叉搜索树中查找元素

public boolean searchKey(String key,Node node) {
        if (node==null) {
            return false;
        }
        int result = key.compareTo(node.data);
        if (result>0) {
            return searchKey(key, node.rChild);
        }else if (result<0) {
            return searchKey(key, node.lChild);
        }else {
            return true;
        }
    }

二叉搜索树的插入

   public void insert(T t)  
   {  
       rootTree = insert(t, rootTree);  
   }  
    /**在某个位置开始判断插入元素*/  
   public BinaryNode<T> insert(T t,BinaryNode<T> node)  
   {  
       if(node==null)  
       {  
           //新构造一个二叉查找树  
           return new BinaryNode<T>(t, null, null);  
       }  
       int result = t.compareTo(node.data);  
       if(result<0)  
          node.left= insert(t,node.left);  
       else if(result>0)  
          node.right= insert(t,node.right);  
       else  
           ;//doNothing  
       return node;  
   }

二叉搜索树中删除元素

如果要删除的节点为叶子节点，直接删除

如果要删除的节点只包含左子树或者右子树，直接将其左子树或者右子树的父节点设置为该节点的左子树或者右子树即可，不会破坏树的结构

如果该节点既有左子树又有右子树，则要找到该节点右子树的最小值并将其设置到要删除的节点，然后将其右边子树的最小的该节点进行删除即可

public void remove(T t)  
   {  
       rootTree = remove(t,rootTree);  
   } /**在某个位置开始判断删除某个结点*/  
   public BinaryNode<T> remove(T t,BinaryNode<T> node)  
   {  
       if(node == null)  
           return node;//没有找到,doNothing  
       int result = t.compareTo(node.data);  
       if(result>0)  
           node.right = remove(t,node.right);  
       else if(result<0)  
           node.left = remove(t,node.left);  
       else if(node.left!=null&&node.right!=null)  
       {  
           node.data = findMin(node.right).data;  
           node.right = remove(node.data,node.right);  
       }  
       else  
           node = (node.left!=null)?node.left:node.right;  
       return node;  
             
   }

http://blog.csdn.net/luckyxiaoqiang/article/details/7518888#topic14

图和树

图