推荐|【考研】数据结构考点—

前言

本文内容源于对《数据结构（C语言版）》（第2版）和王道讲解及博主的笔记整理和总结。

可结合以下链接“食用”：

【考研】《数据结构》知识点总结.pdf_数据结构知识点总结pdf,考研数据结构知识点总结背诵-其它文档类资源-CSDN下载

一、基本概念

1、拓扑排序：可以用来判断图是否有环。（以下存储结构：邻接表）（网：带权的图）

2、有向无环图（DAG图）：一个无环的有向图。（描述一项工程或系统的进行过程的有效工具）

3、AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图。

4、拓扑排序：AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点到顶点有一条路径，则在该线性序列中的顶点必定在顶点之前。

5、对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列，反之不一定成立。

6、若一个有向图的顶点不能排在一个拓扑序列中，表示图中必有回路，该回路构成一个强连通分量，即则可判定该有向图含有顶点数目大于1的强连通分量。

7、若拓扑排序算法中为暂存入度为0的顶点，可使用栈，也可使用队列。

二、拓扑排序的过程

（1）在有向图中选一个无前驱的顶点且输出它。

（2）从图中删除该顶点和所有以它为尾的弧。

（3）重复（1）和（2），直至不存在无前驱的顶点。

（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列。

三、拓扑排序的实现

引入以下辅助的数据结构：

(1) 一维数组indegree[i]：存放各顶点入度，没有前驱的顶点就是入度为零的顶点。删除顶点及以它为尾的弧的操作，可不必真正对图的存储结构进行改变，可用弧头顶点的入度减1的办法来实现。
(2) 栈S：暂存所有入度为零的顶点，这样可以避免重复扫描数组indegree检测入度为0的顶点，提高算法的效率。
(3) 一维数组topo[i]：记录拓扑序列的顶点序号。

【算法步骤】
① 求出各顶点的人度存人数组 indegree[i] 中，并将入度为0的顶点入栈。
② 只要栈不空，则重复以下操作:
● 将栈顶顶点 V 出栈并保存在拓扑序列数组 topo 中;
● 对顶点 v_i 的每个邻接点 v_k 的入度减1，如果 v_k 的入度变为0，则将 v_k 入栈。
③ 如果输出顶点个数少于AOV-网的顶点个数，则网中存在有向环，无法进行拓扑排序，否
则拓扑排序成功。


//【算法描述】 
Status Topologica lSort (ALGraph G,int topo[] ){
// 有向图 G 采用邻接表存储结构
// 若 G 无回路，则生成 G 的一个拓扑序列 topo[] 并返回 OK， 否则 ERROR
 
    FindInDegree (G, indegree);   //求出各顶点的入度存人数组indegree中
    InitStack(S);    //栈 s 初始化为空
    for (i = 0; i < G.vexnum; ++i)
        if(!indegree[i])   
            Push(S, i);    //入度为0者进栈
    m = 0;   //对输出顶点计数，初始为0
    while (!StackEmpty(S)){  //栈 s 非空
        Pop(S, i);     //将栈顶顶点v(i)出栈
        topo[m] = i;    //将v(i)保存在拓扑序列数组 topo 中
        ++m;     //对输出顶点计数
        p = G.vertices[i].firstarc;    //p 指向 v(i) 的第一个邻接点
        while(p != NULL){
            k = p->adjvex;    // v(k) 为 v(i) 的邻接点
            --indegree[k];    // v(i) 的每个邻接点的入度减1
            if(indegree[k] == 0) Push(S, k);    //若入度减为0，则入栈
            p = p->nextarc;    //p 指向顶点 v(i) 下一个邻接结点
        }
    }
    if (m < G.vexnum)     //该有向图有回路
        return ERROR;
    else return OK;
}

【算法分析】

对有 n 个顶点和 e 条边的有向图而言，

建立求各顶点入度的时间复杂度为 O(e) ；

建立零入度顶点栈的时间复杂度为 O(n) ；

在拓扑排序过程中，若有向图无环，则每个顶点进栈，出一次栈，入度减1的操作在循环中总共执行 e 次，所以，总的时间复杂度为 O(n +e) 。

id="article_content" class="article_content clearfix"> id="content_views" class="htmledit_views">

一、Ubuntu20.04配置深度学习环境

1.首先给Ubuntu安装Chrome浏览器（搜索引擎换成百度即可）

安装命令：打开终端直接输入

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">

前言

一、基本概念

二、拓扑排序的过程

三、拓扑排序的实现

一、Ubuntu20.04配置深度学习环境

1.首先给Ubuntu安装Chrome浏览器（搜索引擎换成百度即可）

2.换成搜狗输入法（如果安装完成无法打汉字，可输入以下命令）

搜狗使用老是有问题换一个

3、ubuntu 20.04中文输入法安装

配置language support

参考：ubuntu 20.04中文输入法安装_ubuntu20.04desktop系统可输拼音-CSDN博客

安装 terminator

参考：terminator安装、美化、使用及闪退解决-CSDN博客

3.安装WPS for Linux

5. ubuntu换国内镜像源

6.安装配置anaconda

安装完成anaconda后创建一个虚拟环境

二、安装pytorch前首先安装显卡驱动

输入

设置完密码reboot就可以了

2.安装显卡驱动最简单方式：

3.这时如果弹出没有可用的附加驱动或附加驱动为空

解决方法：

三、安装配置pytorch

1.首先查看查看显卡使用情况

2.进入自己创建的虚拟环境把pytorch安装在自己的虚拟环境里面

cat /usr/local/cuda/include/cudnn.h | grep CUDNN_MAJOR -A 2 没有显示

Downloading https://ultralytics.com/assets/Arial.ttf to ...... yolov5报错解决:

3. 配置完成测试，终端打开输入：

4.用conda list查看pytorch和cuda、cudnn的版本

四、ubuntu20.04下载安装tensorrt

4.1 环境

4.2 下载tensorRT （匹配相应的版本）

4.3 添加环境

4.4 C++测试是否成功

4.5 python download_pgms.py

需要对yolov5中的权重模型.pt转换成onnx的，请点击以下链接：

yolo的模型转换权重pt文件转onnx（1）

参考文章：

Ubuntu20.04 安装tensorRT

评论记录：