图

为什么要有图

1. 线性表局限于一个前驱和一个后继
2. 树也只能有一个直接前驱也就是父节点
3. 当我们需要表示多对多的关系时， 这里我们就用到了图

图的举例说明

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图：

图的分类

• 有向图：有方向的图，像上面的这个一样
• 无像图：没有方向的图，每一个结点都是互相☞的
• 带权图：每一个边都有对应的权值（每一条边上都有对应的数字）

图的常用概念

1. 顶点：（vertex）
2. 边：（edge）
3. 路劲
4. 无向图，右向图

图的表示方法

1. 领接矩阵：使用矩阵表示的（二维数组）
2. 邻接表：使用一个一维数组和链表表示

图的代码实现

使用邻接矩阵的方式实现图的创建

思路分析

1. 给出需要创建表的数据，这里使用string的数据进行表示，为了方便给出的数据应该是一个数组，然后使用遍历的方式就可以将数据创建成为一个表
2. 顶点的表示：因为图里面包含顶点，所以就需要将每一个顶点保存下来，可以使用数组，但是扩容不方便，就是用集合将每一个顶点保存下来
3. 边的表示：图最关键的就是对边的表示，我们将记录每一个顶点之间的边，当然有些顶点之间是不连接的，这里就使用二维数组进行表示，将顶点的所有组合情况列举出来，使用二维数组，然后用1表示他们之间可以连通，0表示他们之间不可以连通
4. 创建几个图常用的方法

package graph;

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

/**
 * 
 * @author Mr.sun
 *
 */
public class Graph {
    //首先创建一个string的集合来存储定点
    //二维数组来存储图对应的二阶矩阵
    List<String> vertexList;
    int[][] edge;
    int numOfEdge;
    //常用的方法
    //返回结点的个数
    public int vertexNum() {
        return vertexList.size();
    }
    //得到边的数目
    public int edgeNum() {
        return edge.length;
    }
    //返回下标对应的点
    public String vertexReturn(int i) {
        return vertexList.get(i);
    }
    //返回v和v2的权值
    public int getWeight(int v1,int v2) {
        return edge[v1][v2];
    }
    //显示图对应的矩阵
    public void showEdge() {
        for(int[] link : edge) {
            System.err.println(Arrays.toString(link));
        }
    }

    //构造器初始化顶点和边
    public Graph(int n) {
        vertexList = new ArrayList<String>(n);
        edge = new int[n][n];
        numOfEdge = 0;
    }
    //添加顶点
    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }
    /**
     * 
     * @param v1表示第几个点对应的下标
     * @param v2表示第几个点对应的下标
     * @param weight表示是否连接
     */
    //添加边
    public void addEdge(int v1,int v2,int weight) {
        edge[v1][v2] = weight;
        edge[v2][v1] = weight;
        //将边的数目加一
        numOfEdge++;
    }
    //深度优先算法dfs

    public static void main(String[] args) {
        //测试图是否创建成功
        int n = 5;
        String[] str = {"a","d","e","g","s"};
        Graph graph = new Graph(n);
        for(String s :str) {
            graph.addVertex(s);
        }
        //添加边
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 2, 1);
        graph.addEdge(1, 4, 1);
        graph.addEdge(1, 3, 1);
        graph.showEdge();
    }
}

注 ：因为无法让程序确定边是否连通，最后依然需要进行手动连通

图的深度优先遍历（dfs）

遍历就是指对图中每一个节点的访问

深度优先遍历的思想

1. 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
2. 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
3. 显然，深度优先搜索是一个递归的过程

算法步骤

1. 访问初始结点v，并标记结点v为已访问。
2. 查找结点v的第一个邻接结点w。
3. 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
4. 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5. 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

代码实现思路

public class dfsTest {
    // 待排序的数
    int[] array = { 1, 2, 3, 4, 5 };
    // 存放数字的盒子
    int[] a = new int[10];
    int[] b = new int[10];

    public static void main(String[] args) {
        // 调用函数
        new dfsTest().dfs(1);
    }

    // 求一个数的全排列，从哪一个地方开始放数字
    public void dfs(int n) {
        // 结束条件，条件通过，说明已经将最后一个数字都放进了盒子里面
        if (n == 3 + 1) {
            // 此时就将盒子里面的数字进行输出,盒子里面已经存进去的所有的数字
            for (int i =1 ; i <=array.length; i++) {
                System.out.print(a[i]);
            }
            System.out.println();
            // 将所有的数字遍历完成之后，就应该进行回溯
            return;// 返回上一层将数字取出来
        }
        // 将手里面的扑克放在盒子里面，并且每一次都是从第一张开始放，如果没有放过就将这一张放在里面
        for (int i = 0; i < array.length; i++) {
            // 因为每一次都是从第一个数字开始取的，所以我们应该首先判断一下该数字是否被取过
            if (b[i] == 0) {
                a[n] = array[i];
                // 记录这个数字已经被放过
                b[i] = 1;
                // 继续从未放的数字中放
                dfs(n + 1);
                // 将数字取出来，就是把那个数字标记为未放入
                b[i] = 0;
            }
        }
    }
}