图算是数据结构中比较难的问题，但是在实际中解决的问题也更多。

其中，在图结构中涉及的问题主要有：

图的存储：

• 邻接表(Adjacency list)：为每个节点建立一个链表存放与之连接的点.
• 邻接矩阵(Adjacency matrix)：n*n的矩阵，有边的是1，无边的是0.

最短路径：

• Dijkstra：记录起点能够到达的所有节点的最短路径，这样，我们要找的终点一定在其中啊。
  • DIST(w) = min(DIST(w), DIST(u) + c(u, w))
  • 
  • 
  • 代码实现示例：
  • package com.realise;import java.util.Arrays;public class Dijkstra {    static int max = 10000;        public static int[] dijkstra(int[][] edge) {        int n = edge.length;        int[] res = new int[n];        for(int i=0; i

     
• Floyd：又称插点法，可以寻找任意两点间的最短路径，允许图中带负权值的边，但不允许包含负权值的边组成的回路。
  • 
  • 代码实现示例：
  • package com.realise;/** * Floyd算法的实现 * @author  * */public class Floyd {    static int Max = 1000;        public static int[][] floydRealise(int[][] edge) {        int n = edge.length;        int[][] a = new int[n][n];        int[][] path = new int[n][n];        //Initialize         for(int i=0; i

     

最小生成树

• Prim算法：A为要求的生成树，将要计入到A中的下一条边(u, v)，应是E种一条不在A中且最小成本的边。
  •            
  • 代码示例：华为的一道笔试题，使用Prim解决的，作为本个算法的示例程序：
  • import java.util.Scanner;import java.util.Vector;/** * 沿海有N个岛屿，为方便岛与岛之间的沟通，现规划对这些岛屿进行建桥， * 建桥的消耗和岛屿之间的距离成正比，如何规划才能使每个桥梁都能连通，且消耗最少 * @author  * */public class Main {        public static int prim(int[][] val) {        if(val == null || val.length == 0 || val.length == 1)            return 0;        boolean[] visited = new boolean[val.length];        for(int i=0; i
              
                v = new Vector
               
                ();        v.add(0);        do {            int weight = Integer.MAX_VALUE;            int temp = -1;            for(Integer i : v) {                for(int j=0; j
               
              

     
•  Kruskal算法：将图中所有边的权重按大小排序，然后在每次添加放入边中以不构成回路为前提，每次选择一条权重最小的边加入生成树中。
  • 为了快速判断候选边e的加入是否会形成环，可以使用并查集。时间复杂度为：O(eloge).

图的搜索(遍历)：其中要特别注意隐式图的搜索，一些问题乍一看可能不是图的问题，但是其实可以用图的方法解决！！！

• 广度优先搜索BFS：辅助数据结构为队列，与树的层次遍历类似

 

• 深度优先搜索DFS：辅助数据结构为栈，与树的先序/中序/后序遍历类似

 

• 隐式图：在实践中，往往一看不是关于图的问题，但如果给定一个起始状态和一些规则，求解决方案的问题：往往可以根据这些规则，将各个状态建立边，然后BFS/DFS搜索方法，在解空间中搜索。

 

几个经典的问题：

• 单词变换问题Word Ladder。
  • Given a pattern and a string str, find if str follows the same pattern.

    Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

    Examples:

    1. pattern = "abba", str = "dog cat cat dog" should return true.
    2. pattern = "abba", str = "dog cat cat fish" should return false.
    3. pattern = "aaaa", str = "dog cat cat dog" should return false.
    4. pattern = "abba", str = "dog dog dog dog" should return false.
    代码如下：
    • public class Solution {    public boolean wordPattern(String pattern, String str) {            Map
                  
                    map = new HashMap
                   
                     ();            Set
                    
                      set = new HashSet
                     
                      ();            char[] ch = pattern.toCharArray();            String[] strr = str.split(" ");            if(ch.length != strr.length)                return false;            for(int i=0; i
                     
                    
                   
                  
• 周围区域问题。
  • • 代码：
    • import java.util.LinkedList;import java.util.Queue;class Node {    int x;    int y;    public Node(int x, int y) {        this.x = x;        this.y = y;    }}class Regions {    private int[] rowdi = {-1, 1, 0, 0};    private int[] coldi = {0, 0, -1, 1};        /**     * BFS.      * Search begin from the edge to the interior.      * @param val     * @return     */    public int[][] check(int[][] val) {        if(val == null || val.length == 0 || val[0].length == 0)            return val;        Queue
                  
                    q = new LinkedList
                   
                    ();        int row = val.length;        int col = val[0].length;        for(int i=0; i
                    
                     = 0 && n.y+coldi[i] >= 0) {                    if(val[n.x+rowdi[i]][n.y+coldi[i]] == 0) {                        Node t = new Node(n.x+rowdi[i], n.y+coldi[i]);                        q.add(t);                        val[n.x+rowdi[i]][n.y+coldi[i]] = 2;                    }                }            }        }        for(int i=0; i
                    
                   
                  
• 八皇后问题。
  • • 代码：
    • package com.eight;import java.util.ArrayList;import java.util.Arrays;class EightQueen {    private int N; //The number of queens.    private boolean[] column;    private boolean[] maind;    private boolean[] secondaryd;    private ArrayList
                  
                    result = new ArrayList
                   
                    ();                /**     * Initial the column, main diagonal, secondary diagonal to false,     * which means there is no queen everywhere.     * @param N     */    public void initQ(int N) {        this.N = N;        column = new boolean[N];        maind = new boolean[2 * N - 1];        secondaryd = new boolean[2 * N - 1];        int i = 0;        for(i=0; i
                    
                      getResult() {        return result;    }}public class Queens {    public static void main(String[] args) {        EightQueen q = new EightQueen();        q.initQ(8); // It is a eight queens problem.        q.queens();            }}//Some output instances:[0, 4, 7, 5, 2, 6, 1, 3][0, 5, 7, 2, 6, 3, 1, 4][0, 6, 3, 5, 7, 1, 4, 2][0, 6, 4, 7, 1, 3, 5, 2][1, 3, 5, 7, 2, 0, 6, 4][1, 4, 6, 0, 2, 7, 5, 3][1, 4, 6, 3, 0, 7, 5, 2][1, 5, 0, 6, 3, 7, 2, 4][1, 5, 7, 2, 0, 3, 6, 4][1, 6, 2, 5, 7, 4, 0, 3][1, 6, 4, 7, 0, 3, 5, 2][1, 7, 5, 0, 2, 4, 6, 3][2, 0, 6, 4, 7, 1, 3, 5]
                    
                   
                  
• 数独问题。
  • • 代码：
    • import java.util.Stack;class Help {    int row;    int col;    int val;}public class Sudoku {    /**     * Use stack store the roads.     * @param chess     * @return     */    public static int[][] getSudoku(int[][] chess) {        Stack
                  
                    stack = new Stack
                   
                    ();        int val = -1;        for(int i=0; i<9; i++) {            for(int j=0; j<9; j++) {                if(chess[i][j] != 0)                    continue;                boolean flag = false;                int k;                if(val == -1)                    k = 0;                else                     k = val+1;                for(; k<10; k++) {                    if(isValid(k, i, j, chess)) {                        Help h = new Help();                        h.row = i;                        h.col = j;                        h.val = k;                        stack.add(h);                        chess[i][j] = k;                        val = -1;                        flag = true;                                            }                    if(flag == true)                        k = 10;                }                if(flag == false && !stack.isEmpty()) { //There is no road, backtracking                    Help h = stack.pop();                    i = h.row;                    j = h.col-1;                    val = h.val;                    chess[i][j+1] = 0;                }            }        }        return chess;    }        /**     * Judge if it is valid when chess[row][col] = k.     * @param k     * @param row     * @param col     * @param chess     * @return     */    private static boolean isValid(int k, int row, int col, int[][] chess) {        for(int i=0; i<9; i++)            if(chess[row][i] == k)                return false;        for(int i=0; i<9; i++)             if(chess[i][col] == k)                return false;        int r = row/3, c = col/3;        for(int i=r*3; i
                   
                  

• 所有括号的匹配问题。

  • • 代码：
    • /**     * Given the number N, return all of the correct brackets.     * @param n     * @return     */    @SuppressWarnings("unchecked")    public static ArrayList
                  
                    getBracketsOfN(int n) {        @SuppressWarnings("rawtypes")        ArrayList[] dp = new ArrayList[n+1];        for(int i=0; i
                   
                    ();        dp[0].add("");        dp[1].add("()");        if(n == 0)             return dp[0];        if(n == 1)             return dp[1];        int count = 2;        while(count < n+1) {            ArrayList
                    
                      lcount = dp[count];            for(int i=0; i
                     
                       l1 = dp[i];                ArrayList
                      
                        l2 = dp[count-i-1];                for(int j=0; j