Implementation and Application of Keypase Algorithm in Data Structure

Implementation and Application of Keypase Algorithm in Data Structure

Abstract To introduce the algorithm for key paths, for the given event node network, request to find all the paths from the starting point to the end point, after analysis, compare, find the maximum path, thus getting the key path Algorithm, and give the source program implemented on the computer.

Key words critical path minimum time

1 Introduction

It usually regards plans, construction processes, production processes, and procedures. In addition to small projects, the project is generally divided into several sub-projects called "activity". Completed the sub-projects of these "activities", this project can be completed.

Usually we use a project to represent an engineering. In this figure, the activity is expressed in the vertex, with a direction

indicates that the activity VI must be performed before the active VJ. If there is a directional direction in which a direction is used in the direction of the direction, it represents the activity of a project, and the duration of the activity is indicated by the value of the edge, and the event is indicated by the vertex. (EVENT), this is called a network that represents the activity of the active network, referred to as the ACTIVE ON EDGES network.

The AOE network is very useful in certain engineering estimates. He can make people understand:

(1) How long does it take to study at least a project?

(2): Those activities are the key to the progress of the project?

In the AOE network, some activities can be conducted in parallel. From the source point to each vertex, so that the path from the source point to the combo point may more than one. The length of these paths may also be different. Although the time required to complete the activities of different paths is different, all activities on each path are completed, and this project is completed. Therefore, the time required to complete the entire project depends on the longest path length from the source point to the coming point, that is, the sum of all activities on this path. This path is called a critical path (Critical Path).

2: Design steps:

1: Taking a certain project as blueprint, the structure of the map represents the actual engineering plan.

2: Survey to analyze and predict the time of this project plan.

3: Establish the Activity On Edge Network in the results of the survey, which means the activity of the activity, and is represented by the form of the figure.

4: Use the graph to store this information.

5: Establish AOE diagram with cretegraphic (); function.

6: Use the searchmAppath (); function to obtain the maximum path and print the critical path.

7: Write code

8: Test

3: Design code:

#include

#include

#include

#include

// # Define Projectnumber 9 // 10

// # Define plannumber 11 // 13

Typedef struct node

{

Int adjvex;

Int Dut;

Struct Node * Next;

} edgenode;

Typedef struct

{

INT projectname;

Int ID;

Edgenode * LINK;

} vExnode;

// vexNode GraphicMap [ProjectNumber];

Void Creategraphic (VexNode * GraphicMap, int propjectNumber, int activenumber)

{

Int Begin, end, duttem

Edgenode * P;

For (int i = 0; i

GraphicMap [i] .projectname = i;

Graphicmap [i] .id = 0;

Graphicmap [i] .LINK = NULL;

}

Printf ("The beginning of a project to the end of the node input / n");

Printf ("such as: 3, 4, and 9 Enter 9 unit time / N" in the third node to the fourth node);

For (int K = 0; K

{

Scanf ("% D,% D,% D", & Begin, & End, & DUTTEM);

p = (edgenode *) malloc (sizeof (edgenode));

P-> adjgEx = end-1;

P-> DUT = DUTTEM;

GraphicMap [end-1] .id ;

P-> Next = graphicmap [begin-1] .link;

Graphicmap [begin-1] .LINK = P;

}

}

INT searchMAppath (VexNode * GraphicMap, int projectNumber, int activenumber, int & totaltime)

{

INT I, J, K, M = 0;

INT front = -1, rear = -1;

INT * TOPOLOGYSTACK = (int *) Malloc (int)); // Used to save topology arrangement

INT * VL = (int *) malloc (int)); // Used to indicate that VJ allows for the latest time without postponed the entire project

INT * VE = (int *) malloc (int)); // Used to indicate that VJ is the earliest time

INT * L = (int *) malloc (activenumber * sizeof (int)); // Used to indicate the event AI to complete the start time

INT * E = (int *) malloc (activenumber * sizeof (int)); // Indicates the earliest start time

Edgenode * P;

TOTALTIME = 0;

For (i = 0; i

For (i = 0; i

{

IF (GraphicMap [i] .id == 0)

{

TopologyStack [ REAR] = i;

M ;

}

}

While (Front! = Rear)

{

Front ;

J = TopologyStack [Front];

M ;

P = graphicmap [j] .link;

While (p)

{

K = P-> Adjvex;

Graphicmap [k] .id -;

IF (VE [J] P-> DUT> VE [K])

VE [K] = VE [J] P-> DUT;

IF (GraphicMap [K] .id == 0)

TopologyStack [ REAR] = K;

P = P-> next;

}

}

IF (M

{

Printf ("/ n The chart established by this program does not calculate the key path / N");

Printf ("will exit this procedure / n"); Return 0;

}

TotalTime = ve [Projectnumber-1];

For (i = 0; i

VL [I] = TOTALTIME;

For (i = projectnumber-2; i> = 0; I -)

{

J = TopologyStack [i];

P = graphicmap [j] .link;

While (p)

{

K = P-> Adjvex;

IF ((VL [K] -P-> DUT)

VL [J] = VL [K] -p-> DUT;

P = P-> next;

}

}

i = 0;

Printf ("| starting point | end point | earliest start time | latest completion time | difference | Note | / N");

For (j = 0; j

{

P = graphicmap [j] .link;

While (p)

{

K = P-> Adjvex;

e [ i] = ve [j];

l [i] = VL [k] -p-> dut;

Printf ("|% 4D |% 4D |% 4D |% 4D |% 4D |", graphicmap [j] .projectname 1, graphicmap [k] .projectname 1, e [i], l [i], l [i] -e [i]);

IF (L [i] == e [i])

Printf ("Key Activity |");

Printf ("/ n");

P = P-> next;

}

}

Return 1;

}

void seekkeyroot ()

{

INT ProjectNumber, ActiveNumber, TotalTime = 0;

SYSTEM ("CLS");

PRINTF ("Please enter the number of nodes of this project:");

Scanf ("% D", & projectnumber;

Printf ("Please enter the number of activities for this project:");

Scanf ("% D", & activeNumber;

VEXNODE * graphicmap = (vexNode *) Malloc (Projectnumber * Sizeof (vexNode);

CreateGraphic (GraphicMap, Projectnumber, ActiveNumber);

SearchMappath (GraphicMap, Projectnumber, ActiveNumber, Totaltime);

Printf ("The shortest time used throughout the project is:% D unit time / n", TOTALTIME);

System ("pause");

}

int main ()

{

CHAR CH;

For (;;)

{

DO

{

SYSTEM ("CLS");

Printf ("| Welcome to the key path algorithm process |");

For (int i = 0; i <80; i ) Printf ("*");

Printf ("% s", "(s) TART starts entering the node data of the project and finds a critical path / N");

Printf ("% s", "(e) xit exit / n"); Printf ("% s", "Please enter the selection:");

Scanf ("% C", & ch);

CH = TouPper (CH);

} whiling (ch! = 's' && ch! = 'e');

Switch (CH)

{

Case's':

SeekKeyRoot ();

Break;

Case'e ':

Return 1;

}

}

}

4: Summary:

At this point, all of the design processes have been completed, and all of the code has been debugged under the VC6.0 Win2000 platform. As can be seen from the above analysis, the design results are in line with the prediction. Key paths have an important role in specific projects, when only one of the key paths in an AOE network, accelerate any key activities on key paths, Can accelerate the completion of the entire project. However, when a key path in an AOE network is more than one, accelerating any key activity is not necessarily capable of accelerating the completion of the entire project. As scheme 1 and Scheme 2, the progress of the entire project is not changed when changing the critical path. Refers

[1] Tan Haoqiang compiled. Beijing: Tsinghua University Press, 2000 [2] Yan Weimin, Wu Weimin Edited. Data Structure. Beijing: Tsinghua University Press, 2001 [3] Liu Zhenglin Edited. Object-oriented Programming. Wuhan: East China University of Science and Technology Press, 2002 [4] Yichen, Practical Training Tutorial. Beijing: Electronic Industry Press, 1998