拓扑学是几何学的一个分支，但是这种几何学又和通常的平面几何、立体几何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。

举例来说，在通常的平面几何里，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里所研究的图形，在运动中无论它的大小或者形状都发生变化。在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。


所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”，而把连接实体的线路抽象成“线”，进而以图的形式来表示这些点与线之间关系的方法，其目的在于研究这些点、线之间的相连关系。表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中，我们要考察的是点、线之间的位置关系，或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构，但从拓扑结构的角度去看，由于点、线间的连接关系相同，从而具有相同的拓扑结构即环型结构。也就是说，不同的几何结构可能具有相同的拓扑结构。





作者：喵潇湘

链接：https://www.zhihu.com/question/26507158/answer/409420878

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2020年9月28日 周一 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

最近在看数据结构中的图，里面有一节叫做拓扑排序，不是很明白这个“拓扑”是什么意思，上网搜了一下，有个说法如下，感觉比较通俗易懂。

所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”，而把连接实体的线路抽象成“线”，进而以图的形式来表示这些点与线之间关系的方法，其目的在于研究这些点、线之间的相连关系。表示点和线之间关系的图被称为拓扑结构图。拓扑结构与几何结构属于两个不同的数学概念。在几何结构中，我们要考察的是点、线之间的位置关系，或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构，但从拓扑结构的角度去看，由于点、线间的连接关系相同，从而具有相同的拓扑结构即环型结构。也就是说，不同的几何结构可能具有相同的拓扑结构。

一句话总结：

拓扑结构：不考虑形状，不考虑连线的长短，侧重节点连或不连
几何结构：注重形状及连线的长度


参考文献
https://www.zhihu.com/question/26507158

以线性回归和逻辑回归来实际看一下什么是过拟合问题

 

线性回归

线性回归是使用多项式来拟合变量之间的关系，从而可以根据某些变量来预测另外的变量。

图中的一个红叉叉描述了一个关系实例，横轴代表房子面积，纵轴代表房子的面积。

最左边的图是使用一次多项式来拟合两个变量之间的关系，我们可以直观的感受到直线并不能很好的描述两个变量之间的关系，主要原因就是一次多项式的表达力不够，这个现象叫做欠拟合。

然后直接来看最右边的图，我们使用一个4次多项式来拟合两个变量之间的关系，这条曲线完美的通过了所有的样例点，但是这种扭扭曲曲的线条并不一定适用于未出现的样例点，只是很强的拟合了现有的数据，所以我们把这个情况称作过拟合（over fitting）



 

 逻辑回归

首先声明逻辑回归是一个分类问题，这个令人捉摸不透的叫法需要从很久很久以前说起。。。。。。所以就不说了

逻辑回归的本质是找到决策边界



主要参考自 吴恩达的机器学习视频  https://www.bilibili.com/video/BV164411b7dx?p=39

这篇文章中总结一下关于图的遍历算法，在此之前，我们来看一下什么是图：

首先，图可以分为有向图和无向图（这里只讨论无权图），像下面这个图就是无向图，V1 ~ V5 是图的顶点，而连接图的两个顶点的线就叫边或者专业一点的说法叫做：“度”，在无向图中，两个顶点之间的连线的方向可以是互换的，比如说，V1 顶点和 V2 顶点之间的边我们可以看做是以 V1 为起点， V2 为终点的一条边，也可以看做是以 V2 位起点， V1 位终点的一条边。由此，一个无向图的度的总数等于这个图中的边的总数的两倍，下面的那个图中一共有 7 条边，因为它是无向图，那么它的度的总数就是 14。



下面来看一下有向图：



有向图和无向图不同，图中的每一条边都是有方向的而且是唯一的，像下面的图中，V1 到 V2 中就只有一条边，方向是从 V1 到 V2 ，V2 到 V3 也只有一条边，方向是从 V2 到 V3。V1 和 V3 之间有两条边，分别是从 V1 到 V3 和 V3 到 V1 ，在这个有向图中度的总数为 4 。

接下来来看一下图的储存方式，我们用什么来储存一个图信息呢？最常用的方法就是通过图的邻接矩阵和邻接表来实现，邻接矩阵顾名思义就是用一个二维数组来储存图的信息，图的顶点数目为二维数组的下标最大值，如果两个顶点之间有边直接相连，那么对应的数组的值就为 1 ， 否则为 0。对于上面的图来说，一共有 7 个顶点，那么我们可以设置一个二维数组 a[7][7]，初始值全部设置为 0，之后根据边的信息将这个二维数组信息补全，比如：V1 顶点和 V2 顶点有一条边，那么 a[0][1] = a[1][0] = 1; （注意这里是无向图，所以正反都要储存），对于其余的边也是一样。那么邻接表呢？邻接表通过储存每一个点的度的信息来保存图的信息，我们先对图的边设置一个结构体来描述一条边（终点、下一条边的结构体信息指针），然后设置一个结构体数组来保存每个顶点的边的信息，比如下面的结构体：



struct Node {
    int end;
    struct node *next;
};


那么只要 next 指针不为空，就证明这个顶点还有边。对于上面的图，我们可以设置一个 7 个元素的结构体数组：Node node[7]; 之后对每一个顶点储存边的信息。

好了，对图有了基本的认识之后，我们来看一下图的遍历，所谓图的遍历，就是根据某种算法来将图中的顶点通过连接的边全部访问一遍。在遍历的算法方面，我们可以有两种选择：深度优先遍历和广度优先遍历，先来看看深度优先遍历：深度优先遍历是利用了栈的原理来对图的顶点进行访问，类似我们之前总结过的深度优先搜索，我们总是通过当前顶点的第一条出边（专业术语是：出度）（边的结束顶点下标最小并且这条边的结束顶点还未被访问过）来访问这条出边的结束顶点，之后对当前顶点做同样的处理，直到所有的顶点都被访问完成。

我们以上面第一张无向图为例，
首先，我们先从 V1 顶点开始访问，然后我们对 V1 顶点的度进行讨论，我们发现顶点 V1  的第一条边的结束顶点 V2 还没有被访问过，
这里为什么选择 V2 而不选择 V4 呢？
因为 V2 是第二个顶点，其作为数组下标肯定比第四个顶点小，而我们每次就是要找出还未被访问过的并且作为数组下标最小的顶点来进行访问。
好了，我们继续对 V2 进行讨论，我们发现 V3 也没被访问过，于是访问 V3 ，接下来是 V4 ，最后是 V5，
于是这个无向图的深度优先遍历的结果就是 V1 --> V2 --> V3 --> V4 --> V5。
来看一张图：




为了拍这张图也是不容易，寝室光线不好，在寝室拍了几次效果都不好，然后跑去阳台拍，结果还把纸弄湿了~

好了，小伙伴们能理解这个过程就可以了，根据这个原理我们可以写出伪代码：

// 对 n 顶点进行访问讨论
void dfs(int n) {
    cout << n << " ";
    for(int i = 0; i < n; i++) {
        if(e[n][i] == 1 && i 顶点还未被访问过) {
            标记 i 顶点为已经被访问过 
            dfs(i); // 继续对 i 顶点进行访问讨论
        }
    }
}


下面我们来看一下广度优先遍历：广度优先遍历算法思想是借助队列来完成的，我们每次对当前顶点的所有的出边（出度）进行讨论，如果某条边的结束顶点还未被访问过，那么就把顶点加入到队列的队尾中，直到当前顶点的所有边都讨论完了，我们再从队列头部取出一个顶点，继续对这个顶点的出边进行讨论，重复这个过程，直到队列为空。

我们还是以上面那个无向图为例，来看一下广度优先遍历：
首先将 V1 顶点加入队列中，然后取出队列头元素，也就是 顶点 V1 ，然后对 V1 顶点的两条出边进行讨论，
我们发现这两条出边的结束顶点 V2 V4  都没有被访问过，
于是，我们把 顶点 V2 和 V4 加入队尾，并且将顶点 V1 出队列（因为已经把 V1 的所有出边都讨论完了），
接下来继续取出队列的头元素，也就是 V2 顶点，之后对它的出边进行讨论并且把没有访问过的对应的顶点加入队尾中，
重复这个过程，直到队列为空。


继续看一张笔者画的模拟图（不会 PS是硬伤。。。）：



下面给出广度优先遍历的伪代码：




// 宽度优先遍历，n 为图的顶点个数 
void bfs(int n) {
    que.push(0); // 将 V1 顶点入队
    int s;
    while(!que.empty) { // 队列非空的时候继续循环 
        s = que.fornt; // 输出访问的顶点 
        cout << s;
        que.pop; // 队头元素出队列
        for(int i = 0; i < n; i++) { // 对当前顶点的所有边进行讨论 
            if(e[s][i] == 1 && i 顶点未被访问过) {
                que.push(i);
            }
        } 
    }
}


好了，最后给出完整代码




#include <iostream>
#include <queue>
#include <cstring> 
using namespace std;
const int N = 10010; // 图的顶点最大个数
int e[N][N]; // 储存图信息的邻接矩阵 
int book[N]; // 标记顶点是否被访问 

 // 对第 n 个顶点进行深度优先遍历 
void dfs(int n, int sum) {
    if(n != 0) { // 输出格式控制 
        cout << " ";
    }
    cout << n+1; // 输出顶点信息 
    for(int i = 0; i < sum; i++) { // 对当前所有的顶点进行讨论
        // 如果顶点 i 和顶点 n 之间存在边直接相连，并且顶点 i 未被访问 
        if(e[n][i] == 1 && book[i] == 0) {  
            book[i] = 1; // 标记这个顶点已经被访问 
            dfs(i, sum); // 对这个顶点继续进行深度优先遍历 
        }
    }
}

// 对图进行广度优先遍历 
void bfs(int n) {
    queue<int> que;
    book[0] = 1; // 标记第一个顶点已经被访问
    que.push(0);
    int s;
    while(!que.empty()) {
        s = que.front(); // 获取队头元素 
        que.pop(); // 队头元素出队
        if(s != 0) { // 输出格式控制
            cout << " ";
        }
        cout << s+1; // 输出顶点信息 
        for(int i = 0; i < n; i++) {
            // 如果顶点 i 和顶点 n 之间存在边直接相连，并且顶点 i 未被访问 
            if(e[s][i] == 1 && book[i] == 0) {
                book[i] = 1; // 标记这个顶点已经被访问 
                que.push(i); // 这个顶点入队尾 
            }
        } 
    }
}

int main() {
    int n, m; // 图的顶点个数和边的条数 
    cin >> n >> m;
    int x, y; // 边的开始顶点和结束顶点 
    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        e[--x][--y] = e[y][x] = 1; // 因为是无向图，所以要双向储存 
    }

    cout << "深度优先遍历结果：" << endl;
    book[0] = 1; // 标记第一个顶点已经被访问
    dfs(0, n); // 从第一个顶点开始深度优先遍历 

    memset(book, 0, sizeof(book)); // 重置访问标记 
    cout << endl << "广度优先遍历结果：" << endl;
    bfs(n);

    return 0;
}


测试数据和结果：



Good， 和我们模拟得到的结果一样。图的遍历算法是图的基础算法， 也是在很多其他图的算法中经常用得到的算法思想，比如图中两个顶点的最短路，图的最小生成树算法等等。

好了。如果博客中有什么不正确的地方，还请多多指点。如果觉得我写得不错，那么请点个赞支持我吧。

谢谢观看。。。