AOV network topology sorting

 

 AOV Network to solve the problem of topology sorting ,AOE Network to solve the critical path problem

AOV network

AOV The characteristics of the net

Topological sorting concept

The method of topological sorting

 

 

  testing AOV The method of whether there is a ring in the network

 

  Structure code involved

typedef struct EdgeNode      // Side table node 
{
	int adjvex;              // Adjacency region , Store the subscript corresponding to the vertex 
	int weight;              // Used to store weights , You don't need 
	struct EdgeNoe* next;    // Chain domain , Point to the next adjacent point 
}EdgeNode;

typedef struct VertexNode    // Vertex table node 
{ 
	int in;                  // Vertex penetration 
	int data;                // Vertex domain , Store vertex information 
	EdgeNode* firstedge;     // Side header pointer 
}VertexNode,AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numVertexes, numEdges;  // The current number of vertices and edges in the graph 
}graphAdjList,*GraphAdjList;

Status TopologicalSort(GraphAdjList GL)
{
	EdgeNodde* e;
	int i, k, gettop;
	int top = 0;          // Used for stack pointer subscript 
	int count = 0;        // Used to count the number of output vertices 
	int *stack;           // The stack building storage degree is 0 The summit of 
	stack = (int*)malloc(GL->numVertexes * sizeof(int));
	for (i = 0; i < GL->numVertexes; i++)
	{
		if (GL->adjList[i].in == 0)
			stack[++top] = i;  // The degree of engagement is 0 The top of the stack 
	}
	while (top != 0)
	{
		gettop = stack[top--];  // Out of the stack 
		printf("%d->", GL->adjList[gettop].data);  // Print this vertex 
		count++;                // Count the number of output vertices 
		for (e = GL->adjList[gettop].firstedge; e; e = e->next)
		{
			// Traverse this vertex arc table 
			k = e->adjvex;
			if (!(--GL->adjList[k].in))  // take k The entry degree of vertex adjacency table No -1
				stack[++top] = k;        // if 0 The stack , So that the next cycle output 
		}
	}
	if (count < GL->numVertexes)         // If count Less than the number of vertices , It shows that there is a ring 
		return ERROR;
	else
		return OK;
}