图的存储、遍历以及Dijkstra/Floyd/Kruskal/Prim/拓扑排序/关键路径(实验8--作业)

图–数据结构操作与算法全解析

一、引言

图作为一种重要的数据结构，在计算机科学与众多领域中都有着广泛的应用。它能够有效地描述和解决各种复杂的关系问题，如网络拓扑、路径规划、资源分配等。本文将详细介绍图的相关操作和知识点，包括图的创建、遍历（深度优先遍历和广度优先遍历）、最小生成树（Kruskal 和 Prim 算法）、最短路径（Djikstra 和 Floyd 算法）以及拓扑排序，并结合具体代码进行深入剖析。

二、图的基本概念

图由顶点（Vertex）和边（Edge）组成。顶点表示对象，边表示对象之间的关系。根据边是否有方向，图可分为有向图（Directed Graph）和无向图（Undirected Graph）；根据边是否有权重，又可分为有权图（Weighted Graph）和无权图（Unweighted Graph）。在实际应用中，这些不同类型的图各有其适用场景，例如社交网络可以用无向图表示用户之间的好友关系，而交通网络则可以用有权有向图表示道路的方向和距离。

三、图的存储结构

（一）邻接矩阵

  1. 定义与原理
    • 邻接矩阵是用一个二维数组来表示图中顶点之间的关系。对于一个具有 n 个顶点的图，其邻接矩阵 arcs 的大小为 n×n。如果 arcs[i][j] = 1（或边的权重值，对于有权图），表示顶点 i 和顶点 j 之间有边相连；如果 arcs[i][j] = 0（或 MaxInt，表示无穷大，对于无权图），则表示顶点 i 和顶点 j 之间没有边相连。在无向图中，邻接矩阵是对称的，因为边没有方向，即 arcs[i][j] = arcs[j][i]。
  2. 代码实现与分析
    • 在给定的代码中，AMGraph 结构体中的 arcs 二维数组就是用于存储邻接矩阵。在 CreateUDN 函数中，首先初始化邻接矩阵，将所有元素设置为 MaxInt，表示初始时顶点之间没有边相连。然后，当输入边的信息时，通过 Locate 函数找到顶点在数组中的下标 m 和 n，并将 arcs[m][n] 和 arcs[n][m]（对于无向图）设置为边的权重值 a，从而构建起邻接矩阵。这种存储结构的优点是简单直观，容易判断两个顶点之间是否有边，并且在获取某个顶点的邻接顶点时，可以通过遍历一行（或一列）数组快速得到。然而，其缺点是对于稀疏图（边较少的图），会浪费大量的存储空间，因为大部分元素可能都是 MaxInt。
//邻接矩阵的结构体创建typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;  // 假设边的权值类型为整型
typedef struct { VerTexType   vexs[MVNum]; // 顶点表 ArcType     arcs[MVNum][MVNum]; // 邻接矩阵 int     vexnum, arcnum; // 图的当前顶点数和弧（边）数 GraphKind kind;//图的种类
} AMGraph;

邻接矩阵创建无向网以及其打印

//邻接矩阵创建无向网
Status CreateUDN(AMGraph &G){cout<<"所需点的个数：";cin>>G.vexnum;cout<<"所需边的个数：";cin>>G.arcnum;G.kind = UDN;//无向网//输入顶点的信息cout<<"请依次输入顶点信息"<<endl;for(int i = 0;i<G.vexnum;i++){cout<<"第"<<i+1<<"个：";cin>>G.vexs[i];}//初始化邻接矩阵for(int i=0;i<G.vexnum ;i++) 	 //初始化邻接矩阵for(int j=0;j<G.vexnum ;j++) 	G.arcs[i][j]=MaxInt;//输入边的信息cout<<"请依次输入边的信息"<<endl;cout<<"输入格式 点v1 点v2 边长度a"<<endl;for(int i = 0;i<G.arcnum;i++){VerTexType v1,v2;ArcType a;cout<<"第"<<i+1<<"个：";cin>>v1>>v2>>a;Edges[i].Head = v1;Edges[i].Tail = v2;Edges[i].lowcost = a;int m = Locate(G,v1),n = Locate(G,v2);G.arcs[m][n] = G.arcs[n][m] = a;//构建边成功}return OK;
}
//打印邻接矩阵内容
void PrintUDN(AMGraph &G){cout<<"vexnum："<<G.vexnum<<"\tarcnum："<<G.arcnum<<endl<<endl;cout<<"\t";for(int i = 0 ;i<G.arcnum;i++)cout<<G.vexs[i]<<"\t";cout<<endl;for(int i = 0;i<G.vexnum;i++){cout<<G.vexs[i]<<"\t";for(int j = 0;j<G.vexnum;j++){if(G.arcs[i][j] == MaxInt) cout<<"∞\t";else cout<<G.arcs[i][j]<<"\t";}cout<<endl;}	
}

（二）邻接表

  1. 定义与原理
    • 邻接表是一种链式存储结构，它为图中的每个顶点建立一个单链表，链表中的节点表示与该顶点相邻接的顶点。每个链表节点包含两个部分：邻接顶点的下标 adjvex 和指向下一个邻接顶点节点的指针 nextarc。对于有权图，还可以在节点中添加一个字段来存储边的权重信息 info。
  2. 代码实现与分析
    • 在代码中的 ALGraph 结构体定义了邻接表。vertices 是一个数组，每个元素是一个 VNode 结构体，代表一个顶点。VNode 结构体中的 firstarc 指针指向该顶点的邻接顶点链表的头节点。在 CreateDG 函数中，通过头插法创建邻接表。当输入一条边 v1 到 v2 时，先找到 v1 和 v2 对应的顶点下标 i 和 j，然后创建一个新的边节点 p，将其 adjvex 设置为 j，并将 p 插入到顶点 i 的邻接顶点链表的头部，即 p->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p;。邻接表的优点是对于稀疏图能够节省存储空间，只存储实际存在的边。其缺点是在判断两个顶点之间是否有边时，需要遍历相应顶点的邻接链表，效率相对较低，不如邻接矩阵直接通过数组下标访问那么快速。
//邻接表的相关结构体创建typedef enum {DG, DN, UDG, UDN} GraphKind;  
//{有向图，有向网，无向图，无向网} 
typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;  // 假设边的权值类型为整型typedef struct ArcNode {//边结点int   adjvex; 	// 该弧(边)所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边InfoType   *info; 	 //和边相关的信息	
} ArcNode; typedef struct VNode {//表头结点VerTexType   data; 	// 顶点信息 ArcNode       *firstarc; // 指向第一条依附该顶点的弧(边) 
} VNode, AdjList[MVNum]; typedef struct { AdjList   vertices; 	//顶点数组 int   vexnum, arcnum; // 图的当前顶点数和弧(边)数GraphKind kind;//图的种类 
} ALGraph;

邻接表创建有向网及其打印

//邻接表创建有向网
Status CreateDG(ALGraph &G){cout<<"所需点的个数：";cin>>G.vexnum;cout<<"所需边的个数：";cin>>G.arcnum;G.kind = DG;//有向网//输入顶点的信息//构造头节点cout<<"请依次输入顶点信息"<<endl;for(int i = 0;i<G.vexnum;i++){cout<<"第"<<i+1<<"个：";cin>>G.vertices[i].data;G.vertices[i].firstarc = nullptr;}//边的信息 采用头插法cout<<"请依次输入边的信息"<<endl;cout<<"输入格式 点v1 点v2"<<endl;for(int k = 0;k<G.arcnum;k++){VerTexType v1,v2;
//		ArcType a;cin>>v1>>v2;int i = Locate(G,v1);int j = Locate(G,v2);ArcNode* p = new ArcNode;//新的边节点p->adjvex = j;//边指向的顶点的序号//头插法//p的下一个边改成第i个点后依附的第一条弧p->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p;}return OK;
}
//打印邻接表
void PrintDG(ALGraph &G) {for (int i = 0; i < G.vexnum; i++) {cout << "[" << G.vertices[i].data << "]";ArcNode* p = G.vertices[i].firstarc;while (p!= nullptr) {int t = p->adjvex;cout << "->" << p->adjvex << "("<< G.vertices[t].data<<")";p = p->nextarc;}cout << endl;}
}

四、图的遍历

（一）深度优先遍历（DFS）

  1. 原理与算法流程
    • 深度优先遍历的基本思想是从图中的某个顶点 v 出发，访问该顶点，然后递归地遍历与 v 相邻接且未被访问过的顶点，直到所有与 v 有路径相通的顶点都被访问到。如果图中还有未被访问的顶点，则任选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问过。
  2. 代码实现与分析（以邻接矩阵为例）
    • 在 dfs 函数中，首先输出当前顶点 G.vexs[v]，并将其标记为已访问 visited[v] = true。然后通过一个循环遍历所有顶点，如果 G.arcs[v][w]!= MaxInt 表示顶点 v 和顶点 w 之间有边相连，且顶点 w 未被访问过，则递归调用 dfs(G, w) 继续深度优先遍历。这种递归的方式能够沿着一条路径尽可能深地访问顶点，直到无法继续，然后回溯到上一个顶点，继续探索其他未被访问的路径。时间复杂度为 O ( V 2 ) O(V^2) O(V2)，其中 V 是图的顶点数，因为对于每个顶点都可能需要遍历所有其他顶点来判断是否有边相连。空间复杂度为 O ( V ) O(V) O(V)，主要是用于存储递归调用栈和标记数组 visited。
//邻接矩阵构造无向网的DFS
bool visited[MVNum];
void dfs(AMGraph &G,int v){cout<<G.vexs[v];visited[v] = true;for(int w = 0;w<G.vexnum;w++){if(G.arcs[v][w]!=MaxInt&&!visited[w])dfs(G,w);}
}

//邻接表构造有向网的DFS
bool visited[MVNum];
void dfs(ALGraph &G,int v){cout<<G.vertices[v].data;visited[v] = true;ArcNode *p = G.vertices[v].firstarc;while(p!=nullptr){int w = p->adjvex;//p的周围的点的下标if(!visited[w]) dfs(G,w);//第w个点未被访问 =>访问下p = p->nextarc;}
}

（二）广度优先遍历（BFS）

  1. 原理与算法流程
    • 广度优先遍历的基本思想是从图中的某个顶点 v 出发，先访问该顶点，然后依次访问与 v 相邻接的所有未被访问过的顶点，再按照这些顶点被访问的先后顺序，依次访问它们相邻接的未被访问过的顶点，直到图中所有顶点都被访问过。它类似于层次遍历，先访问距离起始顶点最近的一层顶点，然后再依次访问距离更远的层次的顶点。
  2. 代码实现与分析（以邻接矩阵为例）
    • 在 bfs 函数中，首先将所有顶点标记为未访问。然后将起始顶点 v 标记为已访问并输出，将其下标放入队列 Q 中。在循环中，当队列不为空时，取出队首元素 u，并遍历所有顶点。如果顶点 u 和顶点 v 之间有边相连且顶点 v 未被访问过，则将顶点 v 标记为已访问并输出，然后将其下标放入队列 Q 中。这样可以保证按照距离起始顶点的层次顺序依次访问顶点。时间复杂度为 O ( V 2 ) O(V^2) O(V2)，与深度优先遍历类似，因为都需要遍历邻接矩阵。空间复杂度为 O ( V ) O(V) O(V)，主要用于存储队列和标记数组 visited。
//邻接矩阵构造无向网的BFS
//广度优先搜索
void bfs(AMGraph &G) {for (int i = 0; i < G.vexnum; i++) {visited[i] = false;}queue<int> Q;for (int i = 0; i < G.vexnum; i++) {if (!visited[i]) {visited[i] = true;cout << G.vexs[i];Q.push(i);while (!Q.empty()) {int u = Q.front();Q.pop();for (int v = 0; v < G.vexnum; v++) {if (G.arcs[u][v]!= MaxInt &&!visited[v]) {visited[v] = true;cout << G.vexs[v];Q.push(v);}}}}}
}

//邻接表构造有向网的BFS
void bfs(ALGraph &G){for (int i = 0; i < G.vexnum; i++) {visited[i] = false;}queue<int> Q;for(int i =0;i<G.vexnum;i++){if(!visited[i]){visited[i] = true;cout<<G.vertices[i].data;Q.push(i);while(!Q.empty()){int u = Q.front();//Q存放的是下标Q.pop();ArcNode *p = G.vertices[u].firstarc;while(p!=nullptr){if(!visited[p->adjvex]){visited[p->adjvex] = true;cout<<G.vertices[p->adjvex].data;Q.push(p->adjvex);}p = p->nextarc;}}}}
}

五、最小生成树

（一）Prim 算法

  1. 原理与算法流程

    • Prim 算法的基本思想是从图中的任意一个顶点开始，逐步构建最小生成树。首先将起始顶点加入到最小生成树的顶点集合 (U) 中，然后在集合 (U) 和集合 (V - U)（(V) 是图的所有顶点集合）之间的边中，选择一条权值最小的边，将这条边的另一个顶点加入到集合 (U) 中。重复这个过程，直到集合 (U) 包含了图中的所有顶点。在这个过程中，需要维护一个数组 (lowcost) 来记录集合 (V - U) 中每个顶点到集合 (U) 中顶点的最小权值边的权值，以及一个数组 (vset) 来标记顶点是否已经加入到集合 (U) 中。
      -Prim算法 又叫加边法 实现流程如图所示在这里插入图片描述

  2. 代码实现与分析（以邻接矩阵为例）

    • 在 Prim 函数中，首先进行初始化。将起始顶点 v0 加入到集合 U 中，即 vset[v] = 1，并将与起始顶点相邻接的顶点的 lowcost 值设置为相应边的权值 lowcost[i] = G.arcs[v][i]。然后在循环中，找到 lowcost 数组中的最小值 min，其对应的顶点 k 就是要加入到集合 U 中的顶点。输出加入的边 G.vexs[prevV] - G.vexs[v] : lowcost[v]，并更新 prevV = v 和 v = k。接着，对于集合 (V - U) 中的顶点，如果通过新加入的顶点 v 到该顶点的边权值更小，就更新 lowcost 数组的值。时间复杂度为 (O(V^2))，其中 (V) 是图的顶点数，因为在每次选择最小权值边时，都需要遍历 lowcost 数组来找到最小值，这个过程的时间复杂度为 (O(V))，而总共需要进行 (V - 1) 次这样的选择操作。空间复杂度为 (O(V))，主要用于存储 lowcost、vset 和其他辅助变量。
//求最小生成树
void Prim(AMGraph &G,int v0){cout<<"利用Prim算法构建最小生成树所加入的边是"<<endl;//初始化int v = v0;int k ;//存放最小的权值的下标int vset[MVNum];//存放在U中的点的下标ArcType lowcost[MVNum];//存放权值for(int i = 0;i<G.vexnum;i++){lowcost[i] = G.arcs[v][i];//存放每个点到v的权值vset[i] = 0;//点都还未进U 所以都是0}vset[v] = 1;//首先把第一个点存进去for(int i = 0;i<G.vexnum - 1;i++){//剩余的其他几个节点遍历,依次存入U 共需要遍历n-1次//找lowcost的最小点int min = MaxInt;for(int j = 0;j<G.vexnum;j++){if(min>lowcost[j] && vset[j] == 0){//找未在U中的最小值min = lowcost[j];//找最小值k = j;//更新最小值对应点的下标(k点要存进U中去)}}vset[k] = 1;//第k个点存进Uint prevV = v;//存入边的起点v = k;//更新v为k  此时v为存入的边的终点cout << G.vexs[prevV] << " - " << G.vexs[v] << " : " << lowcost[v] << endl;//更新lowcost  只是更新值 不会显露lowcost的来源信息 就是v->w，v,w不知for(int j = 0;j<G.vexnum;j++){if(vset[j] == 0 && G.arcs[v][j]<lowcost[j]){lowcost[j] = G.arcs[v][j];}}}
}

（二）Kruskal 算法

  1. 原理与算法流程

    • Kruskal 算法的基本思想是将图中的所有边按照权值从小到大进行排序，然后依次选择边。如果选择的边不会形成环，就将其加入到最小生成树中，直到选择了 (V - 1) 条边为止，其中 (V) 是图的顶点数。为了判断选择的边是否会形成环，使用了并查集数据结构，通过维护一个数组 Vexset 来记录每个顶点所属的连通分量。
      Kruskal算法又叫加点法 实现流程如图所示
    • 在这里插入图片描述

  2. 代码实现与分析（以邻接矩阵为例，结合辅助数组 Edges）

    • 在 Kruskal 函数中，首先将辅助数组 Edges 按照边的权值进行排序，这可以通过调用 sort 函数并传入自定义的比较函数 compareEdges 来实现。然后初始化并查集数组 Vexset，使得每个顶点的初始连通分量为其自身下标。接着遍历排序后的边数组，对于每条边，找到其两个顶点在 Vexset 中的连通分量 vs1 和 vs2。如果 vs1!= vs2，说明这条边不会形成环，将其加入到最小生成树中，并输出该边信息 Edges[i].Head - Edges[i].Tail : Edges[i].lowcost，然后通过更新 Vexset 数组来合并两个连通分量。时间复杂度主要取决于边的排序操作，一般为 (O(E log E))，其中 (E) 是图的边数，以及并查集操作的时间复杂度，在优化较好的情况下可以接近线性时间。空间复杂度为 (O(E))，主要用于存储辅助数组 Edges 和并查集数组 Vexset。
// 比较函数，用于指定按照lowcost进行排序
bool compareEdges(const Edge& a, const Edge& b) {return a.lowcost < b.lowcost;
}
void Kruskal(AMGraph &G){cout<<"利用Kruskal算法构建最小生成树加入的边是"<<endl;//辅助数组 用祖先的所在位置表示所在连通分量//如果某条选取边的起点终点的Vexset值相等 则不能加进去//加进去会使得成环int Vexset[MVNum];sort(Edges,Edges+G.arcnum,compareEdges);//边按照权值排序for(int i = 0;i<G.arcnum;i++){Vexset[i] = i;}//遍历所有边for(int i = 0;i<G.arcnum;i++){//找当前边的下标int v1 = Locate(G,Edges[i].Head);int v2 = Locate(G,Edges[i].Tail);//当前边的首尾节点所在的连通分量vs1,vs2int vs1 = Vexset[v1];int vs2 = Vexset[v2];if(vs1!=vs2){//说明成不了环 输出cout<<Edges[i].Head<<" - "<<Edges[i].Tail<<": "<<Edges[i].lowcost<<endl;//合并vs1,vs2(并查集操作)for(int j = 0;j<G.arcnum;j++){if(Vexset[j] == vs2){Vexset[j] = vs1;//vs2合并为vs1}}}}}

六、最短路径

（一）Djikstra 算法

  1. 原理与算法流程

    • Djikstra 算法用于计算带权有向图中一个顶点到其他所有顶点的最短路径。其基本思想是从起始顶点开始，逐步确定到其他顶点的最短路径。首先将起始顶点到自身的距离设置为 (0)，到其他顶点的距离设置为无穷大（在代码中用 MaxInt 表示），然后将起始顶点标记为已确定最短路径的顶点。在每次迭代中，选择一个未确定最短路径且距离起始顶点最近的顶点 (v)，将其标记为已确定，并更新与 (v) 相邻接的顶点到起始顶点的距离（如果通过 (v) 到达这些顶点的距离更短）。重复这个过程，直到所有顶点都被确定了最短路径。
      在这里插入图片描述

  2. 代码实现与分析（以邻接矩阵为例）

    • 在 Dijkstra 函数中，初始化部分包括设置标记数组 S、路径数组 Path 和距离数组 Dist。将起始顶点 v0 的相关信息初始化，即 S[v0] = true，Dist[v0] = 0，并根据邻接矩阵设置其他顶点到起始顶点的初始距离和路径信息。然后在循环中，找到未确定最短路径且距离起始顶点最近的顶点 v，将其标记为已确定 S[v] = true。接着更新与 v 相邻接的顶点的距离和路径信息，如果 Dist[i] > Dist[v] + G.arcs[i][v]，则更新 Dist[i] = Dist[v] + G.arcs[i][v] 和 Path[i] = v。最后，通过 PrintPath_Dijkstra 函数输出从起始顶点到每个顶点的最短路径及其长度。时间复杂度为 (O(V^2))，因为在每次迭代中都需要遍历所有顶点来找到未确定最短路径且距离最近的顶点，以及更新相邻接顶点的距离。空间复杂度为 (O(V))，用于存储标记数据 S、路径数组 Path 和距离数组 Dist。
      Dijkstra算法及其最短路径的打印
void PrintPath_Dijkstra(AMGraph &G,int start,int end,int Path[]){cout<<"从"<<G.vexs[start]<<"到"<<G.vexs[end]<<"的最短路径：";int current = end;//倒着存放路径stack<int>pathStack;while(current != start){pathStack.push(current);current = Path[current];}pathStack.push(start);VerTexType temp =  G.vexs[pathStack.top()];pathStack.pop();if(!pathStack.empty()) cout<<temp;while(!pathStack.empty()){cout<<"->"<<G.vexs[pathStack.top()];pathStack.pop();}
}
void Dijkstra(AMGraph &G,int v0){cout<<"利用Dijkstra算法计算得 "<<G.vexs[v0]<<" 到各点的最短路径的信息如下"<<endl;//----初始化----bool S[G.vexnum];//存放已经存的顶点int Path[G.vexnum];//存放自起点来的在最短路径里面的点的下标int Dist[G.vexnum];//存放自起点来的最短路径的长度int n = G.vexnum;for(int i = 0;i<n;i++){S[i] = false;//都还未存入Dist[i] = G.arcs[v0][i];if(Dist[i]!=MaxInt){Path[i] = v0;}else{Path[i] = -1;}}S[v0] = true;//起点存入Dist[v0] = 0;//起点到自身的距离//----初始化完毕----for(int i = 1;i<n;i++){//剩余n-1个点int min = MaxInt;int v;//未加入S的点中找最小值for(int i = 0;i<n;i++){if(!S[i] && Dist[i]<min){v = i;//所找到的最短路径中一段的终点min = Dist[i];//最小值}}S[v] = true;//v0->v的最短路径已找到 加入进去for(int i = 0;i<n;i++){if(Dist[i]>Dist[v]+G.arcs[i][v]){//找到更短的边时 加入Dist[i] = Dist[v] + G.arcs[i][v];Path[i] = v;}}}//输出到每个点的最短路径for(int i = 0;i<n;i++){if(i != v0){ //消除自身到自身的路径PrintPath_Dijkstra(G,v0,i,Path);cout<<"\t路径长度为"<<Dist[i]<<endl;}}
}

（二）Floyd 算法

  1. 原理与算法流程

    • Floyd 算法用于计算带权有向图中所有顶点对之间的最短路径。其基本思想是通过动态规划的方法，逐步考虑加入中间顶点来更新两点之间的最短路径。首先初始化一个二维数组 Dist 来存储顶点之间的初始距离（直接距离或无穷大），以及一个二维数组 Path 来存储最短路径中每个顶点的前驱顶点。然后，对于每一个可能的中间顶点 k，遍历所有顶点对 i 和 j，如果通过中间顶点 k 可以使 i 到 j 的路径更短，即 Dist[i][j] > Dist[i][k] + Dist[k][j]，则更新 Dist[i][j] 和 Path[i][j]。经过 (n) 次迭代（(n) 为图的顶点数）后，Dist 数组就存储了所有顶点对之间的最短路径长度，Path 数组可以用于回溯最短路径。
      在这里插入图片描述

  2. 代码实现与分析（以邻接矩阵为例）

    • 在 Floyd 函数中，初始化 Dist 和 Path 数组，根据邻接矩阵设置初始距离和路径信息。然后通过三重循环进行迭代，外层循环控制中间顶点 k，中层循环遍历起始顶点 i，内层循环遍历终点顶点 j。在每次迭代中，如果发现通过中间顶点 k 可以优化 i 到 j 的最短路径，就更新 Dist[i][j] 和 Path[i][j]。最后，输出经过 (n) 次迭代后的 Dist 和 Path 数组的结果。时间复杂度为 (O(V^3))，因为有三重循环，分别遍历所有顶点作为中间顶点、起始顶点和终点顶点。空间复杂度为 (O(V^2))，用于存储 Dist 和 Path 数组。
      Floyd算法及其辅助数组的打印
void Floyd(AMGraph &G){int n = G.vexnum;int Path[MVNum][MVNum];int Dist[n][n];for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){Dist[i][j] = G.arcs[i][j];if(Dist[i][j]!=MaxInt && i!=j){//i 和 j 之间有弧 将j的前驱置为 iPath[i][j] = i;//说明从i到j的最短路径的终点的前一个点是i}else Path[i][j] = -1;}}for(int k = 0;k<n;k++){for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){if(Dist[i][j]>Dist[i][k]+Dist[k][j]){//每个点都当一次中间点 最后得到最短路径Dist[i][j] = Dist[i][k]+Dist[k][j];Path[i][j] = Path[k][j];//因为Path[i][j]代表的是i 到 j的最短路径的终点的前一个点的下标//所以更改为中间点}}}}//打印出来D(n-1)和Path(n-1)的内容cout<<"通过Floyd算法"<<endl;cout<<"经过 "<<n<<" 次迭代后"<<endl;cout<<"D"<<(n-1)<<"和Path"<<(n-1)<<"的结果如下所示"<<endl;cout<<"\nD("<<n-1<<")：\n"<<endl;for(int i = 0;i<n;i++){if(i==0)cout<<"\t";cout<<"("<<G.vexs[i]<<")"<<"\t";}cout<<endl;for(int i = 0;i<n;i++){cout<<"("<<G.vexs[i]<<")"<<"\t";for(int j = 0;j<n;j++){cout<<Dist[i][j]<<"\t";}cout<<endl;}cout<<"\nPath("<<n-1<<")：\n"<<endl;for(int i = 0;i<n;i++){if(i==0)cout<<"\t";cout<<"("<<G.vexs[i]<<")"<<"\t";}cout<<endl;for(int i = 0;i<n;i++){cout<<"("<<G.vexs[i]<<")"<<"\t";for(int j = 0;j<n;j++){cout<<Path[i][j]<<"\t";}cout<<endl;}}

七、拓扑排序

（一）原理与算法流程

  • 拓扑排序用于有向无环图（DAG），其目的是将图中的顶点排成一个线性序列，使得对于图中的任意一条有向边((u, v))，顶点(u)在序列中都排在顶点(v)之前。其基本思想是通过计算每个顶点的入度，然后将入度为(0)的顶点依次加入到排序结果中，并删除这些顶点及其出边，同时更新剩余顶点的入度。重复这个过程，直到所有顶点都被加入到排序结果中或者发现图中存在环（如果还有顶点未被处理且其入度不为(0)）。

（二）代码实现与分析（以邻接表为例）

  1. 计算入度

    • 在FindIndegree函数中，首先初始化一个数组indegree，将所有顶点的入度设置为(0)。然后遍历邻接表，对于每个顶点的邻接边，将其指向顶点的入度加(1)。例如，当遍历到顶点(i)的邻接边节点(p)时，执行indegree[p->adjvex]++，这样就正确计算出了每个顶点的入度。时间复杂度为(O(V + E))，其中(V)是图的顶点数，(E)是图的边数，因为需要遍历所有顶点和边来计算入度。

  2. 拓扑排序过程

    • 在TopologicalSort函数中，先调用FindIndegree函数计算入度并将结果存储在indegree数组中。接着创建一个栈(S)，将入度为(0)的顶点入栈。然后进入循环，当栈不为空时，弹出栈顶顶点(i)，将其加入拓扑排序结果数组topo中，并更新其邻接顶点的入度。如果某个邻接顶点的入度变为(0)，则将其入栈。如果最终topo数组中的顶点数量小于图中的顶点数量(G.vexnum)，说明图中存在环，返回ERROR；否则返回OK。时间复杂度为(O(V + E))，因为在最坏情况下，每个顶点和边都可能被处理一次。空间复杂度为(O(V))，主要用于存储入度数组indegree、栈(S)和拓扑排序结果数组topo。
      流程示意图如图所示
      在这里插入图片描述
      代码实现如下
//拓扑排序
void FindIndegree(ALGraph &G,int *indegree){//求每个点的入度for(int i = 0;i<G.vexnum;i++){indegree[i] = 0;//初始化}for(int i = 0;i<G.vexnum;i++){ArcNode * p = G.vertices[i].firstarc;while(p != NULL){//为什么写while(!p)就运行不了indegree[p->adjvex] ++;p = p->nextarc;}}
}
Status TopologicalSort(ALGraph &G,int topo[]){int indegree[G.vexnum];FindIndegree(G,indegree);//入度个数存放完毕stack<int> S;for(int i = 0;i<G.vexnum;i++){if(indegree[i] == 0){//入度为0的点S.push(i);}}int m = 0;while(!S.empty()){//度为0的点int i = S.top();S.pop();topo[m] = i; m++;//拓扑排序依次存入 m自增ArcNode * p = G.vertices[i].firstarc;while(p!=NULL){//删除度为0的点的出度对其他点的影响indegree[p->adjvex] -- ;if(indegree[p->adjvex]==0) S.push(p->adjvex);//如果该点入度为0 则入栈p = p->nextarc;}}if(m<G.vexnum) return ERROR;//m不到G.vexnum 说明有环else return OK;
}

八、关键路径

(一) 原理与算法流程

关键路径算法用于在有向无环图（DAG）中确定项目的最短完成时间以及关键活动序列。其核心原理基于事件的最早发生时间和最迟发生时间的计算。

首先，通过拓扑排序确定图中顶点的一个线性序列。因为只有在拓扑排序可行（即图无环）的前提下才能进行关键路径分析。然后，按照拓扑序列依次计算每个事件的最早发生时间（ve）。从起始事件开始，其最早发生时间初始化为(0)，对于其他事件，其最早发生时间是其所有前驱事件的最早发生时间加上相应活动持续时间的最大值。这意味着一个事件必须在其所有前驱活动都完成后才能开始，取最大值是因为要等待最长的前驱路径完成。

接着，计算每个事件的最迟发生时间（vl）。从最后一个事件开始，其最迟发生时间等于其最早发生时间，然后对于其他事件，其最迟发生时间是其所有后继事件的最迟发生时间减去相应活动持续时间的最小值。这保证了在不影响整个项目最短完成时间的前提下，每个事件可以最晚开始的时间。

最后，通过比较每个活动的最早开始时间（等于其起始事件的最早发生时间）和最迟开始时间（等于其终止事件的最迟发生时间减去活动持续时间），若两者相等，则该活动为关键活动，由所有关键活动构成的路径即为关键路径。关键路径决定了整个项目的最短完成时间，因为关键路径上的任何活动延迟都会导致项目整体延迟。

(二) 代码的实现与分析

1.拓扑排序部分
在TopologicalOrder函数中：

  • 先调用FindInDegree函数计算各顶点入度并存入indegree数组，然后初始化空栈S。
  • 遍历顶点，将入度为(0)的顶点入栈。
  • 进入循环，当栈非空时，弹出栈顶顶点i存入topo数组，对其邻接顶点处理：邻接顶点k入度减(1)，若入度变为(0)则入栈。
  • 循环结束后，根据topo数组中顶点数量与图顶点数比较判断是否有回路并返回相应结果。
    这部分代码为关键路径计算提供了正确的顶点处理顺序基础，时间复杂度为(O(V + E))，空间复杂度主要取决于栈和入度数组，为(O(V))。

2.关键路径计算部分
在CriticalPath函数中：

  • 先调用TopologicalOrder函数获取拓扑序列，失败则返回ERROR。
  • 初始化ve数组为(0)，按拓扑次序遍历顶点，通过邻接边更新后继顶点的ve值，取最大值确保正确计算最早发生时间。
  • 初始化vl数组为最后顶点的ve值，按逆拓扑次序遍历顶点，通过邻接边更新当前顶点的vl值，取最小值确保正确计算最迟发生时间。
  • 最后遍历顶点及其邻接顶点，计算活动的最早开始时间e和最迟开始时间l，若相等则输出关键活动对应的顶点关系。
    整体时间复杂度为(O(V + E))，主要源于对顶点和边的多次遍历，空间复杂度为(O(V))，用于存储ve、vl和topo等数组。代码通过合理的数据结构和循环逻辑，准确地实现了关键路径算法的功能，在项目规划与管理等领域有重要应用价值。
    实现流程如下
    在这里插入图片描述
//关键路径算法#include <iostream>
using namespace std;#define MVNum 100                       	//最大顶点数
#define BDNum MVNum * (MVNum - 1)			//最大边数
#define OK 1	
#define ERROR 0 typedef char VerTexType;//- - - - -图的邻接表存储表示- - - - - 
typedef struct ArcNode{                		//边结点 int adjvex;                          	//该边所指向的顶点的位置int weight;								//权值struct ArcNode *nextarc;          		//指向下一条边的指针 
}ArcNode; typedef struct VNode{ VerTexType data;                    	//顶点信息ArcNode *firstarc;                		//指向第一条依附该顶点的边的指针 
}VNode, AdjList[MVNum];               		//AdjList表示邻接表类型 typedef struct{ AdjList vertices;                 		//邻接表 AdjList converse_vertices;				//逆邻接表int vexnum, arcnum;              		//图的当前顶点数和边数 
}ALGraph;
//- - - - - - - - - - - - - - - -//- - - - -顺序栈的定义- - - - -
typedef struct{int *base;int *top;int stacksize;
}spStack;
//- - - - - - - - - - - - - - - -int indegree[MVNum];						//数组indegree存放个顶点的入度
int ve[BDNum];								//事件vi的最早发生时间
int vl[BDNum];								//事件vi的最迟发生时间
int topo[MVNum];							//记录拓扑序列的顶点序号
spStack S;//----------------栈的操作--------------------
void InitStack(spStack &S){//栈的初始化S.base = new int[MVNum];if(!S.base)exit(1);S.top = S.base;S.stacksize = MVNum;
}//InitStackvoid Push(spStack &S , int i){//入栈if(S.top - S.base == S.stacksize)return;*S.top++ = i;
}//Pushvoid Pop(spStack &S , int &i){//出栈if(S.top == S.base)return;i = *--S.top;
}//Popbool StackEmpty(spStack S){//判断栈是否为空if(S.top == S.base)return true;return false;
}//StackEmpty
//---------------------------------------int LocateVex(ALGraph G , VerTexType v){//确定点v在G中的位置for(int i = 0; i < G.vexnum; ++i)if(G.vertices[i].data == v)return i;return -1;
}//LocateVexint CreateUDG(ALGraph &G){ //创建有向图G的邻接表、逆邻接表int i , k;cout <<"请输入总顶点数，总边数，以空格隔开:";cin >> G.vexnum >> G.arcnum;				//输入总顶点数，总边数 cout << endl;cout << "输入点的名称，如a" << endl;for(i = 0; i < G.vexnum; ++i){          		//输入各点，构造表头结点表cout << "请输入第" << (i+1) << "个点的名称:";cin >> G.vertices[i].data;           		//输入顶点值G.converse_vertices[i].data = G.vertices[i].data;//初始化表头结点的指针域为NULL G.vertices[i].firstarc=NULL;			G.converse_vertices[i].firstarc=NULL;}//forcout << endl;cout << "输入边依附的顶点及其权值，如a b 3" << endl;for(k = 0; k < G.arcnum;++k){        			//输入各边，构造邻接表VerTexType v1 , v2;int i , j , w;cout << "请输入第" << (k + 1) << "条边依附的顶点及其权值:";cin >> v1 >> v2 >> w;                		//输入一条边依附的两个顶点i = LocateVex(G, v1);  j = LocateVex(G, v2);//确定v1和v2在G中位置，即顶点在G.vertices中的序号 ArcNode *p1=new ArcNode;               		//生成一个新的边结点*p1 p1->adjvex=j;                   			//邻接点序号为jp1->nextarc = G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;p1->weight = w;//将新结点*p1插入顶点vi的边表头部ArcNode *p2=new ArcNode;               		//生成一个新的边结点*p1 p2->adjvex=i;                   			//逆邻接点序号为ip2->nextarc = G.converse_vertices[j].firstarc;  G.converse_vertices[j].firstarc=p2;p2->weight = w;//将新结点*p1插入顶点vi的边表头部}//for return OK; 
}//CreateUDGvoid FindInDegree(ALGraph G){//求出各顶点的入度存入数组indegree中 int i , count;for(i = 0 ; i < G.vexnum ; i++){count = 0;ArcNode *p = G.converse_vertices[i].firstarc;if(p){while(p){p = p->nextarc;count++;}}//ifindegree[i] = count;}//for
}//FindInDegreeint TopologicalOrder(ALGraph G , int topo[]){ //有向图G采用邻接表存储结构 //若G无回路，则生成G的一个拓扑序列topo[]并返回OK，否则ERROR int i , m;FindInDegree(G);              				//求出各顶点的入度存入数组indegree中 InitStack(S);                          		//栈S初始化为空 for(i = 0; i < G.vexnum; ++i)if(!indegree[i]) Push(S, i);     		//入度为0者进栈 m = 0;                               		//对输出顶点计数，初始为0 while(!StackEmpty(S)){                		//栈S非空 Pop(S, i);                          	//将栈顶顶点vi出栈topo[m]=i;                         		//将vi保存在拓扑序列数组topo中 ++m;                             		//对输出顶点计数 ArcNode *p = G.vertices[i].firstarc;    //p指向vi的第一个邻接点 while(p){int k = p->adjvex;					//vk为vi的邻接点   --indegree[k];                   	//vi的每个邻接点的入度减1 if(indegree[k] ==0)  Push(S, k);	//若入度减为0，则入栈 p = p->nextarc;                		//p指向顶点vi下一个邻接结点 }//while }//whileif(m < G.vexnum)  return ERROR;    			//该有向图有回路 else return OK;
}//TopologicalOrderint CriticalPath(ALGraph G){ //G为邻接表存储的有向网，输出G的各项关键活动int n , i , k , j , e , l;if (!TopologicalOrder(G, topo))  return ERROR; //调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR n = G.vexnum;                  				//n为顶点个数 for(i = 0; i < n; i++)               		//给每个事件的最早发生时间置初值0 ve[i] = 0; /*――――――――――按拓扑次序求每个事件的最早发生时间－――――－―――――*/ for(i = 0;i < n; i++){                 k = topo[i];                   			//取得拓扑序列中的顶点序号k             ArcNode *p = G.vertices[k].firstarc;    //p指向k的第一个邻接顶点  while(p != NULL){            			//依次更新k的所有邻接顶点的最早发生时间   j = p->adjvex;               		//j为邻接顶点的序号                   if(ve[j] < ve[k] + p->weight)    	//更新顶点j的最早发生时间ve[j] ve[j] = ve[k] + p->weight;     p = p->nextarc;              		//p指向k的下一个邻接顶点  } //while } //for for(i=0;i<n;i++)                 			//给每个事件的最迟发生时间置初值ve[n-1] vl[i]=ve[n-1];/*――――――――――按逆拓扑次序求每个事件的最迟发生时间－――――－―――――*/ for(i = n - 1;i >= 0; i--){               k = topo[i];                   			//取得拓扑序列中的顶点序号k             ArcNode *p = G.vertices[k].firstarc;    //p指向k的第一个邻接顶点  while(p != NULL){            			//根据k的邻接点，更新k的最迟发生时间   j = p->adjvex;              		//j为邻接顶点的序号                   if(vl[k] > vl[j] - p->weight)    	//更新顶点k的最迟发生时间vl[k] vl[k] = vl[j] - p->weight;       p = p->nextarc;              		//p指向k的下一个邻接顶点  }//while }//for /*――――――――――――判断每一活动是否为关键活动－――――――－―――――*/cout << endl;cout << "关键活动路径为:";for(i = 0;i < n; i++){                		//每次循环针对vi为活动开始点的所有活动 ArcNode *p = G.vertices[i].firstarc;    //p指向i的第一个邻接顶点  while(p != NULL) {    j = p->adjvex;             			//j为i的邻接顶点的序号    e = ve[i];                 			//计算活动<vi, vj>的最早开始时间 l = vl[j] - p->weight;      		//计算活动<vi, vj>的最迟开始时间 if(e == l)               			//若为关键活动，则输出<vi, vj> cout << G.vertices[i].data << "-->" << G.vertices[j].data << " ";p = p->nextarc;              		//p指向i的下一个邻接顶点  } //while } //for  return OK;
}//CriticalPathint main(){cout << "************算法6.13　关键路径算法**************" << endl << endl;ALGraph G;CreateUDG(G);int *topo = new int [G.vexnum];cout << endl;cout << "有向图创建完成!" << endl << endl;if(!CriticalPath(G))cout << "网中存在环，无法进行拓扑排序！" <<endl << endl;cout << endl;return OK;
}//main

九、 代码汇总

邻接矩阵

/*
图的创建
深度优先遍历
广度优先遍历
最小生成树（Kruskal和Prim）
最短路径（Djikstra和Floyd)
*/#include<bits/stdc++.h>
using namespace std;#define MaxInt  32767       // 最大值∞ 
#define MVNum	 100		// 最大顶点数 
#define MAXSIZE 100 		//最大长度
#define OVERFLOw -2
#define OK 1
#define TeleType char
#define ERROR 0typedef int Status;
typedef enum {DG, DN, UDG, UDN} GraphKind;  
//{有向图，有向网，无向图，无向网} 
typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;  // 假设边的权值类型为整型
typedef struct { VerTexType   vexs[MVNum]; // 顶点表 ArcType     arcs[MVNum][MVNum]; // 邻接矩阵 int     vexnum, arcnum; // 图的当前顶点数和弧（边）数 GraphKind kind;//图的种类
} AMGraph;
//辅助数组 Edges定义
typedef struct Edge {VerTexType Head;//边的起点VerTexType Tail;//边的终点ArcType lowcost;//边的权值
}Edge;
Edge Edges[MVNum];//两个顶点的信息和权值
//确定顶点的位置
int Locate(AMGraph &G, VerTexType v){int t = -1;for(int i = G.vexnum-1;i>=0;i--){if(G.vexs[i] == v){t = i;}}return t;//return -1 相当于没找到
}//邻接矩阵创建无向网
Status CreateUDN(AMGraph &G){cout<<"所需点的个数：";cin>>G.vexnum;cout<<"所需边的个数：";cin>>G.arcnum;G.kind = UDN;//无向网//输入顶点的信息cout<<"请依次输入顶点信息"<<endl;for(int i = 0;i<G.vexnum;i++){cout<<"第"<<i+1<<"个：";cin>>G.vexs[i];}//初始化邻接矩阵for(int i=0;i<G.vexnum ;i++) 	 //初始化邻接矩阵for(int j=0;j<G.vexnum ;j++) 	G.arcs[i][j]=MaxInt;//输入边的信息cout<<"请依次输入边的信息"<<endl;cout<<"输入格式 点v1 点v2 边长度a"<<endl;for(int i = 0;i<G.arcnum;i++){VerTexType v1,v2;ArcType a;cout<<"第"<<i+1<<"个：";cin>>v1>>v2>>a;Edges[i].Head = v1;Edges[i].Tail = v2;Edges[i].lowcost = a;int m = Locate(G,v1),n = Locate(G,v2);G.arcs[m][n] = G.arcs[n][m] = a;//构建边成功}return OK;
}
//打印邻接矩阵内容
void PrintUDN(AMGraph &G){cout<<"vexnum："<<G.vexnum<<"\tarcnum："<<G.arcnum<<endl<<endl;cout<<"\t";for(int i = 0 ;i<G.arcnum;i++)cout<<G.vexs[i]<<"\t";cout<<endl;for(int i = 0;i<G.vexnum;i++){cout<<G.vexs[i]<<"\t";for(int j = 0;j<G.vexnum;j++){if(G.arcs[i][j] == MaxInt) cout<<"∞\t";else cout<<G.arcs[i][j]<<"\t";}cout<<endl;}	
}
bool visited[MVNum];
void dfs(AMGraph &G,int v){cout<<G.vexs[v];visited[v] = true;for(int w = 0;w<G.vexnum;w++){if(G.arcs[v][w]!=MaxInt&&!visited[w])dfs(G,w);}
}
//广度优先搜索
void bfs(AMGraph &G) {for (int i = 0; i < G.vexnum; i++) {visited[i] = false;}queue<int> Q;for (int i = 0; i < G.vexnum; i++) {if (!visited[i]) {visited[i] = true;cout << G.vexs[i];Q.push(i);while (!Q.empty()) {int u = Q.front();Q.pop();for (int v = 0; v < G.vexnum; v++) {if (G.arcs[u][v]!= MaxInt &&!visited[v]) {visited[v] = true;cout << G.vexs[v];Q.push(v);}}}}}
}
//求最小生成树
void Prim(AMGraph &G,int v0){cout<<"利用Prim算法构建最小生成树所加入的边是"<<endl;//初始化int v = v0;int k ;//存放最小的权值的下标int vset[MVNum];//存放在U中的点的下标ArcType lowcost[MVNum];//存放权值for(int i = 0;i<G.vexnum;i++){lowcost[i] = G.arcs[v][i];//存放每个点到v的权值vset[i] = 0;//点都还未进U 所以都是0}vset[v] = 1;//首先把第一个点存进去for(int i = 0;i<G.vexnum - 1;i++){//剩余的其他几个节点遍历,依次存入U 共需要遍历n-1次//找lowcost的最小点int min = MaxInt;for(int j = 0;j<G.vexnum;j++){if(min>lowcost[j] && vset[j] == 0){//找未在U中的最小值min = lowcost[j];//找最小值k = j;//更新最小值对应点的下标(k点要存进U中去)}}vset[k] = 1;//第k个点存进Uint prevV = v;//存入边的起点v = k;//更新v为k  此时v为存入的边的终点cout << G.vexs[prevV] << " - " << G.vexs[v] << " : " << lowcost[v] << endl;//更新lowcost  只是更新值 不会显露lowcost的来源信息 就是v->w，v,w不知for(int j = 0;j<G.vexnum;j++){if(vset[j] == 0 && G.arcs[v][j]<lowcost[j]){lowcost[j] = G.arcs[v][j];}}}
}
// 比较函数，用于指定按照lowcost进行排序
bool compareEdges(const Edge& a, const Edge& b) {return a.lowcost < b.lowcost;
}
void Kruskal(AMGraph &G){cout<<"利用Kruskal算法构建最小生成树加入的边是"<<endl;//辅助数组 用祖先的所在位置表示所在连通分量//如果某条选取边的起点终点的Vexset值相等 则不能加进去//加进去会使得成环int Vexset[MVNum];sort(Edges,Edges+G.arcnum,compareEdges);//边按照权值排序for(int i = 0;i<G.arcnum;i++){Vexset[i] = i;}//遍历所有边for(int i = 0;i<G.arcnum;i++){//找当前边的下标int v1 = Locate(G,Edges[i].Head);int v2 = Locate(G,Edges[i].Tail);//当前边的首尾节点所在的连通分量vs1,vs2int vs1 = Vexset[v1];int vs2 = Vexset[v2];if(vs1!=vs2){//说明成不了环 输出cout<<Edges[i].Head<<" - "<<Edges[i].Tail<<": "<<Edges[i].lowcost<<endl;//合并vs1,vs2(并查集操作)for(int j = 0;j<G.arcnum;j++){if(Vexset[j] == vs2){Vexset[j] = vs1;//vs2合并为vs1}}}}}
void PrintPath_Dijkstra(AMGraph &G,int start,int end,int Path[]){cout<<"从"<<G.vexs[start]<<"到"<<G.vexs[end]<<"的最短路径：";int current = end;//倒着存放路径stack<int>pathStack;while(current != start){pathStack.push(current);current = Path[current];}pathStack.push(start);VerTexType temp =  G.vexs[pathStack.top()];pathStack.pop();if(!pathStack.empty()) cout<<temp;while(!pathStack.empty()){cout<<"->"<<G.vexs[pathStack.top()];pathStack.pop();}
}
void Dijkstra(AMGraph &G,int v0){cout<<"利用Dijkstra算法计算得 "<<G.vexs[v0]<<" 到各点的最短路径的信息如下"<<endl;//----初始化----bool S[G.vexnum];//存放已经存的顶点int Path[G.vexnum];//存放自起点来的在最短路径里面的点的下标int Dist[G.vexnum];//存放自起点来的最短路径的长度int n = G.vexnum;for(int i = 0;i<n;i++){S[i] = false;//都还未存入Dist[i] = G.arcs[v0][i];if(Dist[i]!=MaxInt){Path[i] = v0;}else{Path[i] = -1;}}S[v0] = true;//起点存入Dist[v0] = 0;//起点到自身的距离//----初始化完毕----for(int i = 1;i<n;i++){//剩余n-1个点int min = MaxInt;int v;//未加入S的点中找最小值for(int i = 0;i<n;i++){if(!S[i] && Dist[i]<min){v = i;//所找到的最短路径中一段的终点min = Dist[i];//最小值}}S[v] = true;//v0->v的最短路径已找到 加入进去for(int i = 0;i<n;i++){if(Dist[i]>Dist[v]+G.arcs[i][v]){//找到更短的边时 加入Dist[i] = Dist[v] + G.arcs[i][v];Path[i] = v;}}}//输出到每个点的最短路径for(int i = 0;i<n;i++){if(i != v0){ //消除自身到自身的路径PrintPath_Dijkstra(G,v0,i,Path);cout<<"\t路径长度为"<<Dist[i]<<endl;}}
}void Floyd(AMGraph &G){int n = G.vexnum;int Path[MVNum][MVNum];int Dist[n][n];for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){Dist[i][j] = G.arcs[i][j];if(Dist[i][j]!=MaxInt && i!=j){//i 和 j 之间有弧 将j的前驱置为 iPath[i][j] = i;//说明从i到j的最短路径的终点的前一个点是i}else Path[i][j] = -1;}}for(int k = 0;k<n;k++){for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){if(Dist[i][j]>Dist[i][k]+Dist[k][j]){//每个点都当一次中间点 最后得到最短路径Dist[i][j] = Dist[i][k]+Dist[k][j];Path[i][j] = Path[k][j];//因为Path[i][j]代表的是i 到 j的最短路径的终点的前一个点的下标//所以更改为中间点}}}}//打印出来D(n-1)和Path(n-1)的内容cout<<"通过Floyd算法"<<endl;cout<<"经过 "<<n<<" 次迭代后"<<endl;cout<<"D"<<(n-1)<<"和Path"<<(n-1)<<"的结果如下所示"<<endl;cout<<"\nD("<<n-1<<")：\n"<<endl;for(int i = 0;i<n;i++){if(i==0)cout<<"\t";cout<<"("<<G.vexs[i]<<")"<<"\t";}cout<<endl;for(int i = 0;i<n;i++){cout<<"("<<G.vexs[i]<<")"<<"\t";for(int j = 0;j<n;j++){cout<<Dist[i][j]<<"\t";}cout<<endl;}cout<<"\nPath("<<n-1<<")：\n"<<endl;for(int i = 0;i<n;i++){if(i==0)cout<<"\t";cout<<"("<<G.vexs[i]<<")"<<"\t";}cout<<endl;for(int i = 0;i<n;i++){cout<<"("<<G.vexs[i]<<")"<<"\t";for(int j = 0;j<n;j++){cout<<Path[i][j]<<"\t";}cout<<endl;}}
int main(){AMGraph G;CreateUDN(G);PrintUDN(G);for(int i =0;i<G.vexnum;i++){visited[i] = false;}cout<<"DFS遍历后的结果 "<<endl;dfs(G,0);cout<<"\nBFS遍历后的结果 "<<endl;bfs(G);cout<<endl;Prim(G,0);//0开始构造最小生成树Kruskal(G);Dijkstra(G,0);Floyd(G);return 0;
}
/*
6 7
a
b
c
d
e
f
a b 3
a c 6
a e 5
b c 9
c d 7
d e 4
d f 2
*/

运行结果如下
在这里插入图片描述

邻接表

/*
图的创建
深度优先遍历
广度优先遍历
拓扑排序
关键路径
*/#include<bits/stdc++.h>
using namespace std;#define MaxInt  32767       // 最大值∞ 
#define MVNum	 100		// 最大顶点数 
#define MAXSIZE 100 		//最大长度
#define OVERFLOw -2
#define OK 1
#define TeleType char
#define InfoType int//代表边的权值
#define ERROR 0typedef int Status;
typedef enum {DG, DN, UDG, UDN} GraphKind;  
//{有向图，有向网，无向图，无向网} 
typedef char VerTexType;  //假设顶点的数据类型为字符型
typedef int ArcType;  // 假设边的权值类型为整型typedef struct ArcNode {//边结点int   adjvex; 	// 该弧(边)所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边int weight;		//权值	
} ArcNode; typedef struct VNode {//表头结点VerTexType   data; 	// 顶点信息 ArcNode       *firstarc; // 指向第一条依附该顶点的弧(边) 
} VNode, AdjList[MVNum]; typedef struct { AdjList   vertices; 	//顶点数组 int   vexnum, arcnum; // 图的当前顶点数和弧(边)数GraphKind kind;//图的种类 
} ALGraph; 
//找点的位置
int Locate(ALGraph &G,VerTexType v){int t = -1;for(int i = 0;i<G.vexnum;i++){if(G.vertices[i].data == v){t = i;break;}}return t;
}
//邻接表创建有向网
Status CreateDG(ALGraph &G){cout<<"所需点的个数：";cin>>G.vexnum;cout<<"所需边的个数：";cin>>G.arcnum;G.kind = DG;//有向网//输入顶点的信息//构造头节点cout<<"请依次输入顶点信息"<<endl;for(int i = 0;i<G.vexnum;i++){cout<<"第"<<i+1<<"个：";cin>>G.vertices[i].data;G.vertices[i].firstarc = nullptr;}//边的信息 采用头插法cout<<"请依次输入边的信息"<<endl;cout<<"输入格式 点v1 点v2"<<endl;for(int k = 0;k<G.arcnum;k++){VerTexType v1,v2;
//		ArcType a;cin>>v1>>v2;int i = Locate(G,v1);int j = Locate(G,v2);ArcNode* p = new ArcNode;//新的边节点p->adjvex = j;//边指向的顶点的序号//头插法//p的下一个边改成第i个点后依附的第一条弧p->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p;}return OK;
}
//打印邻接表
void PrintDG(ALGraph &G) {for (int i = 0; i < G.vexnum; i++) {cout << "[" << G.vertices[i].data << "]";ArcNode* p = G.vertices[i].firstarc;while (p!= nullptr) {int t = p->adjvex;cout << "->" << p->adjvex << "("<< G.vertices[t].data<<")";p = p->nextarc;}cout << endl;}
}
bool visited[MVNum];
void dfs(ALGraph &G,int v){cout<<G.vertices[v].data;visited[v] = true;ArcNode *p = G.vertices[v].firstarc;while(p!=nullptr){int w = p->adjvex;//p的周围的点的下标if(!visited[w]) dfs(G,w);//第w个点未被访问 =>访问下p = p->nextarc;}
}
void bfs(ALGraph &G){for (int i = 0; i < G.vexnum; i++) {visited[i] = false;}queue<int> Q;for(int i =0;i<G.vexnum;i++){if(!visited[i]){visited[i] = true;cout<<G.vertices[i].data;Q.push(i);while(!Q.empty()){int u = Q.front();//Q存放的是下标Q.pop();ArcNode *p = G.vertices[u].firstarc;while(p!=nullptr){if(!visited[p->adjvex]){visited[p->adjvex] = true;cout<<G.vertices[p->adjvex].data;Q.push(p->adjvex);}p = p->nextarc;}}}}
}
//拓扑排序
void FindIndegree(ALGraph &G,int *indegree){//求每个点的入度for(int i = 0;i<G.vexnum;i++){indegree[i] = 0;//初始化}for(int i = 0;i<G.vexnum;i++){ArcNode * p = G.vertices[i].firstarc;while(p != NULL){//为什么写while(!p)就运行不了indegree[p->adjvex] ++;p = p->nextarc;}}
}
Status TopologicalSort(ALGraph &G,int topo[]){int indegree[G.vexnum];FindIndegree(G,indegree);//入度个数存放完毕stack<int> S;for(int i = 0;i<G.vexnum;i++){if(indegree[i] == 0){//入度为0的点S.push(i);}}int m = 0;while(!S.empty()){//度为0的点int i = S.top();S.pop();topo[m] = i; m++;//拓扑排序依次存入 m自增ArcNode * p = G.vertices[i].firstarc;while(p!=NULL){//删除度为0的点的出度对其他点的影响indegree[p->adjvex] -- ;if(indegree[p->adjvex]==0) S.push(p->adjvex);//如果该点入度为0 则入栈p = p->nextarc;}}if(m<G.vexnum) return ERROR;//m不到G.vexnum 说明有环else return OK;
}
int main(){ALGraph G;CreateDG(G);PrintDG(G);for(int i =0;i<G.vexnum;i++){visited[i] = false;}cout<<"DFS遍历后的结果:"<<endl;dfs(G,0);cout<<"\nBFS遍历后的结果:"<<endl;bfs(G);int topo[G.vexnum];Status sortStatus = TopologicalSort(G, topo);if (sortStatus == OK) {cout << "拓扑排序结果: ";for (int i = 0; i < G.vexnum; i++) {cout << G.vertices[topo[i]].data;if (i!= G.vexnum - 1) cout << " -> ";}cout << endl;} else {cout << "图中存在环，无法进行拓扑排序。" << endl;}return 0;
}
/*
6 7
a
b
c
d
e
f
a b
a c
a e
b c
c d
d e
d f
*/

运行结果如下
在这里插入图片描述

十、总结

通过以上对图的各种操作和算法的详细介绍，我们可以看到图数据结构在处理复杂关系问题时的强大能力。从图的创建开始，无论是邻接矩阵还是邻接表的存储方式，都为后续的操作提供了基础。深度优先遍历和广度优先遍历是图的基本遍历方式，能够帮助我们探索图的结构。最小生成树算法（Prim 和 Kruskal）在解决网络设计等问题中具有重要应用，如构建通信网络时找到成本最小的连接方式。最短路径算法（Djikstra 和 Floyd）则在导航、路由等领域发挥关键作用，帮助我们找到两点之间的最优路径。拓扑排序在任务调度、课程安排等方面有着实际意义，确保各项任务或课程能够按照合理的顺序进行。在实际应用中，我们需要根据具体问题的特点选择合适的图存储结构和算法，以达到高效解决问题的目的。同时，理解这些算法的原理和实现细节，有助于我们在面对更复杂的图相关问题时能够灵活运用和创新。希望本文对大家理解图的操作和算法有所帮助，在今后的学习和工作中能够更好地应用图数据结构解决实际问题。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/475940.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

利用Vue的相关特性，制作相册

利用Vue的相关特性，制作相册

目录 一、整体结构 1、设置一个div盒子 2、设置图片展示 3、页码按钮 4、翻页按钮 二、CSS样式 1、 .clear_ele::after 2、设置图片、按钮等属性的样式 三、JavaScript部分&#xff08;Vue&#xff09; 1、导入模块 2、创建Vue应用 ①定义响应式数据 ②定义事件处…
阅读更多...
优化表单交互：在 el-select 组件中嵌入表格显示选项

优化表单交互：在 el-select 组件中嵌入表格显示选项

介绍了一种通过 el-select 插槽实现表格样式数据展示的方案&#xff0c;可更直观地辅助用户选择。支持列配置、行数据绑定及自定义搜索&#xff0c;简洁高效&#xff0c;适用于复杂选择场景。完整代码见GitHub 仓库。 背景 在进行业务开发选择订单时&#xff0c;如果单纯的根…
阅读更多...
（C语言）文件操作

（C语言）文件操作

目录 文件 程序文件 数据文件 文件名 ​编辑数据文件的分类 文件的打开和关闭 流 标准流 1&#xff09;stdin 2&#xff09;stdout 3&#xff09;stderr 文件指针 文件的打开和关闭 对文件内容操作的函数 1&#xff09;fgetc&#xff0c;fputc 2&#xff09;fp…
阅读更多...
AI修改验证账号名正则表达式的案例

AI修改验证账号名正则表达式的案例

我有如下的一行老代码&#xff0c;今天复用的时候发现当时注释写错了&#xff0c;改好以后请AI再检查一遍。 因为这次AI的分析的思路很典范&#xff0c;所以拿出来分享一下。 提问&#xff1a; 请看一下这个正则和后面的注释是否匹配&#xff0c;现在的验证规则是否保证账号至…
阅读更多...
SQL进阶技巧：如何进行数字范围统计？| 货场剩余货位的统计查询方法

SQL进阶技巧：如何进行数字范围统计？| 货场剩余货位的统计查询方法

目录 0 场景描述 1 剩余空位区间和剩余空位编号统计分析 2 查找已用货位区间 3 小结 0 场景描述 这是在做一个大型货场租赁系统时遇到的问题&#xff0c;在计算货场剩余存储空间时&#xff0c;不仅仅需要知道哪些货位是空闲的&#xff0c;还要能够判断出哪些货位之间是连…
阅读更多...
彻底理解如何保证Redis和数据库数据一致性问题

彻底理解如何保证Redis和数据库数据一致性问题

一.背景 系统中缓存最常用的策略是&#xff1a;服务端需要同时维护 DB 和 Cache 并且是以 DB 的结果为准&#xff0c;那么就可能出现 DB 和 Cache 数据不一致的问题。 二.读数据 逻辑如下&#xff1a; 当客户端发起查询数据的请求&#xff0c;首先回去Redis中查看没有没该数据&…
阅读更多...
后仿真中的SDF语法之关键字 IOPATH 用法详解

后仿真中的SDF语法之关键字 IOPATH 用法详解

在后仿真中&#xff0c;SDF&#xff08;Standard Delay Format&#xff09;文件用于描述设计的时序信息&#xff0c;而IOPATH是SDF中的一个关键结构&#xff0c;用于定义单元间的路径延迟。以下是IOPATH关键字的用法及其相关内容的详细介绍&#xff1a; IOPATH结构旨在将延迟数…
阅读更多...
Springboot 整合 Java DL4J 搭建智能问答系统

Springboot 整合 Java DL4J 搭建智能问答系统

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…
阅读更多...
基于SpringBoot的“网上书城管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“网上书城管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“网上书城管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 系统首页界面图 用户注册界面…
阅读更多...
测评部署和管理 WordPress 最方便的面板

测评部署和管理 WordPress 最方便的面板

新版宝塔面板快速搭建WordPress新手教程 - 倚栏听风-Morii - 博客园 初学者使用1Panel面板快速搭建WordPress网站 - 倚栏听风-Morii - 博客园 可以看到&#xff0c;无论是宝塔还是1Panel&#xff0c;部署和管理WordPress都有些繁琐&#xff0c;而且还需要额外去配置Nginx和M…
阅读更多...
网络安全问题概述

网络安全问题概述

1.1.计算机网络面临的安全性威胁 计算机网络上的通信面临以下的四种威胁&#xff1a; (1) 截获——从网络上窃听他人的通信内容。 (2) 中断——有意中断他人在网络上的通信。 (3) 篡改——故意篡改网络上传送的报文。可应用于域名重定向&#xff0c;即钓鱼网站。 (4) 伪造——伪…
阅读更多...
视觉顶会论文 | 基于Swin Transformer的轴承故障诊断

视觉顶会论文 | 基于Swin Transformer的轴承故障诊断

往期精彩内容&#xff1a; Python-凯斯西储大学&#xff08;CWRU&#xff09;轴承数据解读与分类处理 Pytorch-LSTM轴承故障一维信号分类(一)-CSDN博客 Pytorch-CNN轴承故障一维信号分类(二)-CSDN博客 Pytorch-Transformer轴承故障一维信号分类(三)-CSDN博客 三十多个开源…
阅读更多...
Altenergy电力系统控制软件 status_zigbee SQL注入漏洞复现(CVE-2024-11305)

Altenergy电力系统控制软件 status_zigbee SQL注入漏洞复现(CVE-2024-11305)

0x01 产品简介 Altenergy电力系统控制软件是Altenergy Power System推出的一款专业软件。旨在为用户提供全面、高效、安全的电力系统控制解决方案。广泛应用于各类电力系统领域，如电力调度中心、发电厂、变电站、工业园区等。通过该软件的应用，用户可以实现对电力系统的全面…
阅读更多...
java: spire.pdf.free 9.12.3 create pdf

java: spire.pdf.free 9.12.3 create pdf

可以用windows 系统中文字体&#xff0c;也可以从文件夹的字体文件 /*** encoding: utf-8* 版权所有 2024 ©涂聚文有限公司* 许可信息查看&#xff1a;言語成了邀功盡責的功臣&#xff0c;還需要行爲每日來值班嗎* 描述&#xff1a;* # Author : geovindu,Geovin Du 涂…
阅读更多...
AUTOSAR网络管理中的主动唤醒与被动唤醒

AUTOSAR网络管理中的主动唤醒与被动唤醒

文章目录 1、主动/被动唤醒源、主动/被动唤醒节点2、网络拓扑说明 1、主动/被动唤醒源、主动/被动唤醒节点 休眠唤醒需要有一个触发源来进行触发&#xff0c;我们常用的NM报文是其中的载体之一。休眠唤醒的触发源又分为主动唤醒源和被动唤醒源。 主动唤醒源&#xff0c;就是能…
阅读更多...
索贝融媒体 Sc-TaskMonitoring/rest/task/search SQL注入漏洞复现

索贝融媒体 Sc-TaskMonitoring/rest/task/search SQL注入漏洞复现

0x01 产品简介 索贝融媒体产品是成都索贝数码科技股份有限公司（简称索贝）为各级电视台和媒体机构打造的一套集互联网和电视融合生产的解决方案。其代表产品为MCH2.0融合媒体生产业务系统，该系统带来了媒体领域一种全新的融合生产流程和工作机制，具有全方位的资源汇聚能力、…
阅读更多...
【PyTorch】Pytorch中torch.nn.Conv1d函数详解

【PyTorch】Pytorch中torch.nn.Conv1d函数详解

1. 函数定义 torch.nn.Conv1d 是 PyTorch 中用于一维卷积操作的类。定义如下&#xff1a; 官方文档&#xff1a;https://pytorch.ac.cn/docs/stable/generated/torch.nn.Conv1d.html#torch.nn.Conv1d torch.nn.Conv1d(in_channels, out_channels, kernel_size, stride1,paddi…
阅读更多...
[大数据]Trino

[大数据]Trino

Trino安装部署-CSDN博客 Central Repository: io/trino/trino-server 下载地址: repo1.maven.org/maven2/io/trino/Central Repository: io/trino/trino-serverhttps://repo1.maven.org/maven2/io/trino/trino-server/ vim /etc/security/limits.conf * soft nofile 131072…
阅读更多...
三种复制只有阅读权限的飞书网络文档的方法

三种复制只有阅读权限的飞书网络文档的方法

大家都知道&#xff0c;飞书是一款功能强大的在线协作工具&#xff0c;可以帮助团队更高效地协作和沟通。越来越多的资料都在使用飞书文档&#xff0c;在使用飞书的过程中&#xff0c;发现很多文档没有复制权限&#xff0c;如果想要摘抄笔记&#xff0c;只能一个字一个字地敲出…
阅读更多...
HTML5拖拽API学习 托拽排序和可托拽课程表

HTML5拖拽API学习 托拽排序和可托拽课程表

文章目录 前言拖拽API核心概念拖拽式使用流程例子注意事项综合例子&#x1f330; 可拖拽课程表拖拽排序 前言 前端拖拽功能让网页元素可以通过鼠标或触摸操作移动。HTML5 提供了标准的拖拽API&#xff0c;简化了拖放操作的实现。以下是拖拽API的基本使用指南&#xff1a; 拖拽…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023