史上最全数图算法笔记

快来打我* 2021-11-16 22:58 304阅读 0赞

## 图 ##

**概述**

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支持的边操作接口

<table> 
 <thead> 
  <tr> 
   <th>操作接口</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>e(u)</td> 
   <td>边总数E</td> 
  </tr> 
  <tr> 
   <td>exist(v,u)</td> 
   <td>判断联边(v,u)是否存在</td> 
  </tr> 
  <tr> 
   <td>insert(v,u)</td> 
   <td>引入从顶点v到u的联边</td> 
  </tr> 
  <tr> 
   <td>remove(v,u)</td> 
   <td>删除从顶点v到u的联边</td> 
  </tr> 
  <tr> 
   <td>type(v,u)</td> 
   <td>边在遍历树中所属的类型</td> 
  </tr> 
  <tr> 
   <td>edge(v,u)</td> 
   <td>边所对应的数据域</td> 
  </tr> 
  <tr> 
   <td>weight(v,u)</td> 
   <td>边的权重</td> 
  </tr> 
 </tbody> 
</table>

图ADT支持的顶点操作接口

<table> 
 <thead> 
  <tr> 
   <th>操作接口</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>n()</td> 
   <td>顶点总数n</td> 
  </tr> 
  <tr> 
   <td>insert(v)</td> 
   <td>在顶点集v中插入新顶点v</td> 
  </tr> 
  <tr> 
   <td>remove(v)</td> 
   <td>将顶点v从顶点集中删除</td> 
  </tr> 
  <tr> 
   <td>inDegree(v) outDegree(v)</td> 
   <td>顶点v的入度，出度</td> 
  </tr> 
  <tr> 
   <td>firstNbr(v)</td> 
   <td>顶点vde首个邻接顶点</td> 
  </tr> 
  <tr> 
   <td>nextNbr(v,u)</td> 
   <td>在v的邻接顶点中，u的后继</td> 
  </tr> 
  <tr> 
   <td>status(v)</td> 
   <td>顶点v的状态</td> 
  </tr> 
  <tr> 
   <td>dTime(v),fTime(v)</td> 
   <td>顶点v的时间标签</td> 
  </tr> 
  <tr> 
   <td>parent(v)</td> 
   <td>顶点v在遍历树中的父节点</td> 
  </tr> 
  <tr> 
   <td>priority(v)</td> 
   <td>顶点v在遍历树中的权重</td> 
  </tr> 
 </tbody> 
</table>

**最短路径算法**

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,则其左右结点序号为2*n和2*n+1

**二叉搜索树**

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

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

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