【数据结构基础】之图的介绍,生动形象,通俗易懂,算法入门必看(下)

简介: 【数据结构基础】之图的介绍,生动形象,通俗易懂,算法入门必看(下)

2️⃣深度优先搜索


🍀(1)深度优先搜索介绍


图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。

它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

深度优先搜索是一个递归的过程。


🍀(2)深度优先搜索图解


无向图的深度优先搜索


19dc696f90464f749bdd027d45a76bd5.png


对上面的图G1进行深度优先遍历,从顶点A开始

0e07ae5e1e454be5a8aa6543731970d0.png


第1步:访问A。

第2步:访问(A的邻接点)C。 在第1步访问A之后,接下来应该访问的是A的邻接点,即"C,D,F"中的一个。但在本文的实现中,顶点ABCDEFG是按照顺序存储,C在"D和F"的前面,因此,先访问C。

第3步:访问(C的邻接点)B。 在第2步访问C之后,接下来应该访问C的邻接点,即"B和D"中一个(A已经被访问过,就不算在内)。而由于B在D之前,先访问B。

第4步:访问(C的邻接点)D。 在第3步访问了C的邻接点B之后,B没有未被访问的邻接点;因此,返回到访问C的另一个邻接点D。

第5步:访问(A的邻接点)F。 前面已经访问了A,并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)";因此,此时返回到访问A的另一个邻接点F。

第6步:访问(F的邻接点)G。

第7步:访问(G的邻接点)E。

因此访问顺序是:A -> C -> B -> D -> F -> G -> E


有向图的深度优先搜索:


831a3f8f519d43a1b4317a7b1c828e25.png


对上面的图G2进行深度优先遍历,从顶点A开始。


79388fd8e0264a3e92d173a20b25a61f.png



第1步:访问A。

第2步:访问B。 在访问了A之后,接下来应该访问的是A的出边的另一个顶点,即顶点B。

第3步:访问C。在访问了B之后,接下来应该访问的是B的出边的另一个顶点,即顶点C,E,F。在本文实现的图中,顶点ABCDEFG按照顺序存储,因此先访问C。

第4步:访问E。 接下来访问C的出边的另一个顶点,即顶点E。

第5步:访问D。 接下来访问E的出边的另一个顶点,即顶点B,D。顶点B已经被访问过,因此访问顶点D。

第6步:访问F。 接下应该回溯"访问A的出边的另一个顶点F"。

第7步:访问G。

因此访问顺序是:A -> B -> C -> E -> D -> F -> G


🍀(3)深度优先搜索代码实现

public class Graph {
    /**
     * 定义顶点的抽象
     * @param <T>
     */
    public static class Vertex<T>{
        // 要保存的数据
        private T t;
        // 其他和我管理的邻接节点
        private List<Vertex<T>> neighborList;
        private boolean visited = false;
        public Vertex(T t) {
            this.t = t;
        }
    }
    // dfs 深度优先遍历算法
    public static <T> void dfs(Vertex<T> vertex){
        // 1、定义一个临时存储的空间
        Stack<Vertex<T>> stack = new Stack<>();
        // 2、将第一个顶点放入栈中
        stack.push(vertex);
        while (!stack.isEmpty()){
            // 3、将栈顶的元素取出
            Vertex<T> temp = stack.pop();
            // 4、执行操作
            if(!temp.visited){
                System.out.println(temp.t);
                temp.visited = true;
            }
            // 5、将邻接节点压栈
            if(temp.neighborList != null){
                stack.addAll(temp.neighborList);
            }
        }
    }
}

四、最小生成树


1️⃣最小生成树概念


在含有n个顶点的连通图中选择n-1条边,构成一棵极小连通子图,并使该连通子图中n-1条边上权值之和达到最小,则称其为连通网的最小生成树。

539091dd66ec44a2854e990e7670551c.png


例如,对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。


e18e3dcabcd4499d841dbd81bc6adf70.png


2️⃣克鲁斯卡尔(Kruskal)算法


🍀(1)克鲁斯卡尔算法介绍



克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。

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

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


🍀(2)克鲁斯卡尔算法图解


以上图G4为例,来对克鲁斯卡尔进行演示(假设,用数组R保存最小生成树结果)。

01ba0409e2d245f8a4c5f8e18ff6f429.png


第1步:将边<E,F>加入R中。 边<E,F>的权值最小,因此将它加入到最小生成树结果R中。

第2步:将边<C,D>加入R中。 上一步操作之后,边<C,D>的权值最小,因此将它加入到最小生成树结果R中。

第3步:将边<D,E>加入R中。 上一步操作之后,边<D,E>的权值最小,因此将它加入到最小生成树结果R中。

第4步:将边<B,F>加入R中。上一步操作之后,边<C,E>的权值最小,但<C,E>会和已有的边构成回路;因此,跳过边<C,E>。同理,跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。

第5步:将边<E,G>加入R中。 上一步操作之后,边<E,G>的权值最小,因此将它加入到最小生成树结果R中。

第6步:将边<A,B>加入R中。上一步操作之后,边<F,G>的权值最小,但<F,G>会和已有的边构成回路;因此,跳过边<F,G>。同理,跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。

此时,最小生成树构造完成!它包括的边依次是:<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。


🍀(3)克鲁斯卡尔算法代码实现


这里选取"邻接矩阵"对克鲁斯卡尔算法进行说明。


// 边的结构体
private static class EData {
    char start; // 边的起点
    char end;   // 边的终点
    int weight; // 边的权重
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}
// 邻接矩阵边对应的结构体
public class MatrixUDG {
    private int mEdgNum;        // 边的数量
    private char[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵
    private static final int INF = Integer.MAX_VALUE;   // 最大值
    ...
}
/*
 * 克鲁斯卡尔(Kruskal)最小生成树
 */
public void kruskal() {
    int index = 0;                      // rets数组的索引
    int[] vends = new int[mEdgNum];     // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
    EData[] rets = new EData[mEdgNum];  // 结果数组,保存kruskal最小生成树的边
    EData[] edges;                      // 图对应的所有边
    // 获取"图中所有的边"
    edges = getEdges();
    // 将边按照"权"的大小进行排序(从小到大)
    sortEdges(edges, mEdgNum);
    for (int i=0; i<mEdgNum; i++) {
        int p1 = getPosition(edges[i].start);      // 获取第i条边的"起点"的序号
        int p2 = getPosition(edges[i].end);        // 获取第i条边的"终点"的序号
        int m = getEnd(vends, p1);                 // 获取p1在"已有的最小生成树"中的终点
        int n = getEnd(vends, p2);                 // 获取p2在"已有的最小生成树"中的终点
        // 如果m!=n,意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
        if (m != n) {
            vends[m] = n;                       // 设置m在"已有的最小生成树"中的终点为n
            rets[index++] = edges[i];           // 保存结果
        }
    }
    // 统计并打印"kruskal最小生成树"的信息
    int length = 0;
    for (int i = 0; i < index; i++)
        length += rets[i].weight;
    System.out.printf("Kruskal=%d: ", length);
    for (int i = 0; i < index; i++)
        System.out.printf("(%c,%c) ", rets[i].start, rets[i].end);
    System.out.printf("\n");
}


3️⃣普里姆(Prim)算法


🍀(1)普里姆算法介绍


普里姆(Prim)算法,是用来求加权连通图的最小生成树的算法。

基本思想 : 对于图G而言,V是所有顶点的集合;现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边。从所有uЄU,vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边。


🍀(2)普里姆算法图解


f65ec97269cf49e4a5a3a439a77a83a2.png

以上图G4为例,来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。


c59b6848b87c4dedbf49e63f1330c597.png


初始状态:V是所有顶点的集合,即V={A,B,C,D,E,F,G};U和T都是空!


第1步:将顶点A加入到U中。 此时,U={A}。

第2步:将顶点B加入到U中。 上一步操作之后,U={A}, V-U={B,C,D,E,F,G};因此,边(A,B)的权值最小。将顶点B添加到U中;此时,U={A,B}。

第3步:将顶点F加入到U中。 上一步操作之后,U={A,B}, V-U={C,D,E,F,G};因此,边(B,F)的权值最小。将顶点F添加到U中;此时,U={A,B,F}。

第4步:将顶点E加入到U中。 上一步操作之后,U={A,B,F}, V-U={C,D,E,G};因此,边(F,E)的权值最小。将顶点E添加到U中;此时,U={A,B,F,E}。

第5步:将顶点D加入到U中。 上一步操作之后,U={A,B,F,E},V-U={C,D,G};因此,边(E,D)的权值最小。将顶点D添加到U中;此时,U={A,B,F,E,D}。

第6步:将顶点C加入到U中。 上一步操作之后,U={A,B,F,E,D}, V-U={C,G};因此,边(D,C)的权值最小。将顶点C添加到U中;此时,U={A,B,F,E,D,C}。

第7步:将顶点G加入到U中。 上一步操作之后,U={A,B,F,E,D,C}, V-U={G};因此,边(F,G)的权值最小。将顶点G添加到U中;此时,U=V。

此时,最小生成树构造完成!它包括的顶点依次是:A B F E D C G。


🍀(3)普里姆算法代码实现


这里以"邻接矩阵"为例对普里姆算法进行说明。


// 邻接矩阵对应的结构体
public class MatrixUDG {
    private char[] mVexs;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵
    private static final int INF = Integer.MAX_VALUE;   // 最大值
    ...
}
/*
 * prim最小生成树
 *
 * 参数说明:
 *   start -- 从图中的第start个元素开始,生成最小树
 */
public void prim(int start) {
    int num = mVexs.length;         // 顶点个数
    int index=0;                    // prim最小树的索引,即prims数组的索引
    char[] prims  = new char[num];  // prim最小树的结果数组
    int[] weights = new int[num];   // 顶点间边的权值
    // prim最小生成树中第一个数是"图中第start个顶点",因为是从start开始的。
    prims[index++] = mVexs[start];
    // 初始化"顶点的权值数组",
    // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
    for (int i = 0; i < num; i++ )
        weights[i] = mMatrix[start][i];
    // 将第start个顶点的权值初始化为0。
    // 可以理解为"第start个顶点到它自身的距离为0"。
    weights[start] = 0;
    for (int i = 0; i < num; i++) {
        // 由于从start开始的,因此不需要再对第start个顶点进行处理。
        if(start == i)
            continue;
        int j = 0;
        int k = 0;
        int min = INF;
        // 在未被加入到最小生成树的顶点中,找出权值最小的顶点。
        while (j < num) {
            // 若weights[j]=0,意味着"第j个节点已经被排序过"(或者说已经加入了最小生成树中)。
            if (weights[j] != 0 && weights[j] < min) {
                min = weights[j];
                k = j;
            }
            j++;
        }
        // 经过上面的处理后,在未被加入到最小生成树的顶点中,权值最小的顶点是第k个顶点。
        // 将第k个顶点加入到最小生成树的结果数组中
        prims[index++] = mVexs[k];
        // 将"第k个顶点的权值"标记为0,意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
        weights[k] = 0;
        // 当第k个顶点被加入到最小生成树的结果数组中之后,更新其它顶点的权值。
        for (j = 0 ; j < num; j++) {
            // 当第j个节点没有被处理,并且需要更新时才被更新。
            if (weights[j] != 0 && mMatrix[k][j] < weights[j])
                weights[j] = mMatrix[k][j];
        }
    }
    // 计算最小生成树的权值
    int sum = 0;
    for (int i = 1; i < index; i++) {
        int min = INF;
        // 获取prims[i]在mMatrix中的位置
        int n = getPosition(prims[i]);
        // 在vexs[0...i]中,找出到j的权值最小的顶点。
        for (int j = 0; j < i; j++) {
            int m = getPosition(prims[j]);
            if (mMatrix[m][n]<min)
                min = mMatrix[m][n];
        }
        sum += min;
    }
    // 打印最小生成树
    System.out.printf("PRIM(%c)=%d: ", mVexs[start], sum);
    for (int i = 0; i < index; i++)
        System.out.printf("%c ", prims[i]);
    System.out.printf("\n");
}


五、拓扑排序


1️⃣拓扑排序介绍


拓扑排序(Topological Order)是指,将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

通过简单的例子进行说明:例如,一个项目包括A、B、C、D四个子部分来完成,并且A依赖于B和D,C依赖于D。现在要制定一个计划,写出A、B、C、D的执行顺序。这时,就可以利用到拓扑排序,它就是用来确定事物发生的顺序的。

在拓扑排序中,如果存在一条从顶点A到顶点B的路径,那么在排序结果中B出现在A的后面。


2️⃣拓扑排序的算法图解


拓扑排序算法的基本步骤:

1.构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological);

2.把所有没有依赖顶点的节点放入Q;

3.当Q还有顶点的时候,执行下面步骤:

3.1 从Q中取出一个顶点n(将n从Q中删掉),并放入T(将n加入到结果集中);

3.2 对n每一个邻接点m(n是起点,m是终点):

3.2.1 去掉边<n,m>;

3.2.2 如果m没有依赖顶点,则把m放入Q。

注:顶点A没有依赖顶点,是指不存在以A为终点的边。


f8d3510de6e9493c8d47f3cde5aa27c1.png


以上图为例,来对拓扑排序进行演示。


35fcb8df9c5746fe8799744ddc2a1d87.png


第1步:将B和C加入到排序结果中。顶点B和顶点C都是没有依赖顶点,因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储,因此先访问B,再访问C。访问B之后,去掉边<B,A>和<B,D>,并将A和D加入到队列Q中。同样的,去掉边<C,F>和<C,G>,并将F和G加入到Q中。

(1) 将B加入到排序结果中,然后去掉边<B,A>和<B,D>;此时,由于A和D没有依赖顶点,因此并将A和D加入到队列Q中。

(2) 将C加入到排序结果中,然后去掉边<C,F>和<C,G>;此时,由于F有依赖顶点D,G有依赖顶点A,因此不对F和G进行处理。

第2步:将A,D依次加入到排序结果中。第1步访问之后,A,D都是没有依赖顶点的,根据存储顺序,先访问A,然后访问D。访问之后,删除顶点A和顶点D的出边。

第3步:将E,F,G依次加入到排序结果中。

因此访问顺序是:B -> C -> A -> D -> E -> F -> G


3️⃣拓扑排序的代码实现


拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。

// 邻接表对应的结构体
public class ListDG {
    // 邻接表中表对应的链表的顶点
    private class ENode {
        int ivex;       // 该边所指向的顶点的位置
        ENode nextEdge; // 指向下一条弧的指针
    }
    // 邻接表中表的顶点
    private class VNode {
        char data;          // 顶点信息
        ENode firstEdge;    // 指向第一条依附该顶点的弧
    };
    private VNode[] mVexs;  // 顶点数组
    ...
}
/*
 * 拓扑排序
 *
 * 返回值:
 *     -1 -- 失败(由于内存不足等原因导致)
 *      0 -- 成功排序,并输入结果
 *      1 -- 失败(该有向图是有环的)
 */
public int topologicalSort() {
    int index = 0;
    int num = mVexs.size();
    int[] ins;               // 入度数组
    char[] tops;             // 拓扑排序结果数组,记录每个节点的排序后的序号。
    Queue<Integer> queue;    // 辅组队列
    ins   = new int[num];
    tops  = new char[num];
    queue = new LinkedList<Integer>();
    // 统计每个顶点的入度数
    for(int i = 0; i < num; i++) {
        ENode node = mVexs.get(i).firstEdge;
        while (node != null) {
            ins[node.ivex]++;
            node = node.nextEdge;
        }
    }
    // 将所有入度为0的顶点入队列
    for(int i = 0; i < num; i ++)
        if(ins[i] == 0)
            queue.offer(i);                 // 入队列
    while (!queue.isEmpty()) {              // 队列非空
        int j = queue.poll().intValue();    // 出队列。j是顶点的序号
        tops[index++] = mVexs.get(j).data;  // 将该顶点添加到tops中,tops是排序结果
        ENode node = mVexs.get(j).firstEdge;// 获取以该顶点为起点的出边队列
        // 将与"node"关联的节点的入度减1;
        // 若减1之后,该节点的入度为0;则将该节点添加到队列中。
        while(node != null) {
            // 将节点(序号为node.ivex)的入度减1。
            ins[node.ivex]--;
            // 若节点的入度为0,则将其"入队列"
            if( ins[node.ivex] == 0)
                queue.offer(node.ivex);    // 入队列
            node = node.nextEdge;
        }
    }
    if(index != num) {
        System.out.printf("Graph has a cycle\n");
        return 1;
    }
    // 打印拓扑排序结果
    System.out.printf("== TopSort: ");
    for(int i = 0; i < num; i ++)
        System.out.printf("%c ", tops[i]);
    System.out.printf("\n");
    return 0;
}



相关文章
|
2月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
75 9
 算法系列之数据结构-二叉树
|
2月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
78 3
 算法系列之数据结构-Huffman树
|
2月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
94 22
强化学习:时间差分(TD)(SARSA算法和Q-Learning算法)(看不懂算我输专栏)——手把手教你入门强化学习(六)
本文介绍了时间差分法(TD)中的两种经典算法:SARSA和Q-Learning。二者均为无模型强化学习方法,通过与环境交互估算动作价值函数。SARSA是On-Policy算法,采用ε-greedy策略进行动作选择和评估;而Q-Learning为Off-Policy算法,评估时选取下一状态中估值最大的动作。相比动态规划和蒙特卡洛方法,TD算法结合了自举更新与样本更新的优势,实现边行动边学习。文章通过生动的例子解释了两者的差异,并提供了伪代码帮助理解。
215 2
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
119 29
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
158 25
|
6月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
617 9
|
6月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
164 58
|
4月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
263 77
|
3月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
47 11

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等