数据结构——图

发表于 2024-12-02 更新于 2025-06-12 分类于大二上，数据结构阅读次数：

图的基本概念和术语

定义：一个图可以利用两个集合进行定义。第一个集合是点的集合,这些点在图术语中一般被称(Vertex);第二个集合是连接两个顶点的边(Edge)的集合。图的具体定义如下。图是由顶点集合及顶点间的关系集合组成的一种数据结构:Graph = (V, E)

基本术语

有向图
无向图
邻接点
顶点的度，入度与出度
权和网：
- 权： 某些图的每条边都可能赋予一个数值，这个数值称为权。
- 网： 带有权的图称为网。
无向完全图： 任意两个顶点之间都有一条边的无向图。

有向完全图： 任意两个顶点之间都有方向相反的两条边的有向图。

路径与路径长度
简单路径：若路径上经过的各顶点均不重复，则称这样的路径为简单路径。

回路或环：若路径上的第一个顶点与最后一个顶点相同，则称这样的路径为回路或环。

连通图： 在无向图中，若任意两个顶点之间都存在路径，则称该图为连通图。

连通分量： 非连通图的极大连通子图称为连通分量。也就是说，一个连通分量是一个连通的子图，且不能再扩大。
强连通图： 在有向图中，若对于任意一对顶点 u 和 v，都存在一条从 u 到 v 和从 v 到 u 的路径，则称该图为强连通图。

强连通分量： 非强连通图的极大强连通子图称为强连通分量。
生成树： 一个连通图的生成树是包含图中所有顶点的极小连通子图。也就是说，生成树是一棵树，且包含图中的所有顶点。

生成森林： 非连通图的每个连通分量分别可以得到一棵生成树，这些生成树的集合称为生成森林。

图的储存结构

邻接矩阵

邻接矩阵表示法的基本思想是引入两个数组：

一个用于记录图中各个顶点信息的—维数组，称为顶点表；
另一个用于表示图中各个顶点之间关系的二维数组，称为邻接矩阵。

设图G=(V, E)是具有n(n>0)个顶点的图，则图G所对应的邻接矩阵A是一个n阶方阵

无向图的邻接矩阵可采用只存储上三角阵或下三角阵的压缩存储方法

对于带权图，需要对邻接矩阵的元素值定义进行修改，让元素值表示相应顶点的权值

其中，∞可用计算机中的一个足够大的数代替，以与权重区分

算法

图类MGraph的定义

// 图的类型定义: 无向图、无向网、有向图、有向网
enum GraphType { undigraph, digraph, undinetwork, dinetwork };

template <class T>
struct EdgeType { // 本类型定义也适用于后面的邻接表结构
    T head, tail;
    int cost;
    EdgeType(T h, T t, int c) {
        head = h;
        tail = t;
        cost = c;
    }
};

template <class T>
class MGraph {
private:
    int vexnum, edgenum;
    GraphType kind;
    vector<vector<int>> edges; // 邻接矩阵
    vector<T> vexs;            // 顶点表
};

无向有权图的邻接矩阵构建

void createAdjMatrix(vector<vector<int>>& adjMatrix, const vector<tuple<int, int, int>>& edges, int numVertices) {
    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (i != j) adjMatrix[i][j] = INT_MAX; // 没有边的地方设置为无穷大，当i=j的值为0
        }
    }

    // 填充边的信息
    for (const auto& edge : edges) {
        int u = get<0>(edge);  // 获取第一个元素
        int v = get<1>(edge);  // 获取第二个元素
        int weight = get<2>(edge);  // 获取第三个元素
        adjMatrix[u][v] = weight;
        adjMatrix[v][u] = weight;  // 无向图
    }
}

邻接表

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。

算法

基于邻接表存储表示的图类ALGraph定义

// 边节点
struct EdgeNode {
    int adjvex;  // 邻接点下标
    EdgeNode* next; // 指向下一个邻接点
};

// 顶点节点
template <class T>
struct VexNode {
    T data;
    EdgeNode* firstEdge;
};

// 图的邻接表表示
template <class T>
class ALGraph {
    vector<VexNode<T>> vex;  // 顶点数组
    int vexnum, edgenum;  // 顶点数和边数
	GraphType kind;
};

无向图的构建

template <class T>
ALGraph<T>::ALGraph(GraphType t, T vexs[], int n, int e) {
    // 参数表示图的类型, 参数vexs为存储各顶点值的数组, 参数n和e分别为顶点数和边数
    vexnum = n;
    edgenum = e;
    kind = t;
    adjlist.resize(vexnum);

    // 初始化顶点表
    for (int i = 0; i < vexnum; ++i) {
        adjlist[i].data = vexs[i];
        adjlist[i].firstEdge = 0;
    }

    // 依次输入所有的边的信息
    for (int j = 0; j < edgenum; j++) {
        int va, vb;
        cin >> va >> vb;

        // 产生第一个表结点
        EdgeNode* p = new EdgeNode;
        p->adjvex = vb;
        p->nextedge = adjlist[va].firstEdge;
        adjlist[va].firstEdge = p;

        // 产生第二个表结点
        p = new EdgeNode;
        p->adjvex = va;
        p->nextedge = adjlist[vb].firstEdge;
        adjlist[vb].firstEdge = p;
    }
}

图的遍历

为了防止已经访问过的结点重复访问的问题，提出了辅助数组 visited[]

深度优先遍历

深度优先搜索类似于树的先序遍历。

算法

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//访问顶点
	visited[v] = TRUE;	//设已访问标记
	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
	int v; 
	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);
		}
	}
}

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

对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(V^2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(V＋E)。

广度优先遍历

图的广度优先遍历就类似于树的层序遍历

算法

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for(i = 0; i<G,numVertexes; i++){
		visited[i] = FALSE;
	}
	InitQueue(&Q);	//初始化一辅助用的队列
	for(i=0; i<G.numVertexes; i++){
		//若是未访问过就处理
		if(!visited[i]){
			vivited[i] = TRUE;	//设置当前访问过
			visit(i);	//访问顶点
			EnQueue(&Q, i);	//将此顶点入队列
			//若当前队列不为空
			while(!QueueEmpty(Q)){
				DeQueue(&Q, &i);	//顶点i出队列
				//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
				//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
					//检验i的所有邻接点
					if(!visited[j]){
						visit(j);	//访问顶点j
						visited[j] = TRUE;	//访问标记
						EnQueue(Q, j);	//顶点j入队列
					}
				}
			}
		}
	}
}

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q, n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(V)。采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，在搜索任一顶点的邻接点时，每条边至少访问一次，算法总的时间复杂度为O(V＋E)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为O(V)，故算法总的时间复杂度为O(V^2)。

注意:图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

应用

简单路径的搜索算法 dfs

二部图的判定算法

最小生成树

生成树变成非连通图;若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图G=(V,E)，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树)，称为G的最小生成树(Minimum-Spanning-Tree,MST)。

普里姆（Prim）算法

从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。

引入辅助数组miniedges[]，用于存放每个节点到节点v的边的权值，并每次挑选出权值最小的那个边所对应的节点加入生成树，辅助数组miniedges[]的数据类型如下

struct Edge {
    int adjvex;  // 与当前生成树连接的节点的编号
    int lowcost; // 到当前生成树的最小边权值
};

若将某个数组元素miniedges[i]的 lowcost成员值设为0，则表示相应的顶点v,已加入到最小生成树中。

为便于算法在执行过程中读取任意两个顶点之间边的权值，对图宜采用邻接矩阵存储结构。

算法思路：

初始化辅助数组，从节点v开始，将v的lowcost设为0，说明已经加入生成树
循环vexnum-1次，利用函数MiniNum找到权值最小的节点并输出

函数MiniNum循环vexnum次，找到当前所有节点中，未加入生成树的，lowcost最小的节点
更新辅助数组miniedges[]的每个节点的lowcost：循环vexnum次，如果通过当前节点k能找到比原先更小的边，更新该节点的lowcost；如果大，则保留原lowcost的值，更新后代表生成树节点的集合到未加入节点的集合的权值最小的vexnum条边

时间复杂度：O(n^2)

void Prim(const vector<vector<int>>& graph, int v, int vexnum) {
    // 初始化 miniedges 数组
    Edge* miniedges = new Edge[vexnum];
    
    // 初始化 miniedges，每个节点到起始点v的边的权值
    for (int i = 0; i < vexnum; i++) {
        miniedges[i].adjvex = GetVexValue(v);        // 初始时节点的连接为起始节点v
        miniedges[i].lowcost = GetEdgeValue(graph, v, i);   // 初始化每个节点到v的边权值
    }

    miniedges[v].lowcost = 0; // 将起始节点v的lowcost设为0，表示已经加入生成树

    // 循环执行，每次选取一个未加入生成树的权值最小的节点
    for (int i = 1; i < vexnum; i++) {
        // 找到最小的lowcost
        int k = MiniNum(miniedges, vexnum);
        
        // 输出当前加入生成树的边
        cout << miniedges[k].adjvex << " --> " << GetVexValue(k) << endl;
        
        // 将选中的节点k加入生成树
        miniedges[k].lowcost = 0; // 表示节点k已加入生成树

        // 更新与当前生成树连接的节点的lowcost（最小边权值）
        for (int j = 0; j < vexnum; j++) {
            // 如果通过当前节点k能找到比原先更小的边，更新该节点的lowcost
            if (GetEdgeValue(graph, k, j) < miniedges[j].lowcost) {
                miniedges[j].adjvex = GetVexValue(k);   // 记录当前节点k
                miniedges[j].lowcost = GetEdgeValue(graph, k, j); // 更新到生成树的最小边权值
            }
        }
    }

    // 释放动态分配的内存
    delete[] miniedges;
}

函数MiniNum用于在数组miniedges中查找集合V-U中的具有最小权值的顶点,可以将它定义为私有成员函数

// 找到当前所有节点中，未加入生成树的，lowcost最小的节点
int MiniNum(Edge miniedges[], int vexnum) {
    int min = INT_MAX;
    int k = -1;
    for (int i = 0; i < vexnum; i++) {
        if (miniedges[i].lowcost != 0 && miniedges[i].lowcost < min) { // 如果该节点未加入生成树
            min = miniedges[i].lowcost;
            k = i;
        }
    }
    return k; // 返回最小权值的节点
}

克鲁斯卡尔（Kruskal）算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

每次挑选为加入生成树的最小边，若不构成回路，则加入生成树，若构成则挑选下一个

为提高算法执行过程中查找最小权值边的速度，可以采用一种排序算法(如堆排序算法)对边集数组中的边按权值进行排序。

接下来，Kruskal算法的关键问题就是如何判断所选取的边加入T中是否会产生回路，这里通过引入称为并查集的数据结构来解决

在下面描述的Kruskal 算法实现中，首先利用私有成员 GetGraph()函数将图的边按权值排好序后存入边集数组graph中，而边集数组tree则用于保存和返回算法所构造的最小生成树T。

算法思路：

初始话数组graph，用于存放所有的边，并对其排序
并查集的使用利用数组components，先进行初始化，每个节点的祖先都是自己，也可以理解成每个节点都构成一个集合，后续并查集的过程即为集合合并的过程
循环直到找到最小生成树的所有边（vexnum - 1条），对于每条边，查找他的起点和终点节点的祖先，若是一个祖先则说明在同一集合，不能加入到生成树；若不是一个，则可以加入到生成树数组tree，并要修改节点的祖先，使他们集合合并

template <class T>
void MGraph<T>::Kruskal(vector<EdgeType> &tree) {
    // 创建一个图的边集合，用于存放所有的边
    vector<EdgeType> graph;
    // GetGraph函数将图的所有边按权值从小到大存放到graph数组中
    GetGraph(graph);

    // 初始化最小生成树数组，并且初始化并查集组件
    tree.resize(vexnum - 1);  // 最小生成树包含的边数量是vexnum - 1
    int *components = new int[vexnum];  // 记录每个节点所属的集合
    // 初始时，每个节点都属于自己的集合
    for (int i = 0; i < vexnum; i++) {
        components[i] = i;
    }

    int k = 0, j = 0;
    // 循环直到找到最小生成树的所有边（vexnum - 1条）
    while (k < vexnum - 1) {
        // 从排序好的边中选择一条边
        int h1 = graph[j].head;  // 边的起点
        int t1 = graph[j].tail;  // 边的终点
        int h2 = components[h1];  // 获取起点所在的集合
        int t2 = components[t1];  // 获取终点所在的集合

        // 如果起点和终点属于不同的集合，则这条边可以加入最小生成树
        if (h2 != t2) {
            // 将这条边加入最小生成树中
            tree[k].head = h1;
            tree[k].tail = t1;
            tree[k].cost = graph[j].cost;  // 边的权值
            k++;  // 记录已选择的边的数量

            // 合并两个集合，统一编号
            // 将所有属于终点集合t2的顶点，集合编号更新为起点集合h2的编号
            for (int i = 0; i < vexnum; i++) {
                if (components[i] == t2) {
                    components[i] = h2;  // 更新组件编号
                }
            }
        }
        j++;  // 继续检查下一条边
    }

    // 释放动态分配的内存
    delete[] components;
}

显然，Kruskal算法的效率与所选择的排序算法的效率以及并查集数据结构的实现效率有关。若采用第10章介绍的比较高效的堆排序算法排序，并查集采用树结构实现，则Kruskal算法的时间复杂度可达到O( elog₂e)。相比 Prim 算法而言，Kruskal算法更适用于求解稀疏网(指边数较少的网)的最小生成树。

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

求图的最短路径问题通常可分为两类。一类是求图中某顶点到其余各顶点的最短路径问题，也称为单源最短路径问题;另一类是求图中每对顶点之间的最短路径问题。

迪杰斯特拉( Dijkstra )算法

Dijkstra算法用于构建单源点的最短路径—，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值。

通俗点说，迪杰斯特拉(Dijkstra)算法，它并不是一下子求出了 v_i到 v_j的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

下面介绍 Dijkstra算法的具体实现。为便于在算法执行过程中快速地求得任意两个顶点之间边的权值，图的存储结构宜采用邻接矩阵方式。

为标识图中各顶点在算法执行过程中是否已求出最短路径，设置一个一维数组s[]

为记录 Dijkstra算法所求出的从源点到各顶点的最短路径，引入数组 path[], path[i]中保存了从源点到终点v,的最短路径上该顶点的前驱顶点的序号。算法结束时，可根据数组path[ ]找到源点到v,的最短路径上每个顶点的前驱顶点，并一直回溯至源点，从而推出从源点到v的最短路径。

为便于每次从V-S中选择当前离源点距离最短的顶点，需要引人一个辅助数组dist[]。它的每一个分量dist[i]表示当前所确定的从源点 v₀,到终点 v_i的最短路径.

算法思路：

初始化，s[]所有值为0，s[0]设置为1，代表从 v₀节点开始，path[]所有值设为0，path[0]设为-1，dist[]通过查找邻接矩阵，得到 v₀到各个顶点的值
查找dist中最小的值，从该节点继续完成最小路径，将该节点对应s[]设为1
遍历尚未找到最短路径的节点，即s[]为0，dist[i] = Min{dist[i]，dist[j] +cost(j,i)}，选择是借用上一个最短路径的节点到达还是直接到达，更新dist的值

// Dijkstra算法：计算从起点start到其他所有节点的最短路径
void dijkstra(int start, int dist[], int path[]) {
    int n = numVertices;  // 获取图中节点的数量
    bool visited[n];  // 访问标记数组，用于标记节点是否已经被访问

    // 初始化dist数组和path数组
    // dist[i] 表示从起点到节点i的最短距离
    // path[i] 表示从起点到节点i的最短路径的前驱节点
    for (int i = 0; i < n; ++i) {
        visited[i] = false;  // 初始时，所有节点均未被访问
        dist[i] = adjMatrix[start][i];  // dist数组初始化为起点到各节点的初始距离
        if (dist[i] != INT_MAX || i == start) {  // 如果有边（距离不为无穷大），或者是起点本身
            path[i] = start;  // 将路径的前驱节点设置为起点
        } else {
            path[i] = -1;  // 如果节点无法从起点到达，前驱节点为-1
        }
    }

    dist[start] = 0;  // 起点到起点的距离为0
    visited[start] = true;  // 标记起点为已访问

    // 进行n-1轮循环，逐步更新最短路径
    for (int count = 0; count < n - 1; ++count) {
        int min = INT_MAX, min_index;

        // 找到未访问的节点中距离最小的节点
        for (int v = 0; v < n; ++v) {
            // 选择距离最小且未被访问的节点
            if (visited[v] == false && dist[v] <= min) {
                min = dist[v];  // 更新最小距离
                min_index = v;  // 记录最小距离节点的索引
            }
        }

        visited[min_index] = true;  // 标记该节点为已访问

        // 更新与该最小距离节点相邻的节点的距离
        for (int v = 0; v < n; ++v) {
            // 如果v节点未被访问，并且从min_index到v有边，且经过min_index节点的路径更短
            if (!visited[v] &&  
                dist[v] > dist[min_index] + adjMatrix[min_index][v]) {
                dist[v] = dist[min_index] + adjMatrix[min_index][v];  // 更新v的最短距离
                path[v] = min_index;  // 更新v的前驱节点
            }
        }
    }
}

// 打印从源节点到目标节点v的路径
void PrintPath(const vector<vector<int>>& g, vector<int> path, vector<int> dist, int v) {
    if (dist[v] == INF) {
        cout << "节点 " << v << " 无法到达" << endl;
        return;
    }

    // 递归打印路径
    if (path[v] != -1) {
        PrintPath(g, path, dist, path[v]);
    }

    cout << v << " ";
}

时间复杂度O(n^2)

弗洛伊德( Floyd )算法

算法原理：递归

n阶数组D：用于保留每一步所求得的所有顶点对之间的当前最短路径长度

初始化： D[i][j] = cost(i, j)用邻接矩阵进行初始化

状态转移方程： D^k[i][j] = min{D^k − 1[i][j], D^k − 1[i][k] + D^k − 1[k][j]}更新v_i到v_j的最短路径

path数组：用于存储最短路径，初始化若没有直接路径则 path[i][j] = −1，若有则 path[i][j] = j

算法思路：

初始化数组，遍历n*n次，即v_i到v_j和v_j到v_i都遍历一遍，通过状态转移方程更新D数组的值，若找到短的路径，则同时也更新path数组

// Floyd算法
template <class T>
void MGraph<T>::Floyd(int path[][MAXV], int D[][MAXV]) {
    // 初始化距离矩阵D和路径矩阵path
    for (int i = 0; i < vexnum; ++i) {
        for (int j = 0; j < vexnum; ++j) {
            D[i][j] = edges[i][j];
            //初始化path
            if (D[i][j] < INF && i != j)
                path[i][j] = j;  // 若i到j有直接路径，记录路径
            else
                path[i][j] = -1; // 否则路径不存在
        }
    }

    // 核心Floyd-Warshall算法
    for (int k = 0; k < vexnum; ++k) {
        for (int i = 0; i < vexnum; ++i) {
            for (int j = 0; j < vexnum; ++j) {
                if (D[i][k] != INF && D[k][j] != INF && D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];  // 更新最短路径长度
                    path[i][j] = path[i][k];      // 更新路径
                }
            }
        }
    }
}

函数OutputPath用于输出保存于二维数组path中的所有路径以及保存于二维数组D中的路径长度

template <class T>
void OutputPath(MGraph<T> &G, int path[][MAXV], int D[][MAXV]) {
    // 遍历所有顶点对，输出源点到目标点的最短路径及路径长度
    for (int i = 0; i < G.vexnum; ++i) {      // 遍历所有源点 i
        for (int j = 0; j < G.vexnum; ++j) {  // 遍历所有目标点 j
            if (i != j) { // 排除自身到自身的情况
                if (D[i][j] == INF) {  // 若距离为无穷大，表示无路径
                    std::cout << "Path from " << i << " to " << j << ": No path exists.\n";
                } else {  // 若存在路径
                    std::cout << "Path from " << i << " to " << j << " (Length: " << D[i][j] << "): ";
                    
                    // 输出路径，使用 path 数组逐步跟踪中间节点
                    int temp = i;      // 起始点
                    std::cout << temp; // 输出源点
                    while (temp != j) { // 当未到达目标点时
                        temp = path[temp][j];  // 获取路径中的下一个节点
                        std::cout << " -> " << temp; // 输出中间节点或目标点
                    }
                    std::cout << std::endl; // 换行
                }
            }
        }
    }
}

AOV网与拓扑排序

有向无环图：不含环的有向图

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V, V2 ,..V n，满足若从顶点V到V;有一条路径，则在顶点序列中顶点V必在顶点V;之前。则我们称这样的顶点序列为一个拓扑序列。

拓扑排序：其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:

①从AOV网中选择一个没有前驱的顶点并输出。 ②从网中删除该顶点和所有以它为起点的有向边。 ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。

算法原理：dfs

对于AOV 网宜采用邻接表作为存储结构

数组indegree：用于存放各个顶点的入度

算法思路：

每次遍历数组indegree，查找入度为零的顶点，将其加入队列，再遍历邻接表，将遍历到的顶点的indegree值减一，并判断是否为零，若为零则加入队列

// 拓扑排序实现
void Graph::topologicalSort() {
    vector<int> indegree(V, 0); // 入度数组
    queue<int> q;              // 队列

    // 计算所有顶点的入度
    for (int i = 0; i < V; i++) {
        for (int v : adj[i]) {
            indegree[v]++;
        }
    }

    // 将入度为0的顶点加入队列
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    int count = 0; // 用于检测图是否存在环

    // 输出拓扑排序
    cout << "拓扑排序顺序为: ";
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 输出顶点
        count++;

        // 遍历该顶点的所有邻接点，并更新它们的入度
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    cout << endl;

    // 如果没有输出所有顶点，说明存在环
    if (count != V) {
        cout << "图中存在环，无法进行拓扑排序！" << endl;
    }
}