算法学习笔记

图

概述

1.通路中边依次地首尾相连，其中沿途边的总数m，也称通路的长度

2.对于长度m>=1的通路Π，若起止顶点相同，则称为环路

3.经过图中各边一次且恰好一次的环路，称作欧拉环路（Eulerian tour）
经过图中各顶点一次且恰好一次的环路，称作哈密尔顿环路（Hamiltonian tour）

4.各边均带权重的图，称作带权图（weighted graph）或带权网络（weighted network）

5.对于无向图，每一对顶点至多贡献一条边，故总共不超过n(n-1)/2条边；对于有向图，每一对顶点都可能贡献（互逆的）两条边，因此至多可有n(n-1)条边。
总而言之，必有复杂度为n^2

6.操作接口：

图ADT支持的边操作接口

图ADT支持的顶点操作接口

最短路径算法

template<typename Tv, typename Te> struct DijkstraPu{//针对Dijkstra算法的顶点优先级更新器
    virtual void operator(Graph<Tv, Te> *g, int uk, int v){
        if(g->status(v) == UNDISCOVERED){//对于uk每一尚未被发现的邻接顶点v，按Dijkstra策略
            if(g->priority(v) > g->priority(uk) + g->weight(uk, v)){//做松弛
                g->priority(v) = g->priority(uk) + g->weight(uk, v);//更新优先级数
                g->parent(v) = uk;//并同时更新父节点
            }
        }
    }
}

PAT案例：

void dijk(int c){
    dis[c]=0;//起点到起点的距离为0
    for(int i=0;i<m;i++){//循环n次每次加一个点，每次加入的点都是已更新完成的点
        int v=-1;
        for(int j=0;j<m;j++){
            //每次都遍历所有的点，从没加入图中的点中选一个到原点距离最小的点，加入图中
            if(!vis[j]&&(v==-1||dis[j]<dis[v])){
                v=j;
            }
        }
        vis[v]=1;
        for(int j=0;j<m;j++){//进行松弛操作
            dis[j]=min(dis[j],dis[v]+map[v][j]);
        }
    }
    return ;
}

深度优先搜索（dfs）

以顶点s为基点的DFS搜索，将首先访问顶点s；再从s所有尚未访问到的邻居中任取其一，并以之为基点，递归地执行DFS搜索。

template <typename Tv, typename Te> //深度优先搜索DFS算法（全图）
void Graph<Tv, Te>::dfs ( int s ) { //assert: 0 <= s < n
    reset(); int clock = 0; int v = s; //初始化
    do //逐一检查所有顶点
       if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点
         DFS ( v, clock ); //即从该顶点出发启动一次DFS
    while ( s != ( v = ( ++v % n ) ) ); //按序号检查，故不漏不重
}

template <typename Tv, typename Te> //深度优先搜索DFS算法（单个连通域）
void Graph<Tv, Te>::DFS ( int v, int& clock ) { //assert: 0 <= v < n
    dTime ( v ) = ++clock; status ( v ) = DISCOVERED; //发现当前顶点v
    for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u
       switch ( status ( u ) ) { //并视其状态分别处理
          case UNDISCOVERED: //u尚未发现，意味着支撑树可在此拓展
             type ( v, u ) = TREE; parent ( u ) = v; DFS ( u, clock ); break;
          case DISCOVERED: //u已被发现但尚未访问完毕，应属被后代指向的祖先
             type ( v, u ) = BACKWARD; break;
          default: //u已访问完毕（VISITED，有向图），则视承袭关系分为前向边或跨边
             type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS; break;
       }
    status ( v ) = VISITED; fTime ( v ) = ++clock; //至此，当前

PAT案例：

void dfs(int a){
    visit[a] = 1;
    for(int i = 1; i <= n; i++){
        if(visit[i] == 0 && maps[a][i] == 1){
            dfs(i);
        }
    }
    return ;
}

二叉树

概述

1.沿每个节点v到根r的唯一通路所经过边的数目，称作v的深度，记作depth(v)

2.v的孩子总数，称作其度数或度(degree)，记作deg(v)。无孩子的节点称作叶节点(leaf)，包括根在内的其余节点皆为内部节点(internal node)。

3.v的所有后代及其之间的联边称作子树，记作subtree(v)

4.树T中所有节点深度的最大值称作该树的高度(height)，记作height(T)

5.二叉树(binary tree)中每个节点的度数均不超过2
不含一度节点的二叉树称作真二叉树(proper binary tree)

6.完全二叉树的根节点序号为n,则其左右结点序号为2n和2n+1

二叉搜索树

1.顺序性：任一节点r的左（右）子树中，所有节点（若存在）均不大于（不小于）r

2.中序遍历序列：
二叉搜索树的中序遍历序列，必然单调非降
任何一棵二叉树是二叉搜索树，当且仅当其中序遍历序列单调非降

3.查找算法：
从根节点开始，逐步地缩小查找范围，直到发现目标（成功）或缩小至空树，依照右子树元素不小于根节点，左子树元素不大于根节点的原则层层缩小即可