《老匠新传》

背景剧情：

在安徽省一个偏远小山村里，住着一位年迈的老匠人程老。他是村里最后一位木雕匠，祖传的技艺如今面临失传的窘境。一天，城市的女孩小林，来到了这个小山村。她被精致的雕刻作品和老人的精湛技艺所吸引，留下来悉心学习这传统技艺。

多年后，女孩学成回到城市。她呼吸着浮躁的空气，下定决心在城市的一隅开设了一家雕刻工作室。门口摆放着一只木雕鸟，和曾经吸引她踏入木雕门扉的那只一般，精致而美丽。但是简约的线条又让它显得轻盈而现代。

“那是一块文化的拼图，串起了过去岁月的技艺，和当代创新的潮流。”

创作理念：

我们的故事从安徽省一个偏远小山村的年迈木雕匠人程老为起点，通过他与来自城市的女孩小林之间的师徒传承，展现传统技艺在现代社会中的困境与重生。

文化传承：我们希望强调了传统技艺的文化价值，如木雕这一几代人相传的技艺，不仅是技艺本身，更是一种文化的延续。程老作为村里最后一位木雕匠，他的技艺和作品承载着丰富的历史和文化信息。

师徒传承：通过小林对程老技艺的学习和传承，我们希望展现师徒之间深厚的情感纽带和技艺的传递。这种传承不仅是对技艺的保存，更是对文化精神的延续。

创新融合：小林学成后，在城市开设雕刻工作室，将传统技艺与现代审美相结合，创作出既具有传统韵味又符合现代审美的作品。其中表达着对传统文化的创新和发展，以及传统技艺在现代社会中焕发出新的生命力。

文化自信：故事中的小林在回到城市后，能够自信地展示和推销自己的作品，体现了对传统文化的自信和自豪感。

艺术表达：

我们采用现代的技术载体讲述传统技艺的传承和新生，希望增添作品的现实意义。

细节描写：故事中对木雕作品的细节描写，如“精致的雕刻作品”和“一只木雕鸟”，不仅展现了程老技艺的精湛，也通过小林对这些作品的喜爱和学习，传递了她对传统文化的热爱和尊重。

情感渲染：通过小林与程老之间的互动，以及小林学成后回到城市的心理变化，渲染师徒之间的深厚情感和传统文化的厚重感。

象征手法：木雕鸟作为故事中的象征物，既代表了程老的技艺传承，也象征着传统技艺在现代社会中的重生和创新。它的“精致而美丽”和“简约的线条”既体现了传统技艺的精髓，又融入了现代审美元素。

语言风格：故事中的语言风格简洁明了，富有诗意。

使用技术：

图像生成：首先训练GPT-4成为Midjourney提示词生成器。然后通过文字描述剧本中的场景，获取提示词。最后使用Midjourney生成场景图片，进行筛选。

视频生成：我们利用可灵AI进行视频的制作，我们使用生成的图片生成初版视频，然后通过提示词进行多次约束，修改，最后剪辑合并。

图的基本概念和术语

定义：一个图可以利用两个集合进行定义。第一个集合是点的集合,这些点在图术语中一般被称(Vertex);第二个集合是连接两个顶点的边(Edge)的集合。图的具体定义如下。 图是由顶点集合及顶点间的关系集合组成的一种数据结构:Graph = (V, E)

基本术语

1. 有向图

2. 无向图

3. 邻接点

4. 顶点的度，入度与出度

5. 权和网：

   • 权 ： 某些图的每条边都可能赋予一个数值，这个数值称为权。
   • 网 ： 带有权的图称为网。

6. 无向完全图： 任意两个顶点之间都有一条边的无向图。

   有向完全图： 任意两个顶点之间都有方向相反的两条边的有向图。

7. 路径与路径长度

8. 简单路径：若路径上经过的各顶点均不重复，则称这样的路径为简单路径。

   回路或环：若路径上的第一个顶点与最后一个顶点相同，则称这样的路径为回路或环。

9. 连通图： 在无向图中，若任意两个顶点之间都存在路径，则称该图为连通图。

   连通分量： 非连通图的极大连通子图称为连通分量。也就是说，一个连通分量是一个连通的子图，且不能再扩大。

10. 强连通图： 在有向图中，若对于任意一对顶点 u 和 v，都存在一条从 u 到 v 和从 v 到 u 的路径，则称该图为强连通图。

    强连通分量： 非强连通图的极大强连通子图称为强连通分量。

11. 生成树： 一个连通图的生成树是包含图中所有顶点的极小连通子图。也就是说，生成树是一棵树，且包含图中的所有顶点。

    生成森林： 非连通图的每个连通分量分别可以得到一棵生成树，这些生成树的集合称为生成森林。

图的储存结构

邻接矩阵

邻接矩阵表示法的基本思想是引入两个数组：

• 一个用于记录图中各个顶点信息的—维数组，称为顶点表；
• 另一个用于表示图中各个顶点之间关系的二维数组，称为邻接矩阵。

设图G=(V, E)是具有n(n>0)个顶点的图，则图G所对应的邻接矩阵A是一个n阶方阵

无向图的邻接矩阵可采用只存储上三角阵或下三角阵的压缩存储方法

对于带权图，需要对邻接矩阵的元素值定义进行修改，让元素值表示相应顶点的权值

其中，∞可用计算机中的一个足够大的数代替，以与权重区分

算法

图类MGraph的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 图的类型定义: 无向图、无向网、有向图、有向网
enum GraphType { undigraph, digraph, undinetwork, dinetwork };

template <class T>
struct EdgeType { // 本类型定义也适用于后面的邻接表结构
    T head, tail;
    int cost;
    EdgeType(T h, T t, int c) {
        head = h;
        tail = t;
        cost = c;
    }
};

template <class T>
class MGraph {
private:
    int vexnum, edgenum;
    GraphType kind;
    vector<vector<int>> edges; // 邻接矩阵
    vector<T> vexs;            // 顶点表
};

无向有权图的邻接矩阵构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void createAdjMatrix(vector<vector<int>>& adjMatrix, const vector<tuple<int, int, int>>& edges, int numVertices) {
    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (i != j) adjMatrix[i][j] = INT_MAX; // 没有边的地方设置为无穷大，当i=j的值为0
        }
    }

    // 填充边的信息
    for (const auto& edge : edges) {
        int u = get<0>(edge);  // 获取第一个元素
        int v = get<1>(edge);  // 获取第二个元素
        int weight = get<2>(edge);  // 获取第三个元素
        adjMatrix[u][v] = weight;
        adjMatrix[v][u] = weight;  // 无向图
    }
}

邻接表

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。

算法

基于邻接表存储表示的图类ALGraph定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 边节点
struct EdgeNode {
    int adjvex;  // 邻接点下标
    EdgeNode* next; // 指向下一个邻接点
};

// 顶点节点
template <class T>
struct VexNode {
    T data;
    EdgeNode* firstEdge;
};

// 图的邻接表表示
template <class T>
class ALGraph {
    vector<VexNode<T>> vex;  // 顶点数组
    int vexnum, edgenum;  // 顶点数和边数
	GraphType kind;
};

无向图的构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

template <class T>
ALGraph<T>::ALGraph(GraphType t, T vexs[], int n, int e) {
    // 参数表示图的类型, 参数vexs为存储各顶点值的数组, 参数n和e分别为顶点数和边数
    vexnum = n;
    edgenum = e;
    kind = t;
    adjlist.resize(vexnum);

    // 初始化顶点表
    for (int i = 0; i < vexnum; ++i) {
        adjlist[i].data = vexs[i];
        adjlist[i].firstEdge = 0;
    }

    // 依次输入所有的边的信息
    for (int j = 0; j < edgenum; j++) {
        int va, vb;
        cin >> va >> vb;

        // 产生第一个表结点
        EdgeNode* p = new EdgeNode;
        p->adjvex = vb;
        p->nextedge = adjlist[va].firstEdge;
        adjlist[va].firstEdge = p;

        // 产生第二个表结点
        p = new EdgeNode;
        p->adjvex = va;
        p->nextedge = adjlist[vb].firstEdge;
        adjlist[vb].firstEdge = p;
    }
}

图的遍历

为了防止已经访问过的结点重复访问的问题，提出了辅助数组 visited[]

深度优先遍历

深度优先搜索类似于树的先序遍历。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//访问顶点
	visited[v] = TRUE;	//设已访问标记
	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
	int v; 
	for(v=0; v<G.vexnum; ++v){
		visited[v] = FALSE;	//初始化已访问标记数据
	}
	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
		if(!visited[v]){
			DFS(G, v);
		}
	}
}

DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为O(V)。

对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(V^2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(V＋E)。

广度优先遍历

图的广度优先遍历就类似于树的层序遍历

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for(i = 0; i<G,numVertexes; i++){
		visited[i] = FALSE;
	}
	InitQueue(&Q);	//初始化一辅助用的队列
	for(i=0; i<G.numVertexes; i++){
		//若是未访问过就处理
		if(!visited[i]){
			vivited[i] = TRUE;	//设置当前访问过
			visit(i);	//访问顶点
			EnQueue(&Q, i);	//将此顶点入队列
			//若当前队列不为空
			while(!QueueEmpty(Q)){
				DeQueue(&Q, &i);	//顶点i出队列
				//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
				//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
					//检验i的所有邻接点
					if(!visited[j]){
						visit(j);	//访问顶点j
						visited[j] = TRUE;	//访问标记
						EnQueue(Q, j);	//顶点j入队列
					}
				}
			}
		}
	}
}

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q, n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(V)。 采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，在搜索任一顶点的邻接点时，每条边至少访问一次，算法总的时间复杂度为O(V＋E)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(V)，故算法总的时间复杂度为O(V^2)。

注意:图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

应用

简单路径的搜索算法 dfs

二部图的判定算法

最小生成树

生成树变成非连通图;若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图G=(V,E)，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树)，称为G的最小生成树(Minimum-Spanning-Tree,MST)。

普里姆（Prim）算法

从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。

引入辅助数组miniedges[]，用于存放每个节点到节点v的边的权值，并每次挑选出权值最小的那个边所对应的节点加入生成树，辅助数组miniedges[]的数据类型如下

1
2
3
4

struct Edge {
    int adjvex;  // 与当前生成树连接的节点的编号
    int lowcost; // 到当前生成树的最小边权值
};

若将某个数组元素miniedges[i]的 lowcost成员值设为0，则表示相应的顶点v,已加入到最小生成树中。

为便于算法在执行过程中读取任意两个顶点之间边的权值，对图宜采用邻接矩阵存储结构。

算法思路：

1. 初始化辅助数组，从节点v开始，将v的lowcost设为0，说明已经加入生成树

2. 循环vexnum-1次，利用函数MiniNum找到权值最小的节点并输出

   函数MiniNum循环vexnum次，找到当前所有节点中，未加入生成树的，lowcost最小的节点

3. 更新辅助数组miniedges[]的每个节点的lowcost：循环vexnum次，如果通过当前节点k能找到比原先更小的边，更新该节点的lowcost；如果大，则保留原lowcost的值，更新后代表生成树节点的集合到未加入节点的集合的权值最小的vexnum条边

时间复杂度：O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

void Prim(const vector<vector<int>>& graph, int v, int vexnum) {
    // 初始化 miniedges 数组
    Edge* miniedges = new Edge[vexnum];
    
    // 初始化 miniedges，每个节点到起始点v的边的权值
    for (int i = 0; i < vexnum; i++) {
        miniedges[i].adjvex = GetVexValue(v);        // 初始时节点的连接为起始节点v
        miniedges[i].lowcost = GetEdgeValue(graph, v, i);   // 初始化每个节点到v的边权值
    }

    miniedges[v].lowcost = 0; // 将起始节点v的lowcost设为0，表示已经加入生成树

    // 循环执行，每次选取一个未加入生成树的权值最小的节点
    for (int i = 1; i < vexnum; i++) {
        // 找到最小的lowcost
        int k = MiniNum(miniedges, vexnum);
        
        // 输出当前加入生成树的边
        cout << miniedges[k].adjvex << " --> " << GetVexValue(k) << endl;
        
        // 将选中的节点k加入生成树
        miniedges[k].lowcost = 0; // 表示节点k已加入生成树

        // 更新与当前生成树连接的节点的lowcost（最小边权值）
        for (int j = 0; j < vexnum; j++) {
            // 如果通过当前节点k能找到比原先更小的边，更新该节点的lowcost
            if (GetEdgeValue(graph, k, j) < miniedges[j].lowcost) {
                miniedges[j].adjvex = GetVexValue(k);   // 记录当前节点k
                miniedges[j].lowcost = GetEdgeValue(graph, k, j); // 更新到生成树的最小边权值
            }
        }
    }

    // 释放动态分配的内存
    delete[] miniedges;
}

函数MiniNum用于在数组miniedges中查找集合V-U中的具有最小权值的顶点,可以将它定义为私有成员函数

1
2
3
4
5
6
7
8
9
10
11
12

// 找到当前所有节点中，未加入生成树的，lowcost最小的节点
int MiniNum(Edge miniedges[], int vexnum) {
    int min = INT_MAX;
    int k = -1;
    for (int i = 0; i < vexnum; i++) {
        if (miniedges[i].lowcost != 0 && miniedges[i].lowcost < min) { // 如果该节点未加入生成树
            min = miniedges[i].lowcost;
            k = i;
        }
    }
    return k; // 返回最小权值的节点
}

克鲁斯卡尔（Kruskal）算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

每次挑选为加入生成树的最小边，若不构成回路，则加入生成树，若构成则挑选下一个

为提高算法执行过程中查找最小权值边的速度，可以采用一种排序算法(如堆排序算法)对边集数组中的边按权值进行排序。

接下来，Kruskal算法的关键问题就是如何判断所选取的边加入T中是否会产生回路，这里通过引入称为并查集的数据结构来解决

在下面描述的Kruskal 算法实现中，首先利用私有成员 GetGraph()函数将图的边按权值排好序后存入边集数组graph中，而边集数组tree则用于保存和返回算法所构造的最小生成树T。

算法思路：

1. 初始话数组graph，用于存放所有的边，并对其排序
2. 并查集的使用利用数组components，先进行初始化，每个节点的祖先都是自己，也可以理解成每个节点都构成一个集合，后续并查集的过程即为集合合并的过程
3. 循环直到找到最小生成树的所有边（vexnum - 1条），对于每条边，查找他的起点和终点节点的祖先，若是一个祖先则说明在同一集合，不能加入到生成树；若不是一个，则可以加入到生成树数组tree，并要修改节点的祖先，使他们集合合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

template <class T>
void MGraph<T>::Kruskal(vector<EdgeType> &tree) {
    // 创建一个图的边集合，用于存放所有的边
    vector<EdgeType> graph;
    // GetGraph函数将图的所有边按权值从小到大存放到graph数组中
    GetGraph(graph);

    // 初始化最小生成树数组，并且初始化并查集组件
    tree.resize(vexnum - 1);  // 最小生成树包含的边数量是vexnum - 1
    int *components = new int[vexnum];  // 记录每个节点所属的集合
    // 初始时，每个节点都属于自己的集合
    for (int i = 0; i < vexnum; i++) {
        components[i] = i;
    }

    int k = 0, j = 0;
    // 循环直到找到最小生成树的所有边（vexnum - 1条）
    while (k < vexnum - 1) {
        // 从排序好的边中选择一条边
        int h1 = graph[j].head;  // 边的起点
        int t1 = graph[j].tail;  // 边的终点
        int h2 = components[h1];  // 获取起点所在的集合
        int t2 = components[t1];  // 获取终点所在的集合

        // 如果起点和终点属于不同的集合，则这条边可以加入最小生成树
        if (h2 != t2) {
            // 将这条边加入最小生成树中
            tree[k].head = h1;
            tree[k].tail = t1;
            tree[k].cost = graph[j].cost;  // 边的权值
            k++;  // 记录已选择的边的数量

            // 合并两个集合，统一编号
            // 将所有属于终点集合t2的顶点，集合编号更新为起点集合h2的编号
            for (int i = 0; i < vexnum; i++) {
                if (components[i] == t2) {
                    components[i] = h2;  // 更新组件编号
                }
            }
        }
        j++;  // 继续检查下一条边
    }

    // 释放动态分配的内存
    delete[] components;
}

显然，Kruskal算法的效率与所选择的排序算法的效率以及并查集数据结构的实现效率有关。若采用第10章介绍的比较高效的堆排序算法排序，并查集采用树结构实现，则Kruskal算法的时间复杂度可达到O( elog₂e)。相比 Prim 算法而言，Kruskal算法更适用于求解稀疏网(指边数较少的网)的最小生成树。

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

求图的最短路径问题通常可分为两类。一类是求图中某顶点到其余各顶点的最短路径问题，也称为单源最短路径问题;另一类是求图中每对顶点之间的最短路径问题。

迪杰斯特拉( Dijkstra )算法

Dijkstra算法用于构建单源点的最短路径—，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值。

通俗点说，迪杰斯特拉(Dijkstra)算法，它并不是一下子求出了 v_i到 v_j的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

下面介绍 Dijkstra算法的具体实现。为便于在算法执行过程中快速地求得任意两个顶点之间边的权值，图的存储结构宜采用邻接矩阵方式。

为标识图中各顶点在算法执行过程中是否已求出最短路径，设置一个一维数组s[]

为记录 Dijkstra算法所求出的从源点到各顶点的最短路径，引入数组 path[], path[i]中保存了从源点到终点v,的最短路径上该顶点的前驱顶点的序号。算法结束时，可根据数组path[ ]找到源点到v,的最短路径上每个顶点的前驱顶点，并一直回溯至源点，从而推出从源点到v的最短路径。

为便于每次从V-S中选择当前离源点距离最短的顶点，需要引人一个辅助数组dist[]。它的每一个分量dist[i]表示当前所确定的从源点 v₀,到终点 v_i的最短路径.

算法思路：

1. 初始化，s[]所有值为0，s[0]设置为1，代表从 v₀节点开始，path[]所有值设为0，path[0]设为-1，dist[]通过查找邻接矩阵，得到 v₀到各个顶点的值
2. 查找dist中最小的值，从该节点继续完成最小路径，将该节点对应s[]设为1
3. 遍历尚未找到最短路径的节点，即s[]为0，dist[i] = Min{dist[i]，dist[j] +cost(j,i)}，选择是借用上一个最短路径的节点到达还是直接到达，更新dist的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// Dijkstra算法：计算从起点start到其他所有节点的最短路径
void dijkstra(int start, int dist[], int path[]) {
    int n = numVertices;  // 获取图中节点的数量
    bool visited[n];  // 访问标记数组，用于标记节点是否已经被访问

    // 初始化dist数组和path数组
    // dist[i] 表示从起点到节点i的最短距离
    // path[i] 表示从起点到节点i的最短路径的前驱节点
    for (int i = 0; i < n; ++i) {
        visited[i] = false;  // 初始时，所有节点均未被访问
        dist[i] = adjMatrix[start][i];  // dist数组初始化为起点到各节点的初始距离
        if (dist[i] != INT_MAX || i == start) {  // 如果有边（距离不为无穷大），或者是起点本身
            path[i] = start;  // 将路径的前驱节点设置为起点
        } else {
            path[i] = -1;  // 如果节点无法从起点到达，前驱节点为-1
        }
    }

    dist[start] = 0;  // 起点到起点的距离为0
    visited[start] = true;  // 标记起点为已访问

    // 进行n-1轮循环，逐步更新最短路径
    for (int count = 0; count < n - 1; ++count) {
        int min = INT_MAX, min_index;

        // 找到未访问的节点中距离最小的节点
        for (int v = 0; v < n; ++v) {
            // 选择距离最小且未被访问的节点
            if (visited[v] == false && dist[v] <= min) {
                min = dist[v];  // 更新最小距离
                min_index = v;  // 记录最小距离节点的索引
            }
        }

        visited[min_index] = true;  // 标记该节点为已访问

        // 更新与该最小距离节点相邻的节点的距离
        for (int v = 0; v < n; ++v) {
            // 如果v节点未被访问，并且从min_index到v有边，且经过min_index节点的路径更短
            if (!visited[v] &&  
                dist[v] > dist[min_index] + adjMatrix[min_index][v]) {
                dist[v] = dist[min_index] + adjMatrix[min_index][v];  // 更新v的最短距离
                path[v] = min_index;  // 更新v的前驱节点
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 打印从源节点到目标节点v的路径
void PrintPath(const vector<vector<int>>& g, vector<int> path, vector<int> dist, int v) {
    if (dist[v] == INF) {
        cout << "节点 " << v << " 无法到达" << endl;
        return;
    }

    // 递归打印路径
    if (path[v] != -1) {
        PrintPath(g, path, dist, path[v]);
    }

    cout << v << " ";
}

时间复杂度O(n^2)

弗洛伊德( Floyd )算法

算法原理：递归

n阶数组D：用于保留每一步所求得的所有顶点对之间的当前最短路径长度

初始化： D[i][j] = cost(i, j)用邻接矩阵进行初始化

状态转移方程： D^k[i][j] = min{D^k − 1[i][j], D^k − 1[i][k] + D^k − 1[k][j]}更新v_i到v_j的最短路径

path数组：用于存储最短路径，初始化若没有直接路径则 path[i][j] = −1，若有则 path[i][j] = j

算法思路：

初始化数组，遍历n*n次，即v_i到v_j和v_j到v_i都遍历一遍，通过状态转移方程更新D数组的值，若找到短的路径，则同时也更新path数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// Floyd算法
template <class T>
void MGraph<T>::Floyd(int path[][MAXV], int D[][MAXV]) {
    // 初始化距离矩阵D和路径矩阵path
    for (int i = 0; i < vexnum; ++i) {
        for (int j = 0; j < vexnum; ++j) {
            D[i][j] = edges[i][j];
            //初始化path
            if (D[i][j] < INF && i != j)
                path[i][j] = j;  // 若i到j有直接路径，记录路径
            else
                path[i][j] = -1; // 否则路径不存在
        }
    }

    // 核心Floyd-Warshall算法
    for (int k = 0; k < vexnum; ++k) {
        for (int i = 0; i < vexnum; ++i) {
            for (int j = 0; j < vexnum; ++j) {
                if (D[i][k] != INF && D[k][j] != INF && D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];  // 更新最短路径长度
                    path[i][j] = path[i][k];      // 更新路径
                }
            }
        }
    }
}

函数OutputPath用于输出保存于二维数组path中的所有路径以及保存于二维数组D中的路径长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

template <class T>
void OutputPath(MGraph<T> &G, int path[][MAXV], int D[][MAXV]) {
    // 遍历所有顶点对，输出源点到目标点的最短路径及路径长度
    for (int i = 0; i < G.vexnum; ++i) {      // 遍历所有源点 i
        for (int j = 0; j < G.vexnum; ++j) {  // 遍历所有目标点 j
            if (i != j) { // 排除自身到自身的情况
                if (D[i][j] == INF) {  // 若距离为无穷大，表示无路径
                    std::cout << "Path from " << i << " to " << j << ": No path exists.\n";
                } else {  // 若存在路径
                    std::cout << "Path from " << i << " to " << j << " (Length: " << D[i][j] << "): ";
                    
                    // 输出路径，使用 path 数组逐步跟踪中间节点
                    int temp = i;      // 起始点
                    std::cout << temp; // 输出源点
                    while (temp != j) { // 当未到达目标点时
                        temp = path[temp][j];  // 获取路径中的下一个节点
                        std::cout << " -> " << temp; // 输出中间节点或目标点
                    }
                    std::cout << std::endl; // 换行
                }
            }
        }
    }
}

AOV网与拓扑排序

有向无环图：不含环的有向图

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V, V2 ,..V n，满足若从顶点V到V;有一条路径，则在顶点序列中顶点V必在顶点V;之前。则我们称这样的顶点序列为一个拓扑序列。

拓扑排序：其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:

①从AOV网中选择一个没有前驱的顶点并输出。 ②从网中删除该顶点和所有以它为起点的有向边。 ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。

算法原理：dfs

对于AOV 网宜采用邻接表作为存储结构

数组indegree：用于存放各个顶点的入度

算法思路：

每次遍历数组indegree，查找入度为零的顶点，将其加入队列，再遍历邻接表，将遍历到的顶点的indegree值减一，并判断是否为零，若为零则加入队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 拓扑排序实现
void Graph::topologicalSort() {
    vector<int> indegree(V, 0); // 入度数组
    queue<int> q;              // 队列

    // 计算所有顶点的入度
    for (int i = 0; i < V; i++) {
        for (int v : adj[i]) {
            indegree[v]++;
        }
    }

    // 将入度为0的顶点加入队列
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0; // 用于检测图是否存在环

    // 输出拓扑排序
    cout << "拓扑排序顺序为: ";
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 输出顶点
        count++;

        // 遍历该顶点的所有邻接点，并更新它们的入度
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    cout << endl;

    // 如果没有输出所有顶点，说明存在环
    if (count != V) {
        cout << "图中存在环，无法进行拓扑排序！" << endl;
    }
}

参考文献

数据结构：图(Graph)【详解】_图数据结构-CSDN博客

数据结构-图-prim（普里姆）算法最小生成树（过程分析+手写代码）_哔哩哔哩_bilibili

数据结构-图-最小生成树-克鲁斯卡尔（Kruskal)算法-手画+过程分析+代码_哔哩哔哩_bilibili

论文阅读：Jupiter: friend or foe? An answer

奥尔特云：

奥尔特云 - 维基百科，自由的百科全书

长周期彗星：这些天体来自奥尔特云，周期超过200年，具有完整的轨道倾角范围，由 1012-1013 个冰体组成，其中绝大多数的直径小于 10 公里，并占据一个距离太阳约 103-105 天文单位的厚球形壳

短周期彗星：一般认为来自于柯伊伯带或离散盘。周期在200年以下

短周期彗星有两大类：木星族彗星（半长轴小于5天文单位）及哈雷类彗星

短周期彗星 - 维基百科，自由的百科全书

木星族:木星有时会缩短一颗彗星的运动周期，有时会延长一颗彗星的运动周期，有时会改变彗星轨道，从而使得周期彗星变成非周期彗星，反过来也一样。周期3-10年，远日点在木星轨道附近的彗 星称为木星族彗星。

改变木星轨道上巨星的质量Y来 自小行星带的轰击

我们研究了改变“木星”质量对地球从小行星带向内抛出的物体所经历的撞击率的影响。我们在模拟冲击通量时遇到了一些问题。小行星被认为构成了最大的威胁。然而，在创建一群可能进化到撞击地球轨道的测试小行星时，我们面临着巨大的不确定性，特别是与整合开始时小行星的分布有关的不确定性。

因为自木星形成以来，它一直在扰乱目前在小行星带中观察到的物体的轨道。因此，尝试为这颗小行星构建一个受干扰程度要小得多的初始种群是很重要的

我们 2008 年的论文详细介绍了我们如何确定小行星分布，$\ N_{0}(a)=k(a-a_{min})^\frac{1}{2}$，其中 N（a） 是距离太阳 a 的小行星数量，k 是常数， a_min 是小行星分布的内部边界。 a_min的值为1.558AU，相当于火星的轨道半长轴，1.52 AU，加上三个 希尔半径

归一化常数 k 的确定 为了使总的小行星数量  N_total, 为一个固定值，我们需要对 N(a)进行归一化。通过对 N(a)在范 围[amin,amax]内积分，可以得到归一化常数 k

$\ k=\frac{3N_{total}}{2(a_{max}-a_{min})^\frac{2}{3}}$

希尔半径$\ R_{H}=a_p(\frac{M_{planet}}{3M_{Sun}})^\frac{1}{3}$，ap 是行星轨道的半长轴，M 表示质量。希尔球半径是一个天体对其周围物体产生重力影响的范围

以这种方式创建的物体代表一个碎片圆盘，在行星形成过程中受到了适度但不过度的搅拌（例如 Ward 2002）。

然后，在地球、火星、木星、土星、天星和海王星的影响下，使用 MERCURY 包中包含的混合积分器对测试粒子进行了 1000 万年的跟踪。进行了简单的测试积分，以检查地球横截面积对所经历的冲击通量的影响。正如预期的那样，发现撞击率与地球的横截面积成正比，引力聚焦的影响可以忽略不计。为了提高撞击率以获得合理的撞击统计数据，因此我们将地球膨胀到  10⁶ 公里的半径。在我们的整合中，小行星与行星和太阳发生引力相互作用，但彼此之间没有相互作用

我们运行中使用的 “Jupiter” 经过修改，因此我们运行了 12 个单独的质量。在木星质量 MJ 的倍数中，这些是：0.01、0.05、0.10、0.15、0.20、0.25、0.33、0.50、0.75、1.00、1.50 和 2.00。每个“木星”的轨道元素与今天的木星相同。同样，模拟中其他行星的元素与今天相同：一次运行和下一次运行之间行星设置的唯一区别是木星质量的变化——所有其他变量都是恒定的。

显示了我们的模拟中 通量与质量关系的形式，其中小行星是 源群体。这些结果令人惊讶。在 1.00 M J 时，对地球的撞击次数约为 0.01 M J 时的撞击次数的 3.5 倍Y几乎没 有屏蔽！在这两个”木星”质量之间， 在 0.2 M J 左右存在一个峰值，其中撞 击次数几乎是 1.00 M J 时的两倍。

我们随机生成了 100 000 个测试群体粒子，近日点位于 0.1– 10 AU 范围内，远日点位于 10 000 和100 000 个AU。人口的结构是为 了模仿观察到的长周期彗星的远日点 分布。近日点距离 q 确定如下$\ q=0.1+[(q_{max}-q_{min})^\frac{2}{3}*random]^\frac{2}{3}$其中  q_max 和 q_min分别是 0.1 和 10 AU 的最大和最小可能近日点 距离，而 random 是在克隆程序中 生成的 0 到 1 之间的随机数。这导 致大约 3% 的初始样本具有与地球 轨道交叉的轨道（地球交叉轨 道），大约 38% 位于最初与木星 交叉的轨道（q 小于或等于 5.203 AU 的轨道）。这个分布是一个简 单但有效的尝试，试图拟合新奥尔 特云彗星的已知分布

我们计算了奥尔特云 彗星在（膨胀的）地球上的碰撞次 数。需要采取不同的方法。奥尔特 云彗星的轨道周期是如此之大，以 至于即使在 100 Myr 的模拟中，即 使地球严重膨胀，也很少会与地球 近距离接触。因此，为了直接确定 对地球的撞击率，我们必须模拟大 量的测试粒子，其数量级比所使用 的粒子高出许多数量级

我们模拟中使用的”木 星”的质量被修改了从一个场景到 下一个场景。总共考虑了五种不同 的场景。研究了质量为木星质量 0.25、0.50、1.00 和 2.00 倍 的”木星”系统，以及不存在木星 的系统。和以前一样，场景之间的 唯一区别是木星的质量Y所有其 他参数都是恒定的。

大质量情况下彗星的消失速度 明显快于低质量木星的情况。即使 仅在 1 Myr 后，木星质量较高的喷 射率就很明显，并且一直持续到我 们模拟的最后，到那时，在所有情 况下，仅保留了初始彗星种群的一 小部分。

值得注意的是，即使没有 木星存在，到运行结束时，长周期 彗星的数量仍然会显着减少。由于 木星不存在（“木星”质量为 零）

。当考虑基于喷射率的初始代理 的结果时，重要的是要确保该措施 是实际上是冲击通量的合适代理。 例如，地球上的碰撞率似乎可能并 不简单地与幸存的奥尔特云彗星的 数量成正比。特别是，另外两种可 能性似乎值得进一步研究，以确保 我们最初的假设是正确的：考虑到 所研究的彗星轨道的扩展，重要的 是要检查是否存在穿过地球轨道的 奥尔特云彗星的优先生存（ q < 1 AU)，或那些不存在的 (q > 1 AU)。

换句话说，当考虑到长周期彗星通量（与我们之前 的发现相反），一颗质量更大的木星 肯定会在不存在这样的行星的情况下 为地球提供一些可测量的屏蔽。

事实上，只有在来自奥尔特 云的彗星的情况下，我们的结果表 明木星确实是长期以来所假设的地 球的朋友！

然而，应该指出的 是，在长周期轨道上运动的物体平 均而言通常比在短周期或星状轨道 上运动的物体具有更大的碰撞速度 （这是由于它们较高的倾角[包括逆 行轨道]和更大的轨道）速度为 1 天 文单位），这增加了奥尔特云彗星 作为轰炸机群体的相对重要性。

作 为一个整体，我们的工作表明，而 不是充当作为地球的盾牌，木星反 而增加了我们星球所经历的冲击通 量，超过了如果这颗行星以某种方 式神奇地从我们的太阳系中移走时 所受到的冲击通量。然而，如果木 星的质量减少到土星的质量，地球 的情况会更糟

事实上，只有在来自奥尔特 云的彗星的情况下，我们的结果表 明木星确实是长期以来所假设的地 球的朋友！

我们的结果令人震惊。对于当前时代威胁地球的两个主要种群（近地小行星 和短周期彗星），我们发现木星质量与撞击率之间的关系相当复杂。在”木星”质量 较低的情况下，两颗行星的撞击率都非常低，因为这些小行星很难在地球交叉轨道上 放置物体。同样，在高”木星”质量（类似于或大于我们的木星）时，两个种群的撞 击率都相对较低，尽管略高于质量最小的”木星”。然而，在这两个极端之间，我们 在模拟中发现地球上的撞击通量出现了显着的峰值。对于近地小行星(Horner & Jones, ̚ ̘ ̘ ̠ b)和短周期彗星(Horner & Jones, 2009)，我们发现当模拟中的”木 星”在0.2到0.3倍之间时，撞击通量最大。和我们的木星一样大。换句话说，与质量 小得多的情况相比（例如，当它的质量与海王星相当时），我们的木星仅提供适度的 屏蔽，但如果它围绕土星的质量，那么地球上的撞击通量将是远远大于我们观察到 的。

当我们研究木星质量对第三种潜在危险天体M长周期彗星M的撞击率的影响时 （例如 Wiegert & Tremaine, 1999, Levison, Dones &Duncan, 2001, Horner & Evans, 2002），我们发现”木星”质量越大，对地球的撞击率就越低（Horner，Jones &钱伯斯， 2010）。那么，对于长周期彗星来说，木星似乎确实起到了盾牌的作用。然而，长周期彗星 被认为只对小行星和彗星对地球的影响贡献了一小部分（

这是否也在确定其宿主系统中潜在宜居行星的撞击通量中 发挥作用？在这项工作中，我们通过检查木星轨道偏心率和倾角的影响，建立在早期结果 的基础上。在这项工作中，我们只考虑两个主要的撞击星群M近地小行星和短周期彗星。 由于长周期彗星在轨道倾角基本上各向同性分布的轨道上运行，并且几乎不受太阳系引力 约束，因此可以合理地假设木星轨道的微小变化对彗星通量几乎没有影响或没有影响。

总体而言，很明显，巨行星轨道偏心率的增加会导致近地小行星和短周期彗星对地球的 撞击通量增加。

不要过分苛责自己

​ 数竞的成绩出来，没有看到自己名字，不知道为什么还是有些难受，理性告诉我这是理所应当，因为我根本没有为这个比赛花任何时间，只有前一天晚上临时抱佛脚的两个小时，对于报名，却没有复习的原因，如果别人让我做出解释，我可能会说，那段时间太累了，这不是借口，我记忆中那段时间确实是挺累的，但现在我已经不记得我那段时间忙些了什么，或者为自己留下了什么实际性的收获，似乎什么都没有。

​ 结果上看，我对待这个比赛的态度是放弃的，那既然已经决定放弃的事情，为什么还会有些难受呢，我想，一方面，我还对不劳而获存在不切实际的幻想，幻想着不复习，幻想着靠自己脑子那一点点知识，就想在竞赛中占有一席之地，幻想着运气一次又一次眷顾自己，事实会告诉我这是不可能的；另一方面，每个人的精力确实是有限的，但我总是比较贪心，这也想要，那也想要，结果就是应接不暇，这是好强导致的吗，感觉还是比较幼稚，没有舍弃与选择的魄力，没有舍弃的勇气的人，什么也改变不了，hhh突然想起巨人的台词，有些中二嗷，扯远了扯远了。

​ 其实，就算做不到也没关系，现实已经一次又一次地证明了，人无完人，这件事你做不好不代表其他事你做不好啊，我并不喜欢钻研数学啊物理啊做题做试卷这种，但我决定参加一些项目，学习新的知识很有意思，我也确实在其他一些科研比赛中获得不错的成绩，为什么要为一个小小的数竟，过分地苛责自己呢，况且你一开始就没有好好准备他，失败是理所应当的，你并没有损失什么，看得开一些，向前看，不要为一些小失败而驻足不前，不要为一些小失败过分地苛责自己。

​ 突然发现把一些心里话写下来，心情真的舒畅了很多，继续加油，不要停止奔跑。

笨鸟的共鸣

​ 今天刷谈笑间，看的一位同学很沮丧，说自己在南师大感受到了前所未有的压力，自己是高考发挥超常才来到南师大的，而身边很多同学却是高考发挥失常，在大学的学习中感受同辈人巨大的压力，不禁让我引起共鸣。别人的失常发挥上的学校，却是高中三年竭尽全力的结晶，甚至是高考的超常发挥才带来的。想到这里，我不禁再次感慨人与人之间差距的巨大。

​ 但是，大一一年已经过去，回望这一年，笨鸟变了吗，变了，这只原来的笨鸟也获得很多成就，也在成长，也遇到很多同行路上的好友，甚至也成了别人口中的优秀者。但他真的变了吗，其实没变，他还是那只笨鸟，天赋比他好的大有人在，比他努力者也数不胜数，他始终要以一种谦逊的态度，然后不断学习，不断奔跑。高中，大学，都只是一个跳板，这种笨鸟天生不会飞，通过这一个个跳板，爬至高处，才能看见世间美景。

总结与反思-11.20

距离我正式开始写博客不知不觉已经过去一个多月，决定写一篇随笔，总结反思一下

期中已经考完了，回过头看，其实我对我这个学期的上半学期并不满意，大物的期中和线代的第一次阶段性考核实在是不理想，这跟我自己的学习状态有关，开学一开始给自己定的这学期的主基调是不要太累，导致一直对去图书馆学习十分反感，每天就是在宿舍玩一玩浪费时间，现在回想起来还是挺后悔的，除了期中考试的不如意，主要还因为一个事情让我启发很大，就是我同学的动态，他分享每天自己的收获，可能是学习可能是看书，我看了之后第一感觉是非常的佩服的，觉得他很有毅力很自律，但是他在动态下面评论的一句话让我深有感触，他说他并不觉得他很自律，他没有强迫自己学习，他是以一个享受地态度做这些事，当时我看了可以说大受震撼，因为在过去的一年大学生活中，我一直是以强迫的态度让自己去图书馆的，有时就算到图书馆也坐立不安，最后干脆去都不去了。相比之下，我发现我对自律的理解真是太浅薄了。自律不是强迫自己做某件事情，而是想做成什么事一定会做成的决心。于是，我以一种全新的态度重新审视学习。不想学线代了？那就别强迫自己，看看科研项目相关的事，这样坚持几天下来，我发现这几天过的十分充实，一种精神上的满足。这对我来说，确确实实是一大收获，希望这种享受学习的态度能伴我一直走下去。

这里引用一下他的话，作为记录

有人爱一行干一行，有人干一行不爱一行，有人爱不干的那一行…感觉我是那种“干一行爱一行”的人，越做越觉得有趣，做一点就想知道更多（可能是我运气好刚好碰上的都是能爱上的..)如果单纯为了绩点不需要这样，刷题就好，但是我会把“学习”当做是我的一种生活或者说是娱乐方式

我很少痛苦地去学习，我要是觉得不舒服就会去学别的，去看书（或者刷刷手机)我也经常写很慢写很久停不下来，如果只是为了做题完全不需要。嗯希望给大家一个思路都能发现生活中的美好～导

但令我感到开心的是，我在健身这件事上做到了坚持，以前我一直觉得自己总是三分钟热度，什么事情都做不长久，如今回想起来，我自高中以来，已经做成了很多很多我以前不敢想的事情，包括对英语的学习，包括高考的超常发挥，包括大学以来获得的很多成就，希望能对自己更有自信一些，向更好的自己前进！

树

树的基本术语

1. 结点的度和树的度

   树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。

2. 孩子，双亲，兄弟结点

3. 路径和路径长度

   树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。 注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。

4. 子孙结点和祖先结点

   根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。

5. 结点的层次和树的高度

   结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。

6. 有序树和无序树

   树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。

7. 森林

   森林是m (m≥0)棵互不相交的树的集合。

树的存储结构

多叉链表表示法

采用多叉链表表示法存储树，许多算法设计可以直接参照二叉树的二叉链表结构的算法。其优点是简单易学，缺点是存在许多指针域的浪费。设树中结点数是n，树的度是k，则共使用了n×k个指针域，而这其中只有n -1个非空指针城。

孩子链表表示法

当树的度较大时，CTree类可以减少多叉链表表示法的空间浪费。但是，当插入、删除结点时，却会涉及多个孩子链表的调整,还有可能造成存储空间的再分配，因此时间复杂度较大。在CTree类中，利用孩子链表可以方便、快捷地查找指定结点的孩子结点。但是，查找双亲结点则需遍历所有的孩子链表,因此效率就低得多了。

双亲表示法

在PTree类中，不仅利用结点的双亲指针域很容易找到其双亲结点，而且查找其所有祖先结点也非常便利、高效。若需要查找指定结点的孩子或子孙结点，则需遍历整个树的存储空间，效率就低得多了。

孩子兄弟表示法

因为孩子兄弟表示法建立起了树和二叉树之间的对应关系，所以常常将其称为树的二叉树表示法。相比树的其他存储结构，孩子兄弟表示法既简化了结构，又可以将许多二叉树的优秀算法移植到树结构的应用中来，因此具有很好的学习、应用价值。

树的操作算法

构造算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// 构造函数
    CSTree(vector<pair<T, T>>& ps) {
        if (ps.empty()) {
            root = nullptr;
            return;
        }
        // 创建根节点
        root = new CSNode<T>(ps[0].first);
        root->firstchild = nullptr;
        root->nextsibling = nullptr;

        // 插入其他节点
        for (size_t i = 0; i < ps.size(); i++) {
            InsertNode(ps[i]);
        }
    }
// 插入节点
    void InsertNode(pair<T, T>& p) {
        // 创建新节点
        CSNode<T>* child = new CSNode<T>(p.second);
        child->firstchild = nullptr;
        child->nextsibling = nullptr;

        // 找到父节点
        CSNode<T>* parent = Search(root, p.first);
        if (!parent) {
            cout << "Parent node " << p.first << " not found!" << endl;
            return;
        }

        // 若父节点无子节点，将新节点作为第一个子节点
        if (parent->firstchild == nullptr) {
            parent->firstchild = child;
        } else {
            // 若父节点已有子节点，将新节点作为最后一个子节点
            CSNode<T>* temp = parent->firstchild;
            while (temp->nextsibling != nullptr) {
                temp = temp->nextsibling;
            }
            temp->nextsibling = child;
        }
    }

计算树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 计算指定节点子树的高度
template <class T>
int CSTree<T>::Height(CSNode<T>* p) {
    if (p == nullptr)  // 如果节点为空，返回高度 0
        return 0;

    int maxheight = 0;  // 初始化子树的最大高度为 0

    // 遍历所有子节点
    for (CSNode<T>* child = p->firstchild; child != nullptr; child = child->nextsibling) {
        int height = Height(child);  // 递归计算子节点的高度
        if (height > maxheight)      // 更新最大高度
            maxheight = height;
    }

    return maxheight + 1;  // 当前节点的高度为子树最大高度 + 1
}

// 外部接口：计算整棵树的高度
template <class T>
int CSTree<T>::Height() {
    return Height(root);  // 从根节点开始计算高度
}

计算所有结点的度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 计算指定节点的度并递归处理其子树
template <class T>
void CSTree<T>::Degree(CSNode<T>* p) {
    if (p == nullptr)  // 如果节点为空，直接返回
        return;

    p->degree = 0;  // 初始化节点的度为 0

    // 遍历所有子节点，统计度
    for (CSNode<T>* child = p->firstchild; child != nullptr; child = child->nextsibling) {
        p->degree++;  // 子节点存在则度加 1
    }

    Degree(p->firstchild);    // 递归处理子节点的度
    Degree(p->nextsibling);   // 递归处理兄弟节点的度
}

// 外部接口：计算整棵树的所有节点的度
template <class T>
void CSTree<T>::Degree() {
    Degree(root);  // 从根节点开始计算度
}

二叉树

特殊的二叉树

二叉树的性质

非空二叉树上的叶子结点数等于度为2的结点数加1，即 n₀ = n₁ + 1

因为二叉树中所有节点的度只能是 0、1、2，所以节点总数  n = n₀ + n₁ + n₂

其次考虑二叉树的分支总数。将二叉树的分支总数记作 m。 因为所有的分支是由度为 1 和度为 2 的节点发出的，所以m = n₁ + 2 × n₂

最后，由树的性质 1，可得 n = m + 1，即n₀ + n₁ + n₂ = n₁ + 2 × n₂ + 1

二叉树的存储结构

顺序结构

当二叉树单分支节点较多，高度变化较大时，空间浪费现象惊人

链式结构

二叉树的遍历

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

先序遍历算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13

template <class T>
void BiTree<T>::PreOrder(BiNode<T>* p) {
    if (p == NULL)
        return;             // ① 若二叉树为空，则遍历结束
    cout << p->data;        // ② 访问当前结点
    PreOrder(p->lchild);    // ③ 先序遍历当前结点的左子树
    PreOrder(p->rchild);    // ④ 先序遍历当前结点的右子树
}

template <class T>
void BiTree<T>::PreOrder() {
    PreOrder(root);
}

层序遍历：利用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

template <class T>
void BiTree<T>::LevelOrder() {
    if (root == NULL)
        return;             // ① 若二叉树为空，则遍历结束

    LinkQueue<BiNode<T>*> Q;    // 定义一个队列存储节点指针
    Q.EnQueue(root);            // ② 将根指针加入指针队列

    while (!Q.Empty()) {        // ③ 若指针队列不空，则循环
        BiNode<T>* p = Q.DeQueue();   // ④ 出队列，得到当前指针 p
        cout << p->data;              // ④ 访问当前结点

        // ⑤ 若当前结点有左孩子，则左孩子地址进指针队列
        if (p->lchild != NULL)
            Q.EnQueue(p->lchild);

        // ⑤ 若当前结点有右孩子，则右孩子地址进指针队列
        if (p->rchild != NULL)
            Q.EnQueue(p->rchild);
    }
}

二叉树的构造算法

先序序列是abdecf，带空指针标记的先序序列是abd**e**cf ***

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template <class T>
BinNode<T>* BinTree<T>::CreateByPre(vector<T>& pre, int& i) {
    T e = pre[i]; // 提取当前数据
    i++;
    if (e == '*') // 若是特殊数据，返回空指针
        return NULL;

    // 创建新结点
    BinNode<T>* p = new BinNode<T>;
    p->data = e;
    // 创建左子树
    p->lchild = CreateByPre(pre, i);
    // 创建右子树
    p->rchild = CreateByPre(pre, i);

    return p;
}

template <class T>
BinTree<T>::BinTree(vector<T>& pre) {
    int i = 0; // 向量 pre 的下标变量
    root = CreateByPre(pre, i); // 从先序序列构造二叉树
}

二叉树的其他操作算法

计算结点数

1
2
3
4
5
6
7
8
9
10
11
12
13

template <class T>
int BiTree<T>::Count(BiNode<T>* p) {
    if (p == NULL)
        return 0;  // 当前节点为空，返回 0
    int left = Count(p->lchild);  // 统计左子树节点数
    int right = Count(p->rchild); // 统计右子树节点数
    return 1 + left + right;      // 当前节点总数 = 左子树 + 右子树 + 当前节点
}

template <class T>
int BiTree<T>::Count() {
    return Count(root); // 从根节点开始统计
}

计算高度

1
2
3
4
5
6
7
8
9
10
11
12
13

template <class T>
int BiTree<T>::Height(BiNode<T>* p) {
    if (p == NULL)
        return 0;  // 空节点高度为 0
    int left = Height(p->lchild);  // 左子树高度
    int right = Height(p->rchild); // 右子树高度
    return (left > right ? left : right) + 1; // 树高度为左右子树最大高度 + 1
}

template <class T>
int BiTree<T>::Height() {
    return Height(root); // 从根节点开始计算树高度
}

查找结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

template <class T>
BinNode<T>* BiTree<T>::Search(BinNode<T>* p, T e) {
    if (p == NULL)
        return NULL;  // 查找失败
    if (p->data == e)
        return p;     // 查找成功，返回节点指针

    // 在左子树中递归查找
    BinNode<T>* q = Search(p->lchild, e);
    if (q != NULL)
        return q; // 若在左子树中找到，返回结果

    // 在右子树中递归查找
    return Search(p->rchild, e);
}

template <class T>
BinNode<T>* BiTree<T>::Search(T e) {
    return Search(root, e); // 从根节点开始查找
}

线索二叉树

哈夫曼树

参考文献

数据结构：树(Tree)【详解】_数据结构 树-CSDN博客

本文对目前已收集到的论文进行筛选工作，并简单概述可取之处

视频监控中人体暴力行为检测系统设计与应用

非常非常好的一篇，跟我们要做的方向很贴合，每个人都要看一下，以下是我认为可以学习的地方：

1. 绪论部分：课题研究的背景和意义；从智能视频监控技术和行为识别算法两个方面介绍了研究现状

2. 同样选用了RWF-2000数据集，并给出了理由，同时介绍了三大常见数据集并进行了比较（HMDB-51，UCF101，Kinetics）；在模型框架技术选型方面，简要介绍了 传统方法，然后对比了深度学习下的基于人体骨架的方法以及基于视频的方法。 之后详细介绍了三类基于视频的深度学习方法（双流法，3D卷积方法 和基于时序模型的方法）

​ 本文文采用了双流模型 作为基础框架，我后续了解双流法与我们的 多模态方向是很贴合的

3. 本文完成了人体暴力行为检测系统的设计与实现，包含离线分析和在线监测两种模式，这跟我们的设想很符合

基于注意力机制的暴力音视频检测方法研究

与上一篇同样是哈尔滨工业大学的硕士论文，侧重点也是多模态暴力检测，本文先提出分别基于视觉通道和基于听觉通道的暴力音频检测，再提出了基于视听觉通道的音视频特征融合的暴力音视频检测

本文开头的课题研究的背景和意义和研究现状同样值得参考

基于多模态的校园暴力检测

给我感觉一般，多模态的部分写的并不是很好，他还说的一个基于多模态的校园暴力检测，感觉什么都写到了什么都写的不是很精

但是他在相关理论基础详细地介绍了深度学习网络（RNN，LSTM，GRU）和人体动作识别（openpose），可以参考学习

基于对比学习的视频暴力行为检测算法及 TensorRT 平台实现

里面的对比学习和注意力机制不是很看得懂，但感觉写的挺好的，这篇还把识别系统做在TensorRT 平台实现轻量化，这个跟我们关系不大，只做了解

基于YOLO和ConvLSTM混合神经网络的暴力视频检测

有yolo相关知识，后续可做参考学习

国外论文

因为英文看的太费劲，对国外论文暂时只做初步筛选

Conv3D-Based Video Violence Detection Network Using Optical Flow and RGB Data：光流和RGB数据多模态

Multimodal vision-based human action recognition using deep learning: a review：关于多模态的综述论文，这一篇写的不错，有时间值得啃一下

A Real-Time 3-Dimensional Object Detection Based Human Action Recognition Model：3D卷积神经网络（3DCNN）、LSTM乘法递归网络和YOLOv6实时目标检测

学习计划

• yolo深入学习，代码初步运行尝试
• 视频异常检测与视频动作识别的概念明晰与区分
• 实际操作知识储备：视频预处理，训练，测试
• 具体算法知识储备：3D CNN ，2D CNN + RNN，LSTM
• 根据PPT初步构建立项书框架

视频异常检测与视频动作识别的概念明晰与区分

我们后续做的主要是暴力行为的识别，我个人原本概念并没有清楚，以为是属于视频异常检测领域，但这里更关注的是人的动作，应该与视频动作识别更贴合，以下是我结合网上文章理解的二者区别，用词不严谨处还请指正

视频异常检测系统能够检测明显偏离正常的异常行为或实体，例如在视频监控的先验知识有限的情况下识别多个移动物体，或检测特定事件，例如打架、踩踏、交通事故和流浪。视频异常通常是上下文的，并根据真实场景定义。具体来说，检测过程集中于识别所有视频中包含异常的视频片段，而定位致力于确定哪一帧是异常的，并解释该帧的哪一部分是异常的。

视频动作识别是通过已标记的数据集训练模型实现视频理解视频分类的功能。动作识别的目标是识别出视频中出现的动作，通常是视频中人的动作。视频可以看作是由一组图像帧按时间顺序排列而成的数据结构，比图像多了一个时间维度。动作识别不仅要分析视频中每帧图像的内容，还需要从视频帧之间的时序信息中挖掘线索。动作识别是视频理解的核心领域，虽然动作识别主要是识别视频中人的动作，但是该领域发展出来的算法大多数不特定针对人，也可以用于其他视频分类场景。

二维卷积 2D CNN

卷积神经网络（convolutional neural network）是含有卷积层（convolutional layer）的神经网络。它有高和宽两个空间维度，常用来处理图像数据。

卷积神经网络的结构

层级网络，数据包括输入层，卷积层，激活层，池化层，全连接层等

输入层：就是原始图像，非提取的信息，因此卷积神经网络是一个无监督的特征学习网络，数据输入层主要对原始图像数据进行预处理，基础的操作包括去均值、灰度归一化，数据增强等；

卷积层：就是特征提取层，一般卷积神经网络包含多个卷积层，一个卷积层可以有多个不同的卷积核。通过不同的多个卷积核对图像进行预处理，提取特征，每个卷积核会映射出新的特征平面。再通过非线性激活函数对卷积结果进行处理；

激活层：卷积神经网络需要激活层进行特征的选择和抑制；

池化层：用于降低特征平面分辨率及抽象特征，可以有效的压缩网络参数和数据，减少过拟合。池化层最主要的作用就是压缩图像同时保存图像的特征不变；

全连接层：是卷积神经网络的最后，具有卷积核和偏移量两个参数。（fully connected layers，FC）在整个卷积神经网络中起到“分类器”的作用，全连接层则起到将学到的“分布式特征表示”映射到样本标记空间的作用。在实际使用中，全连接层可由卷积操作实现：对前层是全连接的全连接层可以转化为卷积核为1x1的卷积；而前层是卷积层的全连接层可以转化为卷积核为hxw的全局卷积，h和w分别为前层卷积结果的高和宽

卷积核的运算

应用

2D卷积神经网络（2D CNN）则主要用于处理二维图像数据，如人脸识别、物体检测和自动驾驶等任务。2D CNN通过将图像划分为多个小的矩形区域（也称为滤波器或卷积核），可以对每个区域进行独立的特征提取。这种网络结构可以有效地减少计算量，同时提高特征提取的精度。在计算机视觉领域，2D CNN已经成为许多重要应用的基石，如人脸识别和目标检测等。

三维卷积 3D CNN

三维卷积输入多了深度C这个维度，输入是高度H宽度W深度C的三维矩阵。

3D CNN是如何对时间维度进行操作的，如下图所示，我们将时间维度看成是第三维，这里是对连续的四帧图像进行卷积操作，3D卷积是通过堆叠多个连续的帧组成一个立方体，然后在立方体中运用3D卷积核。在这个结构中，卷积层中每一个特征map都会与上一层中多个邻近的连续帧相连，因此捕捉运动信息。

三维卷积和多通道卷积的区别

多通道卷积

具体的实现过程为：

3D CNN主要运用在视频分类、动作识别等领域，它是在2D CNN的基础上改变而来。由于2D CNN不能很好的捕获时序上的信息，因此我们采用3D CNN，这样就能将视频中时序信息进行很好的利用。

循环神经网络 RNN 与 长短期记忆 LSTM

史上最详细循环神经网络讲解（RNN/LSTM/GRU） - 知乎

【循环神经网络】5分钟搞懂RNN，3D动画深入浅出_哔哩哔哩_bilibili

【LSTM长短期记忆网络】3D模型一目了然，带你领略算法背后的逻辑_哔哩哔哩_bilibili

立项书框架构建

工作清单

1. 每个人写一份自我介绍，包括自身具备的知识条件、自己的特长、兴趣、已有的实践创新成果
2. 每个人查找8篇关于人体动作识别或者暴力事件识别的相关论文，要求：1.国内外论文都要有 2.每个人找好后打成一个压缩包发群里，并把论文名发群里，后面发的就不要跟上面重复了 3.压缩包中除了包含论文，再有一个word文档，简单说明收集每个论文的主要内容
3. 简单看一下我发群里的两份去年的立项书，结合立项书框架想一想，后续会进行分工

立项书框架

1. 项目研究背景
   1. 研究意义
   2. 国内外研究现状
      1. 人类动作识别现状
      2. 暴力行为识别现状
   3. 项目研究目标及主要内容
   4. 项目创新特色概述
   5. 项目研究技术路线
   6. 项目方案设计

PPT思路初步构建

背景与意义

1. 人体行为事件的含义与应用
2. 视频暴力行为识别的意义
3. 暴力行为的定义，早期与后续方法的比较，数据集的比较，暴力行为识别任务和应用

研究现状

单模态与多模态的优点和挑战

行为识别和暴力行为的识别和挑战

数据集的对比

解决方法的比较：3D CNN, 2D CNN+ RNN, 骨架

研究方法：抓住识别暴力的要素

一方面：抓住重要因素进行特征提取

另一方面：尽可能去除冗余信息（裁剪 / 去背景）

算法框架

注意力融合模块

总结

1. 提出了一种基于多模态特征融合的视频暴力行为识别算法。通过融合RGB模态提供的外观信息、RGB帧差提供的运动信息以及Depth模态提供的相对位置信息，丰富、完善了暴力行为的特征，使其能够准确、鲁棒地在复杂的真实环境下进行暴力行为识别。

2. 提出了一种自适应的注意力算法用于多模态融合。让模型自适应地学习不同模态特征之间的权重关系，允许模型根据具体任务动态调整每个模态的重要性，从而更灵活地应对不同的场景。

参考文献

【视频异常检测综述-论文阅读】Deep Video Anomaly Detection: Opportunities and Challenges-CSDN博客

视频理解综述：动作识别、时序动作定位、视频Embedding-CSDN博客

深度学习笔记—-三维卷积及其应用（3DCNN,PointNet,3D U-Net）-CSDN博客

安装，注意配置环境变量 $env:ZINC_FIRST_ADMIN_USER="admin"$env:ZINC_FIRST_ADMIN_PASSWORD=“admin” ..exe

加载示例数据，利用bash curl -L https://github.com/zincsearch/zincsearch/releases/download/v0.1.1/olympics.ndjson.gz -o olympics.ndjson.gz gzip -d olympics.ndjson.gz curl http://localhost:4080/api/_bulk -i -u admin:Complexpass#123 –data-binary “@olympics.ndjson”

概念 ZincSearch 是一个搜索引擎，允许您在上传到 ZincSearch 时搜索自己的数据。将其视为“Google”或“Bing”搜索，但仅用于您自己的数据。 ZincSearch 允许您索引 （json） 文档并允许进行全文搜索。

添加索引 使用 JSON 格式：{ “分析”： { “分析器”： { “默认”： { “type”： “standard” } } } } { “index”: “my_index”, “settings”: { “analysis”: { “analyzer”: { “default”: { “type”: “standard” } } } } }’ “index”: 指定你要创建的索引名称，这里是 my_index。 “settings”: 包含索引的设置。 “analysis”: 定义分析器的部分。 “analyzer”: 指定分析器的配置。 “default”: 定义默认分析器，类型为 standard。

索引的映射（mapping） 映射（mapping）是指在数据存储系统（如数据库或搜索引擎）中定义索引中字段的结构和属性的过程。它类似于数据库中的表结构定义 使用 JSON 格式：{ “属性”： { “内容”： { “type”： “text” } } }

参考文献 https://geekdaxue.co/read/ZincSearch-doc/create-update-index https://prabhatsharma.in/blog/in-search-of-a-search-engine-beyond-elasticsearch-introducing-zinc/