#include<iostream>
#include<string>
using namespace std;//邻接表的实现typedef int InfoType;struct AdjNode {int another_vertex;//该条边另一个顶点在表头节点数组中的下标InfoType info;//AdjNode* next;//下一个节点地址
};typedef char EType;
struct AdjList {int indegree;//表示每个顶点的入度,该域的值建立在邻接表时动态计算EType data;AdjNode* head;
};struct AdjGraph {AdjList* head_list;int vertex_num;int edge_num;
};//基于邻接表表示的有向图计算入度的算法
void CalcIndegree(AdjGraph &g) {int* temp;int i;AdjNode* p;temp = new int[g.vertex_num];memset(temp, 0, sizeof(int) * g.vertex_num);for (i = 0; i < g.vertex_num; i++) {p = g.head_list[i].head;while (p) {temp[p->another_vertex]++;p = p->next;}}for (i = 0; i < g.vertex_num; i++) {g.head_list[i].indegree = temp[i];}delete[]temp;}//基于邻接表表示的有向图拓扑排序算法
#define MAXIMUM 100
void TopSort(AdjGraph g) {int stack[MAXIMUM], top;int i, j, number;AdjNode* p;top = -1;number = 0;for (i = 0; i < g.vertex_num; i++) {//所有度为0的顶点入栈if (g.head_list[i].indegree == 0){top++;stack[top] = i;}}while (top>=0) {i = stack[top];top--;number++;cout << i << ",";p = g.head_list[i].head;while (p) {j = p->another_vertex;g.head_list[j].indegree--;if (!g.head_list[j].indegree){top++;stack[top] = j;}p = p->next;}}if (number < g.vertex_num) {cout << "网中含有回路";}
}//关键路径算法Critical path
//基于邻接表表示的AOE网络的拓扑算法int *CSTACK, CTOP;//存放拓扑序列的栈
int* ve, * vl;void CriticalPath(AdjGraph g) {int i, j;AdjNode* p;CTOP = -1;CSTACK = new int[g.vertex_num];ve = new int[g.vertex_num];vl = new int[g.vertex_num];memset(ve, 0, sizeof(int) * g.vertex_num);TopSort(g);//求解各事件的最早发生时间for (i = 0; i < g.vertex_num;i++) {vl[i] = ve[g.vertex_num - 1];}while (CTOP>=0) {//求解各事件的最迟发生时间i = CSTACK[CTOP];CTOP--;p = g.head_list[i].head;while (p) {j = p->another_vertex;if (vl[i] > (vl[j] - p->info))vl[i] = vl[j] - p->info;p = p->next;}}for (i = 0; i < g.vertex_num; i++) {cout << ve[i] << "," << vl[i] << endl;}
}void TopSort(AdjGraph g) {int stack[MAXIMUM], top;int i, j, number;AdjNode* p;top = -1;number = 0;for (i = 0; i < g.vertex_num; i++) {//所有度为0的顶点入栈if (g.head_list[i].indegree == 0){top++;stack[top] = i;}}while (top >= 0) {i = stack[top];top--;number++;cout << i << ",";CSTACK[++CTOP] = i;//保存拓扑序列p = g.head_list[i].head;while (p) { //求解各事件的最早发生时间j = p->another_vertex;if (ve[i] < (ve[i] + p->info))ve[j] = ve[i] + p->info;p = p->next;}p = g.head_list[i].head;while (p) {j = p->another_vertex;g.head_list[j].indegree--;if (!g.head_list[j].indegree){top++;stack[top] = j;}p = p->next;}}if (number < g.vertex_num) {cout << "网中含有环";}
}
详细解决方案
深入理解数据结构——关键路径算法AOE
热度:87 发布时间:2024-01-17 05:07:57.0
相关解决方案
- 算法效率(数据结构),该如何解决
- 数据结构,很无力~该怎么处理
- 数据结构,该怎么处理
- java 数据结构,该如何解决
- 数据库 数据结构 关于索引解决办法
- 数据结构,离散数学什么的重要吗。该怎么解决
- 数据结构 - 线性表学习(php模拟)
- 【数据结构】【归并排序】
- 数据结构 05——树与二叉树
- 数据结构——01数据结构绪论
- 数据结构——02算法简介
- 《数据结构(C语言版)》课程学习(15)——实验项目名称:矩阵的转置
- 数据结构--连续内存分配的实现
- n叉树 数据结构
- 链表 数据结构
- Hash表 数据结构
- 数据结构——红黑数学习
- c(数据结构)下树的创建的非递归算法
- 数据结构-时间复杂度大O排名
- 数据结构---顺序表
- 数据结构----顺序栈
- 【数据结构】#数据结构复习提纲
- 数据结构 递归遍历二叉树 C/C++
- 数据结构 C/C++ 冒泡排序
- 数据结构 C/C++ 关键路径
- 数据结构 C/C++ 链栈
- 数据结构 C/C++ 链式队列
- 数据结构 C/C++ 对角矩阵
- 数据结构 C/C++ 对称矩阵
- C/C++ 数据结构 单链表