算法学习笔记

图

概述

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

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

图ADT支持的顶点操作接口

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

最短路径算法

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 ;
}