当前位置: 代码迷 >> 综合 >> 深入理解数据结构——关键路径算法AOE
  详细解决方案

深入理解数据结构——关键路径算法AOE

热度:87   发布时间:2024-01-17 05:07:57.0
#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 << "网中含有环";}
}