【数据结构】图

目录

线性表可以是空表，树可以是空树，但图G(Graph)不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V(Vertex)一定非空，但边集E(Edge)可以为空，此时图中只有顶点而没有边。

  • 若一个图有n个顶点，并且边数小于n-1，则此图一定是非连通图。
  • 若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

基本概念

  • 简单图：
    • 不存在重复的边
    • 不存在顶点到自身的边
  • 完全图（简单完全图）：
    • 在无向图中，任意两个顶点之间都存在边。
    • 含有n个顶点的无向完全图有n(n-1)/2条边。
    • 在有向图中，任意两个顶点之间都存在反向相反的两条弧。
    • 含有n个顶点的有向完全图有n(n-1)条有向边。
  • 子图：
    • 由V的子集和E的子集组合而成的图G'。
    • 若有满足V(G')=V(G)（即顶点集相同）的子图G'，则称其为G的生成子图。(详情参照生成树)

并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中（单有一条边，两边可能没顶点）。

  • 连通图和连通分量：
    • 在无向图中任意两点都是连通的，那么图被称作连通图。
    • 无向图中的极大连通子图称为连通分量。
    • 如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。

    • 有向图中的极大强连通子图称为有向图的强连通分量。

      若一个图有n个顶点，并且边数小于n-1，则此图一定是非连通图。

  • 生成树、生成森林：
    • 连通图的生成树是包含图中全部结点的一个极小连通子图。
    • 若图中顶点数为n，则它的生成树含有n-1条边。
    • 对于生成树而言，若砍去它的一条边，则会变成非连通图；若加上一条边，则会形成一个回路。

    • 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

      包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

  • 顶点的度：
    • 对于无向图，顶点v的度是指依附于该顶点的边的条数，记为TD(v)。(Total Degree)
    • 在具有n个顶点、e条边的无向图中，无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。
    • 对于有向图，顶点的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为ID(v)，即(In Degree)；而出度是以顶点v为起点的有向边的数目，记为OD(v)，即(Out Degree)。顶点v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)。
  • 网：边上带有权值的图，称为带权图，也称为网。
  • 回路(环)：
    • 第一个顶点和最后一个顶点相同的路径称为回路或环。
    • 若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

注意：有回路的图不一定是连通图，因为回路不一定包含图的所有结点。

  • 简单路径、简单回路：
    • 在路径序列中，顶点不重复出现的路径，称为简单路径。
    • 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路。

无向图

  • 连通图：
    在无向图中，若从定点V1到V2有路径，则称顶点V1和V2是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。（连通的无向图）

  • 极大连通子图：包含该连通子图中所有的边（当连通时包含了所有的边，当然也包含了所有的点）
    • 连通图只有一个极大连通子图，就是它本身。（是唯一的）
    • 非连通图有多个极大连通子图。（非连通图的极大连通子图叫做连通分量，每个分量都是一个连通图）
    • 称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。
      下图为非连通图，图中有两个极大连通子图（连通分量）。

  • 极小连通子图：包含该无向连通图中所有的顶点，最少的边（即 包含图中所有顶点及其比顶点数量少一个的边（且不能成环））（只存在于连通的无向图中）

    注意：极小连通子图只存在于连通的无向图中，不存在于不连通的无向图和有向图中。

    • 一个连通图的生成树是该连通图的的极小连通子图。（同一个连通图可以有不同的生成树，所以生成树不是唯一的）
      （极小连通子图只存在于连通图中）
    • 用边把极小连通子图中所有节点给连起来，若有n个节点，则有n-1条边。如下图生成树有6个节点，有5条边。
    • 之所以称为极小是因为此时如果删除一条边，就无法构成生成树，也就是说给极小连通子图的每个边都是不可少的。
    • 如果在生成树上添加一条边，一定会构成一个环。
    • 也就是说只要能连通图的所有顶点而又不产生回路的任何子图都是它的生成树。

极大即要求改连通子图包含其所有的边；极小连通子图是既要保持图的连通又要使得边数最少的子图。

极大即加入任何一个不在图的点集中的点都会导致它不再连通。
极小是因为此时如果删除一条边，就导致不再连通，加上一条边，则会形成图中的一条回路。

总的来说：极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的。

有向图

  • 强连通图：
    在有向图中，若对于每一对顶点Vi和Vj，都存在一条从Vi到Vj和从Vj到Vi的路径，则称此图为强连通图。（连通的有向图）

  • 有n个顶点的强连通图最多有n(n-1)条边，最少有n条边(即环）。（4个顶点的强连通图图示如上图和下图）

  • 极大强连通子图：
  1. 强连通图的极大强连通子图为其本身。（是唯一的）
  2. 非强连通图有多个极大强连通子图。（有向图的极大强连通子图叫做强连通分量）
  • 极小强连通子图：不存在这个概念（因为极小是生成树，而有向图的强连通有两条边，不构成生成树）

图的存储及基本操作

  • 十字有向，多重无向。

    助记：（十字准星，就代表有目标了，即 有向）

  • 是有多污：十有多无

邻接矩阵法

  • 基本概念：
    所谓邻接矩阵存储，是指用一个以为数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。

邻接矩阵是一种图的顺序存储结构。

  • 存储结构：
#define MaxVertexNum 100    //顶点数目的最大值
typedef char VertexType;    //顶点的数据类型
typedef int EdgeType;       //带权图中边上权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum];   //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵，边表
    int vexnum, arcnum;     //图的当前顶点数和弧数
}MGraph;    //Matrix Graph(矩阵图)
  • 特点：行列出入（度）
    1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。
    2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度(TD(v_i))。
    3. 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度(OD(v_i))（或入度(ID(v_i))）。
    4. 设图G的邻接矩阵为A，(A^n)的元素(A^n[i][j])等于由顶点i到顶点j的长度为n的路径的数目。
    5. 空间复杂度为O((n^2))，其中n为图的顶点数(|V|)。
    6. 稠密图适合使用邻接矩阵的存储表示。
  • 优点：
    1. 方便检查任意一对顶点间是否存在边。
    2. 方便找任意顶点的所有“邻接点”（有边直接相连的顶点）
    3. 方便计算任意顶点的“度”（从该点出发的边数为“出度”，指向该点的边数为“入度”）
      • 无向图：对应行（或列）非零元素的个数；
      • 有向图：对应行非零元素的个数是“出度”，对应列非零元素的个数是“出度”。
  • 缺点：
    要确定图中有多少边，则必须按行、按列队每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

邻接表法

G[N]为指针数组，对应矩阵每行一个链表，只存非零元素。

  • 基本概念：
    所谓邻接表，是指对图G中的每个顶点(v_i)建立一个单链表，第i个单链表中的结点表示依附于顶点(v_i)的边（对于有向图则是以顶点(v_i)为尾的弧），这个单链表就称为顶点(v_i)的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。
    • 顶点表结点：由顶点域(data)和指向第一条邻接边的指针(firstarc)(弧(Arc))构成。
    • 边表结点：由邻接点域(adjvex)(Adjacency vertex)和指向下一条邻接边的指针域(nextarc)构成。
  • 存储结构：（当然，序号也可以从1开始）
    • 顶点表：
    data firstarc
    顶点域 边表头指针
    顶点信息 指向第一条邻接边的指针
    • 边表：
    adjvex nextarc
    邻接点域 指针域
    该弧所指向的顶点的位置 指向下一条邻接边的指针 
#define MaxVertexNum 100    //图中顶点数目的最大值
typedef struct ArcNode {    //边表结点
    int adjvex;             //该弧所指向的顶点的位置
    struct ArcNode *next;   //指向下一条弧的指针
    //InfoType info;        //网的边权值
}ArcNode;
typedef struct VNode {      //顶点表结点
    VertexType data;        //顶点信息
    ArcNode *first;         //指向第一条依附该结点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices;       //邻接表(顶点表)
    int vexnum, arcnum;     //图的顶点数和弧数
}ALGraph;                   //Adjacency List Graph是以邻接表存储的图的类型
  • 特点：
    1. 若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
    2. 对于稀疏图，采用邻接表表示将极大地节省存储空间。（稠密图不一定，因为每个结点都不止只有一个data域，还存储了下一指针）
    3. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。
  • 优点：
    1. 方便找任一顶点的所有“邻接点”
    2. 节约稀疏图的空间
      • 需要N个头指针 + 2E个结点（每个结点至少2个域）
    3. 计算任一顶点的“度”
      • 对无向图来说，很方便
      • 对有向图来说，只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）（即 存矩阵的每一列）来方便计算“入度”
    4. 给定一顶点，很容易找出它的所有邻边
  • 缺点：
    若要确定给定的两个顶点间是否存在边，则需要在相应结点对应的边表中查找另一结点，效率低。

十字链表

将邻接表和逆邻接表合并而成的链接表。

  • 基本概念：
    十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

  • 存储结构：
    • 弧结点：
    tailvex headvex hlink tlink info
    尾域 头域 头链域 尾链域 相关信息
    指向弧尾顶点在图中的位置 指向弧头顶点在图中的位置 指向弧头相同的下一条弧 指向弧尾相同的下一条弧 指向该弧的相关信息
    • 顶点结点：
    data firstin firstout
    存放顶点相关的数据信息 指向以该顶点为弧头的第一个弧结点 指向以该顶点为弧尾的第一个弧结点

注意，顶点结点之间是顺序存储的。

  • 特点：
    图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。

  • 优点：
    1. 既容易找到vi为尾的弧，又容易找到vi为头的弧
    2. 容易求得顶点的出度和入度

邻接多重表

  • 基本概念：
    邻接多重表是无向图的另一种链式存储结构。
    每条边用一个结点表示，每个顶点也用一个结点表示。
  • 存储结构：
    • 边结点：
    mark ivex ilink jvex jlink info
    标志域，可用于标记该边是否被搜索过 指向该边依附的其中一个顶点位置 指向下一条依附于顶点ivex的边 指向该边依附的另一个顶点位置 指向下一条依附于顶点jvex的边 指向和边相关的各种信息的指针域
    • 顶点结点：
    data firstedge
    存储该顶点的相关信息 指向第一条依附于该顶点的边

PS:由于十字链表与邻接多重表比较少见，所以详情请各位读者自行了解。

转换算法

邻接表转换为邻接矩阵

  • 算法思想：
    设图的顶点分别设在V[n]数组中。首先初始化邻接矩阵。遍历邻接表，在依次遍历顶点V[i]的边链表，修改邻接矩阵的第i行的元素值。若链表边结点的值为j，则置arcs[i][j]=1。遍历完整个邻接表时，整个转换过程结束。此算法对无向图，有向图均适用。
void Convert(ALGraph &G, int arcs[M][N]){
//此算法是将邻接表方式表示的图G转换为邻接矩阵arcs
    for(int i=0; i<n; i++){         //依次遍历各顶点表结点为头的边链表
        p=（G->v[i].firstarc）;       //取出顶点i的第一条出边
        while(p!=null){             //遍历边链表
            arcs[i][p->data]=1;
            p=p->nextarc;           //取下一条出边
        }
    }
}

邻接矩阵转换为邻接表

void MatToList(AdjMatrix &A, AdjList &B) {
    B.vertexNum = A.vertexNum;
    B.arcNum = A.arcNum;
    for(i=0; i<A.vertexNum; i++) {
        B.adjlist[i].firstedge = NULL;
    }
    for(i=0; i<A.vertexNum; i++) {
        for(j=0; j<i; j++) {
            if(A.arc[i][j] != 0) {
                p = new ArcNode;
                p->adjvex = j;
                p->next = B.adjlist[i].firstedge;
                B.adjlist[i].firstedge = p;
            }
        }
    }
}

图的遍历

图的遍历主要有两种算法：广度优先搜索和深度优先搜索，都可以抽象为优先级搜索或最佳优先搜索。
广度优先搜索会优先考虑最早被发现的结点，也就是说离起点越近的结点其优先级越高。
深度优先搜索会优先考虑最后被发现的结点。

广度优先算法由Edward F. Moore在向右迷宫路径问题时发现；
深度优先搜索在20世纪50年代晚期获得广泛使用，尤其在人工智能方面。

画深度优先或广度优先生成树的图时，需要注意，当存储结构固定时，生成树的树形也就固定了。要按存储结构排列的先后顺序先后访问。

广度优先搜索(BFS)

  • 基本概念：
    广度优先搜索(Breadth-First-Search, BFS)类似于二叉树的层次遍历算法。

  • 操作过程：
    首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点(w_1, w_2, ..., w_i)，然后依次访问(w_1, w_2, ..., w_i)的所有未被访问过的邻接顶点；再从这些访问过顶点出发，访问它们所有未被访问过的顶点……依次类推，直到图中所有顶点都被访问过为止。

Dijkstra单源最短路径算法和Prim最小生成树算法也应用了类似的思想。

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

  • 具体实现：
//广度优先搜索（Breadth-First-Search,BFS）
bool visited[MAX_VERTEX_NUM);   //访问标记数组

void BFS(Graph G,int v){        //从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
    Enqueue(Q,v);               //顶点v入队列
    visited[v]=TRUE;            //对v做（已入队待访问）标志
    while(!isEmpty(Q)){
        DeQueue(Q,v);           //顶点v出队列
        visit(v);               //访问顶点v
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) {    //检测v所有邻接点
            if(!visited[w]){    //w为v的尚未访问的邻接顶点
                visited[w]=TRUE;//对w做（已入队待访问）标记
                EnQueue(Q,w);   //顶点w入队列
            }
        }
    }
}

void BFSTraverse(Graph G){      //对图G进行广度优先遍历，设访问函数为visit()
    for(i=0;i<G.vexnum;i++) {
        visited[i]=FALSE;       //访问标志数组初始化
    }
    InitQueue(Q);               //初始化辅助队列Q
    for(i=0;i<G.vexnum;i++) {   //从0号顶点开始遍历
        if(!visited[i]) {       //对每个连通分量开始遍历（以免不连通）
            BFS(G,i);           //v[i]未访问过，从v[i]开始BFS
        }
    }
}
  • 注意：对于for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) { //检测v所有邻接点，不同存储结构有不同的写法。

用邻接表作存储结构的BFS

void BFSTraverse(ALGraph &G) {
    int queue[maxsize];
    int front = -1, rear = -1
    int i=0;
    for(i=0; i<G.vexnum; i++) { //初始化访问状态
        visited[i] = 0;
    }
    
    //遍历其所有邻接点
    i = 0;  //将第一个结点入队
    queue[++rear] = i;  //队内结点都是要访问的，所以一入队就修改其访问状态
    visited[i] = 1;
    while(front < rear) {
        i = queue[++front];     //出队
        visit(i);   //访问
        
        //将其所有邻接结点入队(待访问)
        ArcNode *p = G->vertices[i].firstarc;
        while(p) {
            if(!visited[p->adjvex]) {   //顶点i的邻接点没有被访问过，则入队（待访问），设置访问状态
                visited[p->adjvex] = 1; //设置（已入队待访问）标记
                queue[++rear] = p->adjvex;  //入队
            }
            p = p->next;    //访问下一个邻接点
        }
    }
}

用邻接矩阵作存储结构的BFS

void BFSTraverse(int arcs[M][N]) {
    int queue[maxsize];
    int front = -1, rear = -1
    int i=0;
    for(i=0; i<n; i++) {    //初始化访问状态
        visited[i] = 0;
    }
    
    //遍历其所有邻接点
    i = 0;  //将第一个结点入队
    queue[++rear] = i;  //队内结点都是要访问的，所以一入队就修改其访问状态
    visited[i] = 1;
    while(front < rear) {
        i = queue[++front];     //出队
        visit(i);   //访问
        
        //将其所有邻接结点入队(待访问)
        for(int j=0; j<n; j++) {
            if(arcs[i][j]!=0 && !visited[j]) {  //若i、j之间存在弧，且j未被访问过（即i的邻接点j）
                visited[j] = 1;
                queue[++rear] = j;
            }
        }
    }
}
  • 性能分析：

    • 空间效率：O(|V|)
      无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|V|)。

    • 时间效率：
      • 邻接表：O(|V|+|E|)（其实就相当于把邻接表整个扫描了一遍）
        采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，所以算法中的复杂度为O(|V|+|E|)。
      • 邻接矩阵：(O(|V|^2))（其实就相当于把邻接矩阵整个扫描了一遍）
        采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为(O(|V|^2))。

    • 适用性：
      适合在不断扩大遍历范围时找到相对最优解的情况。

  • 求解单源最短路径问题：

    若图为无权图，利用BFS算法的特性：一层一层的遍历，可以求出某一个顶点到其他顶点的最短路径。（这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的）

//BFS算法求解单源最短路径问题的算法：
void BFS_MIN_Distance(Graph G,int u){   //dist[i]表示从u到i结点的最短距离，path[w]代表w在路径上的前一个顶点
    for(i=0;i<G.vexnum;i++)
        dist[i]=INF;        //初始化路径长度为无穷(infinite)
    //visited[u]=TRUE;
    dist[u]=0;
    EnQueue(Q,u);
    while(!isEmpty(Q)){     //BFS算法主过程
        DeQueue(Q,u);       //队头元素u出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)) {  //对于u的每个邻接顶点w
            if(dist[w] == -1){      //w为u的尚未访问的邻接结点
                dist[w]=dist[u] + 1;    //路径长度加1
                path[w] = u;        //到w路径上经过的最后一个顶点u(即w的前一个顶点u)
                EnQueue(Q,w);
            }
        }
    }

T = O(|V|+|E|)
利用path一次次的寻找前一个结点，就可找到路径。

  • 广度优先生成树：
    在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。需要注意的是，一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

深度优先搜索(DFS)

  • 基本概念：
    与广度优先搜索不同，深度优先搜索(Depth-First-Search, DFS)类似于树的先序遍历。正如它的名字，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。

  • 操作过程：
    首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点(w_1)，再访问与(w_1)邻接且未被访问的任一顶点(w_2)……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的结点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，知道图中所有顶点均被访问过为止。

  • 具体实现：

递归实现

//深度优先搜索（Depth-First-Search,DFS）
bool visited[MAX_VERTEX_NUM];   //访问标记数组

void DFS(Graph G,int v){        //从顶点v出发，采用递归思想，深度优先遍历图G
    //遍历访问完所有结点就出去了，所以无需递归出口
    visit(v);                   //访问顶点v
    visited[v]=TRUE;            //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) {
        if(!visited[w]){        //w为u的尚未访问的邻接顶点
            DFS(G,w);
        }
    }
}

void DFSTraverse(Graph G){      //对图G进行尝试优先遍历，访问函数为visit()
    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);
        }
    }
}

非递归实现

在深度优先搜索的非递归算法中使用了一个栈S来记忆下一步可能访问的结点，同时使用了一个访问标记数组visited[i]来记忆第i个结点是否在栈内或曾经在栈内，若是则它以后不能再进栈。

void DFS_Non_RC(ALGraph &G, int v) {
//从顶点v开始进行深度优先搜索，一次遍历一个连通分量的所有顶点
    int w;      //顶点序号
    InitStack(S);   //初始化栈S
    for(i=0; i<G.vexnum; i++) {
        visited[i] = FALSE; //初始化visited
    }
    Push(S, v);     //v入栈并置visited[v]
    visited[v] = TRUE;
    while(!IsEmpty(S)) {
        k = Pop(S); //栈中退出一个顶点
        visit(k);   //先访问，再将其子结点入栈
        for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)) {  //k所有邻接点
            if(!visited[w]) {   //未进过栈的顶点进栈
                Push(S, w);
                visited[w] = TRUE;  //做标记，以免再次入栈
            }
        }
    }
}

注意：由于使用了栈，使得遍历方式从右端到左端进行，不同于常规的从左端到右端，但仍然是深度优先遍历。

  • 注意：对于for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) { //检测v所有邻接点，不同存储结构有不同的写法。

用邻接表作存储结构的DFS

void DFSTraverse(ALGraph &G, int v) {
    visit(v);       //访问顶点v
    visited[v] = 1; //设已访问标记
    
    //遍历其任一邻接点
    ArcNode *p = G->vertices[v].firstarc;
    while(p) {
        if(!visited[p->adjvex]) {   //若顶点i的邻接点没有被访问过，则DFS
            DFSTraverse(G, p->adjvex);  //遍历其邻接点
        }
        p = p->next;    //访问下一个邻接点
    }
}

用邻接矩阵作存储结构的DFS

void DFSTraverse(int arcs[M][N], int v) {
    visit(v);       //访问顶点v
    visited[v] = 1; //设已访问标记
    
    //遍历其任一邻接点
    for(int w=0; w<n; w++) {
        if(arcs[v][w]!=0 && !visited[w]) {  //若v、w之间存在弧，且w未被访问过（即v的邻接点w）
            DFSTraverse(arcs[M][N], w);
        }
    }
}
  • 性能分析：

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

    • 时间效率：
      • 邻接表：O(|V|+|E|)（其实就相当于把邻接表整个扫描了一遍）
        采用邻接表存储方式时，查找所有顶点的邻接点所需时间为O(|E|)，访问顶点所需的时间为O(|V|)，此时总的时间复杂度为O(|V|+|E|)。
      • 邻接矩阵：(O(|V|^2))（其实就相当于把邻接矩阵整个扫描了一遍）
        采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为(O(|V|^2))。

    • 适用性：
      适合目标比较明确，以找到目标为目的的情况。

  • 深度优先的生成树和生成森林
    与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林。与BFS类似，其基于邻接表存储的深度优先生成树也是不唯一的。

图的连通性

图的遍历算法可以用来判断图的连通性。

  • 无向图：
    • 连通：
      从任一结点出发，仅需一次遍历就能够访问图中的所有顶点。

    • 非连通：
      从某个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。

      上述两个函数调用BFS(G,i)或DFS(G,i)的次数等于该图的连通分量数。

for(v=0;v<G.vexnum;v++) {
    if(visited[v]!=TRUE) {  //如果一次遍历未能访问所有结点，则该图不连通
        return false;   //图不连通
    }
}

  • 有向图：
    若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。

    而有向图的调用次数则不等于连通分量数，因为一个连通的有向图分为强连通和非强连通，它的连通子图也分为强连通分量和非强连通分量，非强连通分量一次调用BFS或DFS无法访问到该非强连通分量的所有顶点（但是图却是连通的）。

    • 强连通分量数：
      当某个顶点只有出弧而没有入弧时，其他顶点无法到达这个顶点，不可能与其他顶点和边构成强连通分量（这个单独的顶点单独构成一个强连通分量）（其实这个方法有点像拓扑排序）
      • 顶点1无入弧构成一个强连通分量。删除顶点1及所有以之为尾的弧。。。

注意：故在BFSTraverser()或DFSTraverse()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点（即 非连通图）。

图的应用

最小生成树(MST)

仅针对无向图

一个连通图的生成树是图的最小连通子图，它包含图中的所有顶点，并且只含尽可能少的边。则意味着对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

边的权值之和最小的那颗生成树，则称为最小生成树(Minimum-Spanning-Tree, MST)。

  • 性质
    1. 是一棵树
      • 无回路
      • |V|个顶点一定有|V|-1条边
    2. 是生成树
      • 包含全部顶点
      • |V|-1条边都在图里
    3. 边的权重和最小
  • 特点：
    1. 最小生成树不是唯一的，即最小生成树的树形不唯一，图中可能有多个最小生成树。
    2. 当图中的各边权值互不相等时，图的最小生成树是唯一的。
    3. 当带权连通图的任意一个环中所包含的边的权值均不相同时，其最小生成树是唯一的。
    4. 若图本身是一棵树时，则图的最小生成树就是它本身。
    5. 最小生成树的边的权值之和总是唯一的。
    6. 最小生成树的边数为顶点数-1。

下列算法都是基于贪心算法。

Prim(普里姆)算法

此算法可以称为”加点法“

其实本质上来说，是“让一棵小树长大”。

记忆：让小树破(P)土而出，长大，加点。

  • 基本思想：
    在伪最小生成树(未完成)的所有顶点与图中其余顶点相连接的边中，找出距离生成树权值最小的边，加入，重复操作，构成最小生成树。

  • 实现步骤：
    • 初始化：向空树(T=(V_T,E_T))中添加图(G=(V,E))的任一顶点(u_0)，使(V_T={u_0})，(E_T=∅)。
    • 循环（重复下列操作至(V_T=V)）：从图G中选择满足({(u,v)|u∈V_T,v∈V-V_T})且具有最小权值的边((u,v))，并置(V_T=V_T∪{v})，(E_T=E_T∪{(u,v)})。
  • 通俗说明：
    此算法可以称为”加点法“，每次迭代选择代价最小的边对应的点，加入到最小生成树中。
    算法从某一顶点s开始，逐渐长达覆盖整个连通网的所有顶点。
    1. 图的所有顶点集合为V；初始令集合u={s},v=V−u;
    2. 在两个集合u，v能过够组成的边中，选择一条代价最小的边((u_0，v_0))，加入到最小生成树中，并把v0并入到集合u中。
    3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

  • 简单实现：
void Prim(G, T) {   //图G = (V,E) 树T = (T,U)
    //初始化树
    T = ∅；      //存放树的边
    U = {w};    //存放树的顶点，添加任一顶点w
    while((V-U) != ∅) {     //若树中不含全部顶点
        设(u, v)是使u∈U与v∈(V-U)，且权值最小的边;   //即u为树中顶点，v为图中顶点，(u,v)为未完成树与图相连接的一条权值最小的边
        T = T∪{(u, v)}; //边归入树
        U = U∪{v};          //顶点归入树
    }
}
  • 性能分析：

    • 时间效率：O((|V^2|))
      Prim算法时间复杂度为O((|V^2|))，不依赖于|E|。

    • 适用性：
      适用于求解边稠密的图的最小生成树。

Kruskal(克鲁斯卡尔)算法

此算法可以称为“加边法”

其实本质上来说，是“将森林合并成树”。

记忆：把森林砍(K)成一颗树，合并成树，加边。

  • 基本思想：
    在整个图中找权值最小的边，不构成回路的情况下加入(连接两棵不同的树，合并为一棵)，重复操作，拼接成最小生成树。

  • 实现步骤：
    • 初始化：(V_T=V)，(E_T=∅)。即每个顶点构成一棵独立的树，T此时是一个仅含|V|个顶点的森林。
    • 循环（重复下列操作至T是一棵树）：按G的边的权值递增排序依次从(E-E_T)中选择一条边，若这条边加入T后不构成回路，则将其加入(E_T)，否则舍弃，直到(E_T)中含有n-1条边。
  • 通俗说明：
    此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
    1. 把图中的所有边按代价从小到大排序；
    2. 把图中的n个顶点看成独立的n棵树组成的森林；
    3. 按权值从小到大选择边，所选的边连接的两个顶点(u_i),(v_i)，(u_i),(v_i),应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
    4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

  • 简单实现：
void Kruskal(V,T) {
    T = V;      //初始化树T，仅含顶点
    numS = n;   //连通分量数
    while(numS > 1) {   //若连通分量数大于1
        从E中取出权值最小的边(v,u);       //利用最小堆
        if(v和u属于T中不同的连通分量) {        //即 不构成回路   （利用并查集）
            T = T∪{(v,u)};      //将此边加入生成树中
            numS--;     //连通分量数减1
        }
    }
}
  • 性能分析：

    • 时间效率：O((|E|log|E|))
      通常在Kruskal算法中，采用堆来存放边的集合，因此每次选择最小权值的边只需O(log|E|)的时间。此外，由于生成树T中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述T，从而构造T的时间复杂度为O(|E|log|E|)。

    • 适用性：
      适用于边稀疏而顶点较多的图。

最短路径

针对有向图和无向图

带权图中，从一个顶点到其余任意一个顶点的一条路径的带权路径长度最短的那条路径称为最短路径。
带权有向图G的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一固定源点出发到其他各顶点的最短路径，可通过经典的Dijkstra算法求解；二是求多源最短路径，即求图中任意两顶点间的最短路径，可通过Floyd算法来求解。

Dijkstra(迪杰斯特拉)算法

该算法要求图中不存在负权边。

  • 基本思想：
    在伪最短路径(未完成)的所有顶点与图中其余顶点相连接的边，并取出距离源点(v_0)权值最小的边，加入最短路径，重复操作，构成最短路径。

可以看出Dijkstra算法与Prim算法极为相似，不过两者的不同之处在于对“权值最低”的定义不同，
Prim的“权值最低”是相对于U中的任意一点而言的，也就是把U中的点看成一个整体，每次寻找V-U中跟U的距离最小（也就是跟U中任意一点的距离最小）的一点加入U；
而Dijkstra的“权值最低”是相对于(v_0)而言的，也就是每次寻找V-U中跟(v_0)的距离最小的一点加入U。

  • 算法特性：

    • 每加入一个顶点，都保证了此顶点dist值是该路径中的最小长度（但可能不是最终整个图的最短路径长度），直到顶点扩充到拥有最短路径中的所有顶点，那么dist值才是最终的最短路径长度。

    • 每加入一个顶点v，影响的是它自己一圈邻接点的dist值。

  • 求解过程：

    顶点 第1轮 第2轮 第3轮 第4轮
    2 10
    v1->v2    		 8
    v1->v5->v2    		 8
    v1->v5->v2
    3 ∞ 14
    v1->v5->v3    		 13
    v1->v5->v4->v3    		 9
    v1->v5->v2->v3
    4 ∞ 7
    v1->v5->v4
    5 5
    v1->v5
    集合S {1,5} {1,5,4} {1,5,4,2} {1,5,4,2,3}
  • 简单实现：
void Dijkstra(Graph G) {
    while(1) {
        V = 未收录顶点中dist最小者;
        if(这样的V不存在) {
            break;
        }
        collected[V] = true;
        for(V的每个邻接点W) {
            if(collected[W] == false) {
                if(dist[V] + E<V,W> < dist[W]) {        //E<V,W>为v到w那条弧的权值
                    dist[W] = dist[V] + E<V,W>;
                    path[w] = V;    //path[w]代表w在路径上的前一个顶点，利用path一次次的寻找前一个结点，就可找到路径。
                }
            }
        }
    }
}
  • 性能分析：
    • 时间效率：
      • 邻接矩阵：(O(|V|^2))
        采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为(O(|V|^2))。
      • 带权的邻接表：(O(|V|^2))
        虽然修改dist[]的时间可以减少，但由于在dist[]中选择最小分量的时间不变（选V轮最小，每次比较V个），故时间复杂度仍为(O(|V|^2))。
    • 适用性：
      适用于不存在负权边的图。
      适用于稀疏图。

Floyd-Warshall(弗洛伊德)算法

又称为“插点法”，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法

该算法允许存在负权边，但不可存在负权回路（即 环上所有权值之和是负数）（因为负权回路不存在最短路径）（转一圈就比原来小，一直转一直爽）。

  • 基本思想：
    初始化，以后逐步尝试在原路径上加入顶点k(k=0,1,...,n-1)作为中间顶点；若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。

  • 实现步骤：

    (A^{(k)}[i][j])表示从顶点(v_i)到顶点(v_j)的路径长度，k表示绕行k个顶点的运算步骤。
    即 (A^{(k)}[i][j]) = 路径{i→{l≤k}→j}的最小长度，即 从顶点(v_i)到(v_j)中间顶点序号不大于k的最短路径长度。

    1. 定义一个n阶方阵序列(A^{(-1)}),(A^{(0)}),...,(A^{(n-1)})
    2. 起始(A^{(-1)}[i][j]) = arcs[i][j]； //arcs表示弧的权值
    3. (A^{(k)}[i][j]) = Min{(A^{(k-1)}[i][j]), (A^{(k-1)}[i][k]) + (A^{(k-1)}[k][j])}, k=0,1,...,n-1 (即最短路径取 加入中间顶点k 或 不加入k 的最小长度)
    4. Floyd算法是一个迭代的过程，每迭代一次，在从顶点(v_i)到(v_j)的最短路径上就多考虑了一个顶点(考虑但不一定会取它)，经过n次迭代后，所得到的(A^{(n-1)}[i][j])(即 已经考虑了其他n-1个顶点后)就是从顶点(v_i)到(v_j)的最短路径长度，即方阵(A^{(n-1)})中就保存了任意一对顶点之间的最短路径长度。
  • 矩阵含义：
    • Dist矩阵：保存图中由顶点i到顶点j的当前最短距离
    • Path矩阵：保存图中由顶点i到顶点j的当前最短路径上顶点j的前驱（这样依次向前找能找到整条最短路径）

  • 矩阵的计算：

    本文应用了十字交叉法，三条线：①主对角线 ②每次沿着主对角线元素画十字（主对角线上都是结点到本身的距离0，每画一个十字都代表加入了该中间结点）。
    每加入一个中间结点i，按该点行、列找到元素位置，画十字，十字（与主对角线）上的元素不会改变（因为十字上的节点与该节点相邻，距离不会发生改变），故只用判断十字（与主对角线）之外的元素是否发生改变，大大减少了判断量。

    • 给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点

    • 相应计算方法如下：


    • 最后A3即为所求结果

  • 简单实现：
void Floyd() {
    for(i=0; i<N; i++) {    //初始化
        for(j=0; j<N; j++) {
            A[i][j] = G[i][j];
            path[i][j] = -1
        }
    }
    //算法
    for(k=0; k<N; k++) {    //依次加入n个中间顶点
        for(i=0; i<N; i++) {    //从每个顶点开始
            for(j=0; j<N; j++) {    //到每个顶点结束（考虑了有向图）
                if(A[i][k] + A[k][j] < D[i][j]) {   //加入了中间顶点k，权值更小
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;     //path[i][j]代表顶点i到顶点j经过了path[i][j]记录值所表示的顶点，利用path一次次的寻找前一个结点，就可找到路径。
                }
            }
        }
    }
}
  • 性能分析：

    • 时间效率：(O(|V|^3))

    • 适用性：
      适用于允许存在负权边，但不可存在负权回路（即 环上所有权值之和是负数）的图。
      适用于稠密图。

虽然Dijkstra算法解决多源最短路径问题的时间复杂度也为O(|V|^2)*|V|=O(|V|^3)（适用于稀疏图），但是Floyd算法（适用于稠密图）的代码更加紧凑，且并不包含其他复杂的数据结构，因此隐含的常数稀疏更小，更适用。

拓扑排序

图→线性排序，二维→一维
拓扑排序相当于是工程的安排顺序，而回路的存在相当于死锁，所以拓扑排序不存在回路。

有向无环图(DAG图)：若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)。

AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边表示活动之间的先后关系，将这种有向图称为顶点表示活动的网络，记为AOV网(Activity On Vertex)。

  • 基本概念：
    拓扑排序是对有向无环图顶点以线性方式进行的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个DAG图都有一个或多个拓扑排序序列。
    如选课，每个课程都有其先行课，需要先学习。

  • 实现步骤：
    1. 从DAG图中选择一个没有前驱（即 入度为0 没有指向它的箭头）的顶点并输出
    2. 从图中删除该顶点和所有以它为起点的有向边
    3. 重复(1)和(2)直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
  • 简单实现：
void TopSort() {
    for(cnt=0; cnt<|V|; cnt++) {    //计数
        V = 未输出的入度为0的顶点;
        if(这样的V不存在) {
            Error("图中有回路");
            break;
        }
        输出V，或者记录V的输出序号;
        for(V的每个邻接点W) {
            Indegree[W]--;  //并不是真的删除，只是入度-1
        }
    }
}

时间复杂度：T=O((|V|^2))

  • 聪明的算法：
    随时将入度变为0的顶点放到一个容器里（随便什么容器）
void TopSort() {
    for(图中每个顶点) {
        if(Indegree[V] == 0) {
            EnQueue(Q, V);
        }
    }
    while(!IsEmpty(Q)) {
        DeQueue{Q, V};
        输出V，或者记录V的输出序号; cnt++;  //cnt用于记录输出的结点数
        for(V的每个邻接点W) {
            if(--Indegree[W] == 0) {    //入度-1
                EnQueue(W, Q);
            }
        }
    }
    if(cnt != |V|) {    //若还有结点没被输出，那么肯定有回路
        Error("图中有回路");
    }
}

时间复杂度：T=O(|V|+|E|)

关键路径

路径长度最大。

其实该题型一般不会太复杂，列出所有路径并写出长度，比较一下即可。

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动(即 弧表示活动，顶点表示活动的开始或结束)(即 只有在顶点所代表的事件发生后，边代表的活动才能开始)，以边上的权值表示完成该活动的开销（如完成活动所需的时间），则称这种有向图为边表示活动的网络，简称为AOV网(Activity On Edge)。(一般用于安排项目的工序)
注意：AOE网仅有一个开始和结束。

  • 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；
  • 网中也仅存在一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
  • 绘制AOE网时，需要注意，活动从同一顶点开始，从另外的同一顶点结束。（当某一活动不作为其他活动的先驱，则其到达了终点，终点记得汇于一点）

从源点(开始顶点)到汇点(结束顶点)的所有路径中，具有最大路径长度的路径称为关键路径(由绝对不允许延误的活动组成的路径)，而把关键路径上的活动称为关键活动。

  • AOV AOE两者关系：

    其实AOV网与工作流网（AOE）在模型结构上其实是很相似的，它们都是以节点表示活动，有向边表示流程的流向，所不同的是AOV网的有向边仅仅只表示活动的前后次序，也可以说是流程中的流程流向，而工作流网中的有向边却不仅如此，它还可以在每条边上设置不同的条件来决定活动的下一环节是什么，它的出度就不一定是所有有向边了。因此，AOV网其实是工作流网(AOE网)的一种特例，是一种全入全出的有向无环工作流网。

  • 参量定义：（最早前进，最迟后退）（当路径相交时，要判断取最大值还是最小值。前进取最大，后退取最小。）

    1. 事件(顶点)(v_k)的最早发生时间(v_e(k))(即 前一个活动的最早完成时间)
      (v_e(源点) = 0);
      (v_e(k)) = MAX{(v_e(j) + Weight(v_j,v_k))}，(Weight(v_j,v_k))表示<(v_j,v_k)>上的权值

      注意：按从前往后的顺序计算
      最早发生要满足最大值，当前继结点均结束后，才能执行后序结点。

    2. 事件(v_k)的最迟发生时间(v_l(k))(即 前一个活动的最晚完成时间)
      (v_l(汇点) = v_e(汇点));
      (v_l(j)) = MIN{(v_l(k) - Weight(v_j,v_k))}，(Weight(v_j,v_k))表示<(v_j,v_k)>上的权值

      注意：按从后往前的顺序计算
      最迟发生要满足最小值，只有取最小时，当前的进度才能按期完成。
      因为是从后往前，在已知完成时间的情况下，求最迟，所以要取离完成最短的路径（即 最小值）。

    3. 活动(弧)(a_i)的最早开始时间e(i)
      该时间是指该活动的起点所表示的事件最早发生的时间。
      若边<(v_k,v_j)>表示活动(a_i)，则有
      (e(i) = v_e(k))

    4. 活动(a_i)的最迟开始时间l(i)
      该时间是指该活动的终点所表示事件的最迟发生时间与该活动所需时间之差。
      若边<vk,vj>表示活动ai，则有
      (l(i) = v_l(j) - Weight(v_k,v_j))

    5. 一个活动ai的最迟开始时间l(i)和其最早开始时间e(i)的差额(机动时间，时间余量)
      它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动(a_i)可以拖延的时间。
      d(i) = l(i) - e(i)
      若一个活动的时间余量为0，则说明该活动必须要如期完成，否则就会拖延完成整个工程的进度，所以称l(i) - e(i) = 0即l(i) = e(i)的活动(a_i)是关键活动。

  • 简化参数：（最早前进，最迟后退）（当路径相交时，要判断取最大值还是最小值。前进取最大，后退取最小。）

    1. 活动(边)最早完成时间Earliest：
      Earliest[0] = 0;
      Earliest[j] = max{Earliest[i] + (C_{<i,j>})};

      注意：按从前往后的顺序计算

    2. 活动最晚完成时间Latest：
      Latest[汇点] = Earliest[汇点];
      Latest[i] = min{Latest[j] - (C_{<i,j>})};

      注意：按从后往前的顺序计算

    3. 活动的机动时间(D_{<i,j>})：
      (D_{<i,j>}) = Latest[j] - Earliest[i] - (C_{<i,j>});

    • 设各事件的最早发生时间v_e和最迟发生时间v_l：
    (v_1) (v_2) (v_3) (v_4) (v_5) (v_6) 备注
    (v_e(i)) 0 3 2 6 6 8 从前往后(0→)
    (v_l(i)) 0 4 2 6 7 8 从后往前(8→)

    此题关键路径为v1→v3→v4→v6，关键活动为B、E、G

    注意：当(v_e)=(v_l)时，必须如期完成，即 为关键路径

判断回路的存在

  • 判断无向图是否存在回路的方法：
    1. 深度优先搜索DFS：若在搜索过程中两次遍历到同一结点，那么存在环。（当考察的点的下一个邻接点w是已经被遍历的点，并且不是自己之前的父亲节点father[v]（即 不是自己“原路返回”的结点，v不来源于w，w不是v的父亲）的时候，我们就找到了一条逆向边，因此可以判断该无向图中存在环路。）
    2. 在图的邻接表表示中，首先统计每个顶点的度，然后重复寻找一个度为1的顶点，将度为1和0的顶点从图中删除，并将与该顶点相关联的顶点的度减1，然后继续寻找度为1的顶点，在寻找过程中若出现若干顶点的度都为2，则这些顶点组成了一个回路；否则，图中不存在回路。
    3. 广度优先搜索BFS：在遍历过程中，为每个顶点标记一个深度deep，如果存在某个结点为v，除了其父节点u外，还存在与v相邻的结点w(即 在广度优先生成树中加入了一条边，vw相邻，所以肯定存在回路)使得deep[v]<=deep[w]的，那么该图一定存在回路。
    4. 用BFS或DFS遍历，判断对于每一个连通分量当中，如果边数m>=结点个数n，那么该图一定存在回路。
  • 判断有向图是否存在回路的方法：
    1. 深度优先搜索：若在搜索过程中某一顶点出现两次，则有回路出现。（当考察的点的下一个邻接点是已经被遍历的点，即存在回路）（与无向图不同）

    2. 拓扑排序：即重复寻找一个入队为0的顶点，将该顶点从图中删除，并将该顶点及其所有的出边从图中删除（即 与该点相应的顶点的入度减1），最终若途中全为入度为1的点，则这些点至少组成一个回路。

      有向图中广度优先搜索不能判断回路，是因为：它是沿着层向下搜索的，无法判断当前层是否有同时针的连接，所以无法判断回路（要路径上第一个结点和最后一个结点相同，即同时针（顺时针或者逆时针））。
      不是环：这个情况实际上并不是一个环，它仅仅是访问到了一个前面访问过的节点。遍历时无法与真正是环的区分开

      这样才是环：

DFS判断无向图回路

  • 算法思想：
    利用深度遍历，若遍历时两次碰到同一结点，那么存在环。（当考察的点的下一个邻接点w是已经被遍历的点，并且不是自己之前的父亲节点father[v]的时候（即 不是自己“原路返回”的结点，v不来源于w，w不是v的父亲，即 绕了一圈回来了），我们就找到了一条逆向边，因此可以判断该无向图中存在环路。）（也就是说 只允许这个图一直向下访问(子结点)，不能向上访问(它的父结点)，否则逆向边，有环）
//深度优先搜索（Depth-First-Search,DFS）
bool visited[MAX_VERTEX_NUM];   //访问标记数组
int father[MAX_VERTEX_NUM];     //标记下标对应结点的父亲结点（即 该下标结点来源于哪个结点）

bool DFS(Graph G,int v){        //从顶点v出发，采用递归思想，深度优先遍历图G
//  for(v=0;v<G.vexnum;v++)
//      visited[v]=FALSE;       //访问标志数组初始化
    visit(v);       //访问顶点v
    visited[v]=TRUE;        //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))    //<v,w>，v的邻接点w
        if(!visit[w]) {
            father[w] = v;      //w的父亲结点为v
            DFS(G,w);
        }else if(w != father[v]) {  //邻接点w被访问过，并且它不是当前结点v的父亲结点（即 v不来源于w，w不是v的父亲）（即 绕了一圈回来了）
            return true;    //存在回路
        }
    }
    return false;   //不存在回路
}

//如果是判断是否有环，则需使用此算法遍历整个图（包括非连通图），但如果只是判断图是否为一棵树，那么如果图一次性没被遍历完，那么就不可能是一棵树
bool DFSTraverse(Graph G){      //对图G进行尝试优先遍历，访问函数为visit()
    for(v=0;v<G.vexnum;v++) {
        visited[v]=FALSE;       //访问标志数组初始化
    }
    for(v=0;v<G.vexnum;v++) {   //本代码中是从v=0开始遍历
        if(!visited[v]) {
            if(DFS(G,v)==true) {
                return true;    //整个图（包括非连通图）中存在回路
            }
        }
    }
    return false;   //不存在回路
}

DFS判断无向图是否是一棵树

一个无向图G是一棵树的条件是，G必须是无回路的连通图或有n-1条边的连通图。

  • 算法思想：（无回路的连通图）
    利用上述判断回路的算法，只需将遍历整个图修改为判断该一次遍历是否访问了所有结点。
//深度优先搜索（Depth-First-Search,DFS）
bool visited[MAX_VERTEX_NUM];   //访问标记数组
int father[MAX_VERTEX_NUM];     //标记下标对应结点的父亲结点（即 该下标结点来源于哪个结点）

bool DFS(Graph G,int v){        //从顶点v出发，采用递归思想，深度优先遍历图G
    for(v=0;v<G.vexnum;v++)
        visited[v]=FALSE;       //访问标志数组初始化
    visit(v);       //访问顶点v
    visited[v]=TRUE;    //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))    //<v,w>，v的邻接点w
        if(!visit[w]) {
            father[w] = v;      //w的父亲结点为v
            DFS(G,w);
        }else if(w != father[v]) {  //邻接点w被访问过，并且它不是当前结点v的父亲结点（即 v不来源于w，w不是v的父亲）
            return false;   //存在回路，不是一棵树
        }
    }
    for(v=0;v<G.vexnum;v++) {
        if(visited[v]!=TRUE) {  //如果一次遍历未能访问所有结点，则该图不连通
            return false;   //图不连通，不是一棵树
        }
    }
    return true;    //不存在回路的连通图，即是一棵树
}
  • 算法思想：（n-1条边）
    对连通的判定，可用能否遍历全部顶点来实现。可以采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数，若一次遍历就能访问到n个顶点和n-1条边，则可断定此图是一棵树。
bool isTree(Graph &G) {
    for(i=1; i<G.vexnum; i++) {
        visited[i]=FALSE;   //访问标记visited[]初始化
    }
    int Vnum = 0, Enum = 0; //记录顶点数和边数
    DFS(G, 1, Vnum, Enum, visited);
    if(Vnum==G.vexnum && Enum==2*(G.vexnum-1))  //n个顶点，n-1条边（注意这个边因为是无向图，访问了两遍，类似于度）
        return true;    //符合树的条件
    else
        return false;   //不符合树的条件
}

void DFS(Graph &G, int v, int &Vnum, int &Enum, int visited[]) {
//深度优先遍历图G，统计访问过的顶点数和边数没通过Vnum和Enum返回
    visited[v] = TRUE;  //作访问标记，顶点计数
    Vnum++;
    int w = FirstNeighbor(G, v);    //取v的第一个邻接顶点
    while(w != -1) {    //当邻接顶点存在
        Enum++;     //边存在，边计数
        if(!visited[w]) {   //当该邻接顶点未访问过
            DFS(G, w, Vnum, Enum, visited);
        }
        w = NextNeighbor(G, v, w);
    }
}

常用算法

自由树（无权连通图），任意两个结点之间的路径长度最大值为该树的直径，设计一算法要求最小的时间复杂度，求出最大直径。

  • 算法思想：
    利用树中求高的方法，求出子树(即 该点除了至父亲结点的那条边之外的其他边)的高，取最大两个子树的高相加再+1，即 为最大直径。由于遍历了所有顶点，类似于遍历算法，故时间复杂度为O(n)
int father[MAX_VERTEX_NUM];     //标记下标对应结点的父亲结点（即 该下标结点来源于哪个结点）

int THeight(Tree T, int v) {
//求自由树的高
    if(!v) {    //递归出口
        return 0;
    }
    p = v->firstarc;
    //遍历T中所有邻接点
    while(p) {
        if(p->adjvex != father[v]) {    //不断向下访问，只能向下（子结点）访问，不能向上访问父结点
            father[p->adjvex] = v;  //设置邻接点的父结点
            adjdep[v++] = THeight(T, p->adjvex);    //求邻接点（子树）中的高度
        }
        p = p->next;
    }
    max = adjdep[0];
    for(i=0; i<v; i++) {    //取出最大高度
        if(adjdep[i] > max) {
            max = adjdep[i];
        }
    }
    return max+1;
}

int MAX_D(Tree T) {
//利用求树高算法，求自由树的直径
    p = T->vertices[0].firstarc;
    while(p) {
        adjdep[v++] = THeight(T, p->adjvex);    //求邻接点（子树）中的高度
        p = p->next;
    }
    //选择排序，取出邻接点两个最大的高度
    for(i=0; i<2; i++) {
        min = adjdep[i];
        for(j=i+1; j<n; j++) {
            if(adjdep[j] < min) {
                min = adjdep[j];
            }
            a[i] = min;
        }
    }
    //取出邻接点前两个最大的高度，相加再+1，则为直径
    return a[0]+a[1]+1;
}
  • 算法思想：
    下面用邻接表作为存储结构，依次删去树叶（度为1的结点），将与树叶相连的结点度数-1，设在第一轮删去原树T的所有树叶后，所得树为T1；再依次做第二轮删除，即删除所有T1的叶子；如此重复，若剩下最后一个结点，则树的直径应为删除的轮数*2。
/*算法思想：下面用邻接表作为存储结构，依次删去树叶（度为1的结点），将与树叶相连的结点度数-1，设在第一轮删去原树T的所有树叶后，所得树为T1；再依次做第二轮删除，即删除所有T1的叶子；如此重复，若剩下最后一个结点，则树的直径应为删除的轮数*2.*/
int MAX_D()
{
    m=0;    //m记录当前一轮叶子数
    for(i=1；i<=n；i++)
        if(du(veil)-1){     //du(v)==1，即叶子结点
            enqueue(Q，v[i]);    //叶子vi入队
            m=m+l;  //m记录当前一轮叶子数
        }
    r=0;    //表示删除叶子轮数
    while(m>=2){    //当前叶子轮数
        j=0;    //j计算新一轮叶子数目
        for(i=1; i<=m; i++){    //将一轮叶子结点全部删光
            dequeue(Q, v);  //出队，表示删去叶子v将与v相邻的结点w的度数减1
            if(du(w)==1){   //w是新一轮的叶子
                j=j+1;
                enqueue(Q, w);//w入队
            }   
        }
        r=r+1;  //删光一轮后，轮数+1进行下一轮
        m=j;    //新一轮叶子总数
    }
    if(m==0)
        return 2*r-1;   //m=0，直径为轮数*2-1
    else 
        return 2*r; //m=l，直径为轮数*2
}

判断图是否有环

看上面

判断无向图是否为一棵树

看上面

判断有向图中是否存在由顶点vi到顶点vj的路径(i≠j)

  • 算法思想：
    两个不同的遍历算法都采用从顶点vi出发，依次遍历图中每个顶点，直到搜索到顶点vj，若能够搜索到vj，则说明存在由顶点vi到顶点vj的路径。

深度优先遍历算法

int visit[MAXSIZE] = {0};   //访问标记数组

int Exist_Path_DFS(ALGraph G, int i, int j) {
//深度优先判断有向图G中顶点vi到顶点vj是否有路径，是则返回1，否则返回0
    int p;      //顶点序号
    if(i == j) {
        return 1;   //i就是j
    }else {
        visited[i] = 1;     //置访问标记
        for(p=FirstNeighbor(G,i); p>=0; p=NextNeighbor(G,i,p)) {
            k = p.adjvex;
            if(!visited[p] && Exist_Path_DFS(G,p,j)) {  //递归检测邻接点
                return 1;   //i下游的顶点到j有路径
            }
        }
    }
    return 0;
}

广度优先遍历算法

int visit[MAXSIZE] = {0};   //访问标记数组

int Exist_Path_BFS(ALGraph G, int i, int j) {
//广度优先判断有向图G中顶点vi到顶点vj是否有路径，是则返回1，否则返回0
    InitQueue(Q);
    EnQueue(Q,i);       //顶点i入队
    while(!isEmpty(Q)) {    //非空循环
        DeQueue(Q,u);       //队头顶点出队
        visited[u] = 1;     //置访问标记
        for(p=FirstNeighbor(G,i); p>=0; p=NextNeighbor(G,i,p)) {    //检查所有邻接点
            k = p.adjvex;
            if(k == j) {    //若k==j，则查找成功
                return 1;
            }
            if(!visited[k]) {   //否则，顶点k入队
                EnQueue(Q,k);
            }
        }
    }
    return 0;
}

输出从顶点vi到顶点vj的所有简单路径

  • 算法思想：
    本题采用基于递归的深度优先遍历算法，从结点u出发，递归深度优先图中结点，若访问到结点v，则输出该搜索路径上的结点。为此设置一个path数组来存放路径上的结点（初始为空），d表示路径长度（初始为-1）。查找从顶点u到v的简单路径过程说明如下（假设查找函数名为FindPath()）：
    1. FindPath(G,u,v,path,d)：d++；path[d]=u；若找到u的未访问过的相邻结点u1，则继续下去，否则置visited[u]=0并返回；
    2. FindPath(G,u1,v,path,d)：d++；path[d]=u1；若找到u1的未访问过的相邻接点u2，则继续下去，否则置visited[u1]=0；
    3. 以此类推，继续上述递归过程，直到ui=v，输出path。
void FindPath(ALGraph *G, int u, int v, int path[], int d) {
    int w, i;
    ArcNode *p;
    d++;        //路径长度+1
    path[d] = u;        //将当前顶点添加到路径中
    visited[u] = 1;     //置已访问标记
    if(u == v) {        //找到一条路径则输出（递归出口）
        print(path[]);  //输出路径上的结点
    }
    p = G->adjlist[u].firstarc; //p指向v的第一个邻接点
    while(p != NULL) {
        w = p->adjvex;  //若顶点w未被访问，递归访问它
        if(visited[w] == 0) {
            FindPath(G, w, v, path, d);
        }
        p = p->nextarc; //p指向v的下一个邻接点
    }
    visited[u] = 0;     //恢复环境，使该顶点可重新使用
}

归纳总结

  • 求关键路径：
    这类题目一般不会很复杂，直接列出所有路径及其长度，比较一下，取最大，即可得出关键路径。
  • 求单源最短路径：
    这类题目一般不会很复杂，若没有要求用什么方法，则可以直接一个一个列出来即可，不必刻意用Dijkstra算法。
  • 关于图的基本操作：
    • 用邻接矩阵作为存储结构：
    int NextNeighbor(MGraph &G, int x, int y) {
    if(x!=-1 && y!=-1) {
        for(int col=y+1; col<G.vexnum; col++) {
            if(G.Edge[x][col]>0 && G.Edge[x][col]<maxWeight) {  //maxWeight代表∞
                return col;
            }
        }
    }
    return -1;
}
    • 用邻接表作为存储结构：
    int NextNeighbor(ALGraph &G, int x, int y) {
    if(x != -1) {   //顶点x存在
        ArcNode *p = G.vertices[x].first;//对应边链表第一个边结点
        while(p!=NULL && p->data!=y) {  //寻找邻接顶点y
            p = p->next;
        }
        if(p!=NULL && p->next!=NULL) {
            return p->next->data;       //返回下一个邻接顶点
        }
    }
}

本文参考：
https://blog.csdn.net/qq_37134008/article/details/85325251
https://blog.csdn.net/a2392008643/article/details/81781766
https://blog.csdn.net/leaf_130/article/details/50684679

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/blknemo/p/11275725.html