《有向无环图的关键路径（Critical path of directed acyclic graphs）.doc》由会员分享，可在线阅读，更多相关《有向无环图的关键路径（Critical path of directed acyclic graphs）.doc（16页珍藏版）》请在三一文库上搜索。
1、有向无环图的关键路径（Critical path of directed acyclic graphs）#包含iostream #包括#包括使用命名空间；#定义max_vertex_num 20typedef struct阿克诺德国际adjvex；/ /该弧所指向的顶点的位置struct阿克诺德* nextarc；/ /指向下一条弧的指针国际信息；/ /弧上的信息/ / / /该弧相关信息字符串信息； ArcNode；typedef struct VNode int数据；/ /顶点信息阿克诺德* firstarc；/ /指向第一条依附该顶点的弧的指针 VNode，adjlist max_ver
2、tex_num ；typedef struct adjlist顶点；/ /存储图int毒液，arcnum；/ /图的当前顶点数和弧数int类型；/ /图的种类标志 ALGraph；int入度 max_vertex_num = 0 ；/用于拓扑排序int CreateUG（algraph & G）cout g.arcnum g.venum CIN；int i；为（i = 0；i g.venum；i+）g.vertices 我。数据= I + 1；g.vertices 我。firstarc = null；为（i = 0；i g.arcnum；i+）cout V2 V1 CIN；阿克诺德*电流= g
3、.vertices v1-1 firstarc ；阿克诺德P = g.vertices v1-1 firstarc ；如果（电流= = null）g.vertices v1-1 。firstarc =新阿克诺德；g.vertices v1-1 。firstarc - adjvex = V2-1；g.vertices v1-1 。firstarc - nextarc = null；别的而（电流！= null）P =电流；电流=电流- nextarc；电流=新阿克诺德；电流- adjvex = V2-1；电流- nextarc = null；P nextarc =电流；电流= g.vertices
4、 V2-1 firstarc ；P = g.vertices V2-1 firstarc ；如果（电流= = null）g.vertices V2-1 。firstarc =新阿克诺德；g.vertices V2-1 。firstarc - adjvex = v1-1；g.vertices V2-1 。firstarc - nextarc = null；别的而（电流！= null）P =电流；电流=电流- nextarc；电流=新阿克诺德；目前adjvex = v1-1 -；电流- nextarc = null；P nextarc =电流；返回1；int CreateDG（algraph &
5、G）cout g.arcnum g.venum CIN；int i；为（i = 0；i g.venum；i+）g.vertices 我。数据= I + 1；g.vertices 我。firstarc = null；为（i = 0；i g.arcnum；i+）cout V2 V1 CIN 信息；阿克诺德*电流= g.vertices v1-1 firstarc ；阿克诺德P = g.vertices v1-1 firstarc ；入度V2-1 + ；如果（电流= = null）g.vertices v1-1 。firstarc =新阿克诺德；g.vertices v1-1 。firstarc -
6、 adjvex = V2-1；g.vertices v1-1 。firstarc - nextarc = null；g.vertices v1-1 。firstarc -信息=信息；别的而（电流！= null）P =电流；电流=电流- nextarc；电流=新阿克诺德；电流- adjvex = V2-1；电流- nextarc = null；电流-信息=信息；P nextarc =电流；返回1；国际createdg1（algraph & G）cout g.arcnum g.venum CIN；int i；为（i = 0；i g.venum；i+）g.vertices 我。数据= I + 1；g
7、.vertices 我。firstarc = null；为（i = 0；i g.arcnum；i+）cout V2 V1 CIN；阿克诺德*电流= g.vertices V2-1 firstarc ；阿克诺德P = g.vertices V2-1 firstarc ；如果（电流= = null）g.vertices V2-1 。firstarc =新阿克诺德；g.vertices V2-1 。firstarc - adjvex = v1-1；g.vertices V2-1 。firstarc - nextarc = null；别的而（电流！= null）P =电流；电流=电流- nextarc
8、；电流=新阿克诺德；目前adjvex = v1-1 -；电流- nextarc = null；P nextarc =电流；返回1；int CreateGraph（algraph & G）cout G.kind；开关（G.kind）案例0：返回createug（G）；/ /构造无向图案例1：返回createdg（G）；/ /构造有向图案例2：返回createdg1（G）；/ /构造逆邻接图默认值：返回0；在我 max_vertex_num = 0 ；bool TopologicalSort（algraph & G，栈 & T）的堆栈；int i；为（i = 0；i nextarc）int W =
9、 P adjvex；入度水；如果（入度W = = 0）S.push（W）；如果（我我 + P 信息我我们）我我们，我我 + P -信息；如果（计数g.venum）cout “有向图中有环存在” endl；返回false；返回true；无效的关键（algraph & G）int k，DUT；堆栈 T；如果（！TopologicalSort（G，T）返回；int v1 max_vertex_num ；为（k = 0；Kg.venum；K+）V1 K =我 g.venum-1 ；而（！T. empty()）int i = t top()；pop() T.；对于（阿克诺德* P = g.vertice
10、s 我。firstarc；P！= null；P = P - nextarc）K = P adjvex；大连理工= P -信息；如果（V1 K - DUTV1 我）V1 我 = V1 K - DUT；为（j = 0；J nextarc）K = Q adjvex；大连理工= Q -信息；如果（我 J = = V1 K - DUT）cout “关键路径：“ g.vertices J。数据” g.vertices K。数据 endl；main() intALGraph G；建立（G）；阿克诺德*电流1；阿克诺德* P；为（int k = 0；Kg.venum；K+）cout g.vertices K。数据”；阿克诺德*电流1 = g.vertices K。firstarc；而（电流1！= null）cout adjvex nextarc；cout endl；系统（“暂停”）；CriticalPath（G）；系统（“暂停”）；为（int i = 0；i nextarc；删除电流1；电流1 = P；返回1；