当前位置： 首页 > article >正文

软考数据结构四重奏：软件工程师的线性、树、图、矩阵算法精要

article 2025/3/14 14:32:25

简介

软件设计师考试的数据结构模块涵盖**数组、链表、栈、队列、树、图等基础结构及其操作，重点考察查找（二分）、排序（快排、归并）算法，以及树/图的遍历（DFS、BFS）。要求掌握算法复杂度分析**，理解哈希、堆等结构的应用场景，强调通过合理选择数据结构优化程序性能，解决实际工程中的存储管理与计算效率问题，为系统设计奠定核心逻辑基础。

一、时间复杂度（Tn）

  1. 时间复杂度为算法中基本操作重复的次数（简称为频度），在计算时只要大致计算出相应的数量级就可以的。
    1. 例如：O(1),O(2^2)等
  2. 高阶项排序（低到高）：

  1. 计算规则：
    1. 加法规则：多项相加，保留最高项，并将系数化为1
      1. 例
      2. T(n)=2n3+n2+1
        1. 结果等于n^3
    2. 乘法规则，多项相乘都保留，并将系数化为1
      1. 例：
      2. T(n)=n3*n3
      3. T(n)=n^6
    3. 加法乘法混合规则：小括号先算再乘法后加法
      1. 例
      2. T(n)=(2+n3)*(3+n1)
      3. T(n)=n^4
  2. 例题：
结果为：log2n
public static void main(String args[]){
    int i =1;   // O(1)
    while(i<=n){   log2n +2
        i=i*2;  // log2n +1
    }
}

结果为 O（n）
public static void main(String args[]){
    int a =1;   
    for(int i = 0;i<=n;i++ ){
        a++;
    }
   
}

二、空间复杂度

  1. 看定义的空间
    1. 例：
// 空间复杂度为：O(1)

int i =1;

// 空间复杂度为：O(n)
int[] ins = nwe int[n];
  1. 注意：非递归空间复杂度一般只到
    1. O(1)
    2. O(n)
    3. O(n^2)

三、渐进符号

  1. 渐进上界（O）：大于等于复杂度
  2. 渐进下界（Ω）：小于等于复杂度
  3. 渐进紧致界（）：需要同时满足渐进上界和渐进下界

  1. 例题：

四、递归式展开式的时间、空间复杂度

  1. 公式：
    1. 递归的次数*每次递归的时间复杂度(每次递归的时间复杂度不变的情况)
  2. 例题
// 阶乘1：
时间为：O(1)*O(n)=O(n)
空间:因为没有新的变量产生，所以为O(1)

int f(int n){
    if(n==1) return 1  
    return n*f(n-1);
}

// 阶乘2
时间为：O(1)*O(log2n)=O(log2n)
空间:因为没有新的变量产生，所以为O(1)

int f(int n){
    if(n==1) return 1  
    return n*f(n/2);
}

// 阶乘3
//技巧：等差数列求和
    公式：[(1+n)*n]/2
时间为：O(1)*O(n^2)=O(n^2)
空间:因为没有新的变量产生，所以为O(1)

int f(int n){
    while(i<=n){
            // 次数为：n+(n-1)+(n-2)+.....+2+1
    }
    return n*f(n-1);

五、递归主方法

公式

题目：

解析：

六、线性结构

  1. 特点：
    1. 元素之间呈现一种线性关系
      1. 例：一个接一个排列

线性表

  1. 采用顺序存储和链式存储
  2. 主要的基本操作：插入、删除、查找
  3. 是n（n>=0）个元素的有限序列
  4. 非空线性表特点：
    1. 有第一个元素
    2. 有最后一个元素
    3. 除第一个元素外，序列中的每个元素均有一个直接前驱
    4. 除最后一个元素外，序列中的每个元素均有一个直接后继
  5. 注意：如果n为1是，元素可为第一和最后，没有前驱和后继
顺序存储
  1. 线性表中的顺序存储是指
    1. 用一组地址连续的存储单元依次存储线性表的中元素
    2. 使得逻辑上相邻的元素物理位置也相邻
  2. 优点：可以随机存取表中的元素
  3. 缺点：插入和删除都需要移动元素
  4. 插入新元素需要移动的元素个数期望值：
    1. n/2
  5. 删除元素需要移动元素的个数期望值：
    1. (n-1)/2
  6. 插入元素代码案例
    1. 时间复杂度：
      1. 最优：O(1)
      2. 最差:O(n)
      3. 平均O()
public class Test {
    public static void main(String[] args) {
        TestList  testList = new TestList();
        testList.init();
        testList.out();
        testList.insert(-1,1111);
        testList.out();
    }
}
class TestList{
    int list[];
    final static  int N=10;
    int n;
    void init(){
        list =new int[N];
        for(int i =0;i<N/2;i++){
            list[i]=i+1;
        }
        n=N/2;

    }
    void out(){
        for (int i = 0;i<n;i++) {
            System.out.print(list[i]+" ");
        }
        System.out.println("");
    }

    /**
     *
     * @param add 插入位置
     * @param num 插入数据
     */
    void insert(int add, int num){
        if (add<1 || add>n+1) return;
        for(int i =n;i>=add;i--){
            list[i]=list[n-1];
        }
        list[add-1]=num;
    }

}
  1. 删除元素代码案例
    1. 时间复杂度
      1. 最优：O(1)
      2. 最差：O（n）
      3. 平均：O（n）
 void del(int add){
        if(add<1 || add >n){
            return;

        }
        for(int i =add;i<n;i++){
            list[i-1]= list[i];
        }
        n--;
    }
  1. 查找元素代码案例
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(1)
      3. 平均：O(1)
  void getItem(int add){
        System.out.println("查询到的数据为："+list[add-1]);
    }
链式结构
  1. 通过指针链接起来的结点来存储数据元素，
  2. 结点结构：
    1. 数据域+指针域
  3. 存储的元素地址不要求连续，因此，存储元素的同时必须存储元素之间的逻辑关系。
  4. 若结点中只有一个指针域，则称为线性链表（单链表）
  5. 结点类：
public class Node {
    int num ;
    Node next;
    public Node(int num ){
        this.num = num;
    }
    public Node(){

    }


}
  1. 不带头结点的链式存储代码示例：
    1. 结点从1开始算
public class NoHeadLineList {


    Node list;
    void init(){

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        list= node1;
        node1.next = node2;
        node2.next = node3;
    }
    public static void main(String[] args) {
        // 初始化并打印
        NoHeadLineList  noHeadLineList= new NoHeadLineList();
        noHeadLineList.init();
        Node p = noHeadLineList.list;
        while(p!=null){
            System.out.println(p.num+" ");
            p=p.next;

        }

    }
}
  1. 不带头结点的链式存储代码示例：
    1. 结点从0开始
public class HeadLineList {
    Node list;
    void init(){
        list = new Node();
        Node n1= new Node(1);
        Node n2= new Node(2);
        Node n3= new Node(3);
        list.next = n1;
        n1.next= n2;
        n2.next=n3;
    }

    public static void main(String[] args) {
        HeadLineList headLineList = new HeadLineList();
        headLineList.init();
        Node p = headLineList.list.next;
        while(p !=null){
            System.out.println(p.num);
            p=p.next;
        }
    }

}
  1. 带头结点插入数据：
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)
 void insert(int add ,Node noe){
        int index = 0;
        Node p = list;
        while (index<add-1&&p!=null ){
           p = p.next;
            index++;
        }
        node.next = p.next; // 先将前一个结点的地址放入要插入的结点中
        p.next = node; // 再把地址替换成新结点

    }
  1. 不带头结点的插入数据
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)
  void insert(int add ,Node node){
        int index = 1;
        Node p = list;
        if(index==1){
            //插入第一个结点时，直接修改
            node.next=list;
            list = node;
            return;

        }
        while (index<add-1&&p!=null ){
            p = p.next;
            index++;
        }
        node.next = p.next;
        p.next = node;

    }
}
  1. 删除带头结点的数据
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)

  void del(int add){
        int index =0;
        Node p = list;
        while (index<add-1&&p!=null){
            index++;
            p=p.next;
        }
        Node s =p.next;
        p.next = s.next;

    }
  1. 删除不带头结点的数据
    1. 需要添加特殊判断
      1. 直接将List指向下一个结点就可以了
void del(int add){
        if (add==1){
            list=list.next;
            
        }
        int index =0;
        Node p = list;
        while (index<add-1&&p!=null){
            index++;
            p=p.next;
        }
        Node s =p.next;
        p.next = s.next;

    }
  1. 查询带头结点的数据
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)
Node find(int add){
    int index=1;
Node p = list.next;
    while(index<add&&p!=null){
        p=p.next;
    }
return p;
}
  1. 循环单链表
    1. 在尾节点的地址中存储首结点的地址
      1. 注意：当在尾结点插入元素时需要：
        1. 现在插入元素中存储首节点的地址，再在尾结点中存储插入元素的地址。

双链表（了解）
顺序栈

栈常用于函数的递归实现

  1. 定义：栈只能通过它的一端来实现数据存储和检索的一种线性数据结构
  2. 先进后出原则
  3. 名词解释：
    1. 栈顶：Top
    2. 栈底：Bottom
  4. 栈的基本运算

链栈
  1. 定义：用链表作用存储结构的栈
  2. 链表的头指针就是栈顶指针

例题：

解答：

顺序队列
  1. 定义：
    1. 队列是先进先出的线性表。
    2. 它只允许在表的一端插入元素（队尾插入），在表的另一端删除元素（队头删除）。
  2. 顺序队列由于队列中的删除和插入在两端进行，所以需要设置队头指针和队尾指针
  3. 队列的基本运算
// 初始化队列
    int[] alist = new int[n];
    int before=0;//队头
    int after =0;//队尾
// 判断空
    before ==after // true为空，
// 入队
    alist[after]=x;
    after++;
//出队
    before++;
//读队头元素
    alist[before]
循环队列
  1. 优点：
    1. 出队和入队都不需要移动队列中的其他元素
  2. 假设队列中有6个元素，队尾值已经为5个，还想要插入数据时，并且不产生越界（删除数据也是类似方法）：
    1. 修改公式：（队尾+1）/6

  1. 例题：
    1. 技巧：代入法或
    2. 从公式内移动队头结点
    3. +M防止下溢出（负）
    4. %M防止上一出（正）

链式队列
  1. 链式队列具有首节点和尾结点，
  2. 链式队列在插入和删除元素时，不需要遍历整个队列链表

栈和队列混合题目
  1. 两个栈可以模拟出一个队列
  2. 入队序列和出队序列关系为1：1
    1. 例如：入队为abc,出队为abc
  3. 入栈序列和出栈序列关系为：1:n(n>=1)
    1. 例如：出栈和出栈的排序方式可以有多种
  4. 例题：

串
  1. 定义：是仅由字符构成的有限序列，是一种线性表。
  2. 形式：
    1. String str=“abcd”；
  3. 扩展知识：
    1. ASCII：
      1. 0为48
      2. A为65
      3. a为97
  4. 基本概念

  1. 字符串的子串需要是连续的
    1. 例 字符串"abc",则子串只有：
      1. a
      2. b
      3. c
      4. ab
      5. bc
串的匹配模式_朴素模式匹配
  1. 时间复杂度：
    1. 最好：O(m) 次数：m次
    2. 最坏:O(m*n) 次数：（n-m+1）*n
    3. 平均：O(m+n) 次数：1/2 *(n+m)

串_Next数组值
  1. 串的前缀：包含第一个字符且不包含最后一个字符的子串
    1. 例：字符串为：abc
      1. 前缀可为：a;b;ab
  2. 串的后缀：包含最后一个字符且不包含最后一个字符的子串
    1. 例如：字符串：abc
      1. 后缀有：b;c;bc
  3. 记：第i个元素的next值等于：
    1. 从1~i-1串中最长相等前后缀长度+1
    2. 例题：字符串中：abcd求d的next值：
      1. 过程：当长度为1时，前缀为a,后缀为：c，不相等
      2. 长度为2时：前缀为：ab,后缀为：bc，不相等
      3. 长度1和长度2都为0，所以0+1=1
      4. d的next值为：1
  4. 记住：next[1]=0;next[2]=1
KMP算法（了解）

一维数组和二维数组地址计算

注意：当在二维数组中i和j相同时，按行存储和按列存储都是一样的。

arr[a][b]:a为行，b为列

  • 题目1：
    • 技巧1：直接背公式
    • 技巧2：可以举简单的二维数组推出结果
  • 题目2：
    • 结论：二维数组在j和i都相同时，不关是按列存储还是按行存储，存储的位置同时相同的（偏移量相同）。

七、矩阵

对称矩阵

对称矩阵：

三个区域 ：

i=j >>>>主对称线

i>j>>>>>下三角区

i>>>>上三角区

  1. 考点：将对称矩阵数据压缩，并用按行优先存储。
  2. 需要存储个数公式：((1+n)*n)/2
    1. 例：存存储一个a[3][3]数组
      1. 解：(1+3)3/2=43/2=6
  3. 对称矩阵转换为一维数组存储位置公式(下标为0的情况)：
    1. 当i>=j时：a(i,j)=i(i+1)/2+j+1
    2. 当i<=j时，a(i,j)=j(j+1)/2+i+1
  4. 对称矩阵转换为一维数组存储位置公式(下标为1的情况)：
    1. 当i>=j时：a(i,j)=i(i-1)/2+j
    2. 当i<=j时，a(i,j)=j(j-1)/2+i
  5. 注意点：做题是看要求的是上三角还是下上三角

  1. 例题:
    1. 技巧：如果做到此题忘记了公式的话，可以采用代入法：
      1. 结果：A

对三角矩阵

  1. 位置推导（下标为0）：

    1. 假设A[3,3]在一位数组中存储位置为：10
      1. 10的由来分为两步：
      2. 第一步：求出3[3,3]之前的元素个数：公式为：i*3-1(减一是因为第一行只有两个元素)
      3. 第二步：求第几个，看j和i，通过j-i可以得到距离为（-1,0,1），所以把每个数+2，则可得到第几个公式：j-i+2
      4. 两步合并：i*3-1+j-i+2
      5. 化简：2i+j+1>>>>>>2*3+3+1=10

  2. 公式

稀疏矩阵

  1. 记：稀疏矩阵的三元组表的顺序存储结构称为：三元组顺序表，常用的三元组表的链式存储结构是十字链表。
  2. **记：****三元顺序表和十字链表**是对稀疏矩阵进行压缩存储的方式。
  3. **三元组顺序表（图右边）**存储稀疏矩阵

  1. **十字链表（图右边）**存储稀疏矩阵

八、树

定义

  1. 树结构是非线性结构
  2. 该结构中的一个元素可以有两个或两个以上的直接后续元素（一对多）
  3. 数是n（n>=0）个结点的有限集合，当n为0时，称为空树。
  4. 在任一非空树中，有且仅有一个称为根结点。
  5. 树的定义是递归的，它表明了树本身的固有特性，也就是一棵树有若干颗子树构成，而子树又由更小的子树构成。

树的性质1

  1. 树中的结点总数=树中所有结点的度数之和+1（加1表示加上根结点）

  1. 例题：
    1. 树中的结点总数为：

树的性质2

  1. 度为m的树中第i层上最多有m^(i-1)个结点（i>=1）
  2. 例：
    1. 根结点：1个
    2. 第二层：3个
    3. 第三层：9个

树的性质3

  1. 高度为h的m次树最多有（m^h-1）/(m-1)个结点
    1. 公式是通过等比数列推导出来的
  2. 例题：
    1. h为3，m为3，求结点：
    2. 解：(3^3-1)/3-1=26/2=13

树的性质4

  1. 知道n个结点和为m的数，求树的高度h
  2. 对性质3的公式变形

$ n=m^h-1/m-1 $

变形：

n(m-1)=m^h-1

n(m-1)+1=m^h

h=logm (n(m-1)+1)

注意：当求出h出现小数点后，需要进行向上取整。

例题

1. 解释：
    1. 叶子结点（终端结点）：指数为0的节点，它之下没有节点
    2.

二叉树

  1. 定义：
    1. 是n（i大于等于0）个节点的有限集合
    2. n为0时，是一个空树
    3. 当n≠0时，一个根节点及两颗不同相交的且分别称为左右子树的二叉树组成
    4. 二叉树具有递归性质
  2. 树和二叉树的区别
    1. 二叉树严格区分结点是左子树还是右子树
    2. 树不区分，称为子树即可。
    3. 二叉树中，结点的最大度为2
    4. 树不限制结点的度数

画板

  1. 二叉树的性质：
    1. 第i层（i≥）上最多有2^(i-1)个结点
      1. 例 第二层：2^(2-1)=2
    2. 高度为h的二叉树共有结点：2^h-1
      1. 共2层的二叉树：2*2-1=3
    3. 对于任一二叉树，度数为0的结点树=度为2的结点树+1（n0=n2+1）
      1. 共2层的二叉树：n0=1+1=2

满足二叉树

  1. 高度为k的二叉树有2^k-1个结点

例题：

求满二叉树7个结点，求高度：

Log2 (7+1)=3

完全二叉树

  1. 高度为h，除了h层的，其余结点都是满的，且结点从左到右依次存储，不能留空。

例题：

求完全二叉树6个结点，求高度：

解：（log2 6 ）+1=2+1=3

单支树

除了叶子结点，其余结点度为1

二叉树的存储结构

顺序存储
  1. 使用数组存储
  2. 定义：顺序存储是有一组地址连续的存储存二叉树的结点
  3. 假设编号为i
    1. i=1，为根结点
    2. 2i≤n ：i为左编号，关系式不成立时，没有左孩子
    3. 2i+1小于等于n：i为右结点，关系式不成立时，没有右孩子
  4. 完全二叉树采用顺序存储结构高效且节约空间。
  5. 一般的二叉树，不宜使用顺序结构。
  6. 最坏情况下，高度为k且只有k个节点的二叉树（单支树）需要(2^k)-1个存储单元。
    1. 例：

画板

存储单位为：(2^2)-1=3

记

题1：

求3个结点的二叉树有多少个形态====》5

求4个结点的二叉树有多少个形态====》14

**求5个结点的二叉树有多少个形态====》42 **

题2

链式存储
  1. 结点中包含了有数据雅元素、左子树的根、右子树的更，及双重信息。
  2. 考点1
    1. 一个双链表中，有多少个空指针域。
      1. 解：二叉树中有n个结点，有（n-1）个分支，分支就是有效指针域，一个结点有2个指针
        1. 公式：2n-(n-1)=n+1
  3. 考点2
    1. 一个三链表中，有多少个空指针域。
      1. 公式：n+2

二叉树的遍历算法

先序遍历

根左右

中序遍历

左根右

后序遍历

左右根

层次遍历

从第1层，先上后先，先左后右

根据遍历构造二叉树

  1. 步骤：先有中序，中序+其他可以找出根结点，从而推出整个二叉树
  2. 组合有：
    1. 中+先
    2. 中+后
    3. 中+层
  3. 注意点：其他两个序列推不出中序

平衡二叉树

  1. 定义：二叉树的任意一个结点的左右子树高度只差的绝对值不超过1
  2. 满二叉树包含完全二叉树，完全二叉树包含平衡树

二叉排序树（二叉查找树）

  1. 特点（根据结点的关键字）：
    1. 大于左子树所有结点的关键字
    2. 小于右子树所有结点的关键字
    3. 左右子树也是一颗二叉排序树
  2. 中序遍历得到的序列也是有序序列
  3. 例：

  1. 二叉排序树的构造

  1. 二叉排序树，进行查找时，效率最差的单支树
  2. 二叉排序树，从左到右排序，同层次的结点，其关键字呈现有序排序特点
    1. 例：

最优二叉树（哈夫曼树）

  1. 定义：它是一类带权路径长队最短的树
  2. 最优二叉树,只有N0和N2，
  3. 总结点数为：2n-1
  4. 树的带权路径长度=树中所有叶子结点的带权路径长度之和
    1. 公式：

2. n为带权结点树目，Wr为叶子节点的权值，Lr为叶子结点到根的路径长度

例：

最优二叉树的构造方法

  1. 大概步骤：
    1. 根据题目给的n个权值 如：{1,2,3,4,}
    2. 转成n颗二叉树的集合(其中的每个元素都是一颗树) F={1,2,3,4,}
    3. 选中最小的两个作为左、右子树，构造出一颗新的树

4. 删除F中使用的二叉树并新增数F={4,3,4}
5. 重复c,d步骤，当F中只剩下一颗树，就是最优了

  1. 注意：在构造左右子树并没有明确规定位置，但是WPL是唯一的。

软考构造最优二叉树的注意事项☆☆☆☆☆☆☆

案例一：

案例二：

等长编码

每个字符编制相同的长度的二进制编码

考点一例题：

告诉英文字符为26个字符，求需要多少个二进制表示？

解：2^n>=26

n=5

哈夫曼编码

考点一：给一串字符并相应权重，求出最优二叉树，在通过标0/1，求出每个字符的编码

例：

哈夫曼编码压缩比：

求一串字符，通过等长编码和哈夫曼编码分别求出需要空间，并算出使用哈夫曼编码可以节省多少空间。

例：

线索二叉树（了解）

特点：在结点存储的信息中作一些改变

二叉树的关系引入

满二叉树包含完全二叉树

完全二叉树包含平衡二叉树

平衡二叉树

排序二叉树

最优二叉树

线索二叉树

二叉树考点知识

  1. 用n个权值构造一颗最优二叉树，该树的结点为：2n-1
  2. 霍夫曼编码是基于贪心策略
  3. 哈夫曼树中的结点一定为奇数
  4. 任意一颗二叉树都是一颗线索二叉树

十、图

  1. 定义：
    1. 图G是集合V和E构成的二元组，记 ：G=（V,E）
    2. V是图中顶点的非空有限集合，E是图中边的有限集合
    3. 图中，元素用顶点表示，元素之间的关系用边表示

有向图

每条边都是有方向的

用<v1,v1>表示，v1表示弧尾，v2表示弧头

注意：

无向图

每条边都是没有方向的

用（v1,v1）表示

注意：

完全图

无 向完全图
  1. 若有N个顶点
    1. 每个顶点和其他n-1个顶点都有边
    2. 有(n(n-1))/2条边

有向完全图
  1. 有n个顶点：
    1. 需要n（n-1）条边，

例：

顶点的度

  1. 无向图：顶点的度指关联该顶点的边的树目
  2. 有向图：分为出度（指向其他顶点）和入度（其他顶点指向自己）
  3. 有向图的每一个顶点的总度数为：出度+入度
  4. 重点：有向完全图和无向完全图的度数都是2e(e为边数)
    1. 边数e=总度数/2

图的路径

  1. 路径的长度为：弧的树目
  2. 例题:

  1. 起点和终点相同称为回路或环

连通图

  1. 定义：无向图中任意两个顶点都是连通的。
  2. 边数
    1. 最少：n-1
    2. 最多：n(n-1)/2
  3. 例题：

强连通图

  1. 定义：在有向图中，从Vi到Vj和从Vj到Vi都是有路径的
  2. 边数：
    1. 最少：n
    2. 最多：n（n-1）

图的存储结构

两种表示法：

邻接矩阵

邻接表

邻接矩阵
  1. 无向表
    1. 的邻接矩阵都是对称的。
    2. 看某个顶点Vi的度，直接看对应行的非0个数
    3. 2e=非0个数
  2. 有向表：
    1. 出度看行的1个数
    2. 入度看列的1个数
    3. 总度=出度+入度
    4. 边数e=非0个数

邻接表
  1. 定义：指的是为图的每个顶点建立一个单链表，

稠密图和稀疏图

  1. 稠密图：边尽可能的多，顶点与顶点间都有两条边，
  2. 稠密图存储邻接矩阵
    1. 例：完全图
  3. 稀疏图：边少
  4. 稀疏图存邻接表

考点记录

有向图在邻接矩阵非0个数为：e

无向图在邻接矩阵的非0个数为2e

扩展—网

  1. 定义：网是在图的基础上，在图的每条边都增加了一个权值
  2. 网在邻接矩阵中把0替换成了∞

图的遍历

  1. 定义：指从某顶点出发，沿着某条搜索路径对图中所有顶点进行访问且指访问依次的过程。
  2. 为了避免对顶点重复访问，在图的遍历过程中必须记下每个访问过的顶点。

深度优先搜索(DFS)

  1. 实现思想：递归
  2. 遍历特点：第一次沿着一条路走到底，没有路时在回溯当上顶点走其他分支
  3. 遍历过程

  1. 时间复杂度
    1. 使用邻接矩阵表示：T平均=O(n^2)
    2. 使用邻接表表示：T平均=O(e+n)

广度优先搜索（BFS）

  1. 实现思想：队列
  2. 特点：先访问完一个顶点的所有邻接点，后再访问其他
  3. 遍历步骤：

  1. 时间复杂度
    1. 使用邻接矩阵表示：T平均=O(n^2)
    2. 使用邻接表表示：T平均=O(e+n)

拓扑排序

  1. AOV网是一个有向无环图
  2. 排序步骤：
    1. 选择入库为0的顶点并输出
    2. 删除该顶点及顶点的所有边
    3. 重复以上步骤，知道图中不存在入度为0的顶点

例：

考题一：

考题二：


http://www.kler.cn/a/584244.html

相关文章：

  • 本地部署DeepSeek-R1模型详细流程
  • 【数据结构】2算法及分析
  • Oracle 查询数据库对象的DDL语句
  • HarmonyOS Next 全栈开发深度解析：从架构设计到分布式应用实战
  • 面试之《什么是流式渲染》
  • 微店平台商品关键字搜索接口调用指南：Python代码实现与实战解析
  • Qemu 详解与 ARM 虚拟机搭建指南
  • Vue3计算属性深度解析：经典场景与Vue2对比
  • Python 进程与线程-分布式进程
  • 工作记录 2017-01-09
  • React Next项目中导入Echart世界航线图 并配置中文
  • Flink 中RocksDB 为什么将每个键和值的限制为 2^31 字节
  • SpringCloud带你走进微服务的世界
  • 零信任架构实战手册-企业安全升级
  • 使用 Excel 实现绩效看板的自动化
  • 2024 年第四届高校大数据挑战赛-赛题 A：岩石的自动鉴定
  • css基本功
  • 手写svm primal form形式
  • kafka连问
  • 华为重拳出击！华为重拳出击！华为重拳出击！