原创

温馨提示:
本文最后更新于 2022年06月17日,已超过 9 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

为什么要有图

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

图的举例说明

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

image-20220531163451483

图的分类

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

图的常用概念

  1. 顶点:(vertex)
  2. 边:(edge)
  3. 路劲
  4. 无向图,右向图

图的表示方法

  1. 领接矩阵:使用矩阵表示的(二维数组)
  2. 邻接表:使用一个一维数组和链表表示

image-20220531164531371

图的代码实现

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

思路分析

  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;
            }
        }
    }
}
正文到此结束