Today, I saw a lot of questions to use the topological sorting diagram, just learn a, a knock on the code to learn algorithm also review the specific operation and the use of the stack.
A topological sort
Topological ordering of a Directed Acyclic Graph (DAG)G is to arrange all vertices in G into a linear sequence, such that any pair of vertices u and V in the Graph appear before V in the linear sequence if edge <u,v>∈E(G). In general, such linear sequences are called Topological Order sequences, or Topological sequences for short. In simple terms, a partial order in a set leads to a total order in that set. This operation is called topological sorting.
Preliminary knowledge
A larger project is often divided into subprojects, which we call activities. In the whole project, some subprojects (activities) must begin after the completion of other related subprojects, that is, the beginning of a subproject presuppositions the completion of all its preceding subprojects, but some subprojects have no presuppositions and can be scheduled to start at any time. In order to vividly reflect the whole project of the relation of before and after each project (activities), can be said with a directed graph, the vertices in the graph represent activities (a project), the directed edges in the graph represent activities successively relations, namely to the edge of the starting point of the activity is at the end of activity, the preamble of starting point only when the activity is completed, the end activities. In general, we refer to the directed graph in which vertices represent activities and edges represent sequential relationships between activities as Activity On Vertex network, or AOV network for short. An AOV network should be a directed acyclic graph, that is, it should not have a loop, because if there is a loop, then all the activities on the loop cannot be carried out. As shown in figure 3-6 is A loop has three vertices, made up by < > A, B to B activity must be after A activities, made up by < B, C > available activities must be in B, C and C activity introduced necessarily after A campaign, but made up by < A > C, available C activities must, before A activity to appear antinomy, can make each activity. If this situation occurs in a program, it is called a deadlock or an infinite loop and must be avoided. In THE AOV network, if there is no loop, all activities can be arranged into a linear sequence, so that all the precursor activities of each activity are ranked in front of the activity. This sequence is called Topological order. The process of constructing Topological sequences from AOV networks is called Topological sort. The topological sequence of AN AOV network is not unique. Any linear sequence satisfying the above definition is called its topological sequence. The practical significance of constructing topological sequence by AOV network is: if the vertex order in the topological sequence is followed, all the precursor activities can be guaranteed to have been completed when each activity is started, so that the whole project sequence can be carried out without conflict. To put it simply, it is to sort the order of the graph from first to last, in which there can be no ring. The final topological sequence is actually to complete all the things and find the order of the middle things.
step
The topological sorting algorithm that constructs topological sequence from AOV network mainly executes the following two steps in a loop until there is no vertex with indegree 0. (1) Select a vertex with input degree of 0 and output it; (2) Delete this vertex and all outgoing edges from the net.
After the loop, if the output number of vertices is less than the number of vertices in the network, the output of “loop” information, otherwise the output of the vertex sequence is a topological sequence.
The illustration
2: Delete 2 or 3 and the corresponding edge
3: delete 3 or 4 and the corresponding edge
3: Repeat the preceding steps
Code implementation
I use the adjacence list of the graph to achieve, but the basic operation of the original graph to add degree count operation, and then use the stack for topological sorting. The graph is:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXVEX 10
typedef char VerType; // Vertex value type
struct EdgeNode{
int adjvex; // The domain of the adjacent points stores the subscripts corresponding to the vertices
int weight; // Used to store weights, which are not required for non-netted graphs
struct EdgeNode* next; // Next node
};
struct VertexNode{
int in; / / into the degrees
VerType data; / / value
struct EdgeNode* firstedge; // The pointer to the adjacencies header
};
struct Graph{
struct VertexNode vers[MAXVEX];
int numVertexes, numEdges; // The number of vertices and edges
};
/* Topological sort, if G has no loop, output the topological sort sequence and return OK, if there is loop ERROR */
int TopologicalSort(struct Graph* G){
struct EdgeNode* e;
int i, k, gettop;
int top = 0; // Stack pointer subscript
int count = 0; // Count the output vertices
int* stack; // Store vertices with degree 0
stack = (int*)malloc(G->numVertexes * sizeof(int));
for(i = 0; i<G->numVertexes; i++)// Traverse all nodes
if(G->vers[i].in == 0)
stack[++top] = i; // Push vertices with input degree 0
while(top ! =0){
gettop = stack[top--]; / / out of the stack
printf("%c ",G->vers[gettop].data);
count++; // Count the output vertices
for(e=G->vers[gettop].firstedge; e; e = e->next){
// Arc table traversal
k = e->adjvex;
if(! (--G->vers[k].in))// Subtract 1 from the input degree of the adjacent vertex k
stack[++top] = k; // If 0, push the stack, so that the next loop output}}if(count < G->numVertexes) // If count is less than the number of vertices, there is a ring
return 0;
else
return 1;
}
/* Figure initialization */
void CreateGraph(struct Graph* G){
int i, m, n;
printf("Input number of vertices and edges: \n");
scanf("%d %d",&G->numVertexes, &G->numEdges);
printf("Input vertex value: \n");
getchar(); // Eat the carriage return
for(i=0; i<G->numVertexes; i++){//getchar(); // Eat the carriage return
G->vers[i].data=getchar();
getchar();
//scanf("%c",&G->vers[i].data);
}
// Initialize the graph head node pointer and input value
for(i=0; i<G->numVertexes; i++){ G->vers[i].firstedge =NULL;
G->vers[i].in = 0; // The input is 0
}
printf("Input edge: \n");
for(i=0; i<G->numEdges; i++){scanf("%d %d",&m, &n);
struct EdgeNode *newNode = (struct EdgeNode*)malloc(sizeof(struct EdgeNode));
newNode->next = G->vers[m].firstedge == NULL ? NULL : G->vers[m].firstedge;
newNode->adjvex = n;
G->vers[m].firstedge = newNode;
G->vers[n].in++; / / into the degree of + 1}}int main(a){
struct Graph *G=(struct Graph*)malloc(sizeof(struct Graph)) ;
CreateGraph(G);
if(TopologicalSort(G)){
printf("Topological sorting is complete! \n");
}else{
printf("Ring of graph existence");
}
return 0;
}
Copy the codeThe results are as follows:
