Topological sorting analysis: the intersection of computers and mathematics and C++ implementation

Depth-first search is a common method for implementing topological sorting. In DFS, we try to visit every node and add the node to the front of the result list when backtracking.

//C++ code example
#include <iostream>
#include <list>
#include <stack>
using namespace std;

class Graph {
    int V; // number of vertices
    list<int> *adj; // adjacency list

    void topologicalSortUtil(int v, bool visited[], stack<int> & Stack);
public:
    Graph(int V); //Constructor

    // add edge
    void addEdge(int v, int w);

    //Perform topological sort
    void topologicalSort();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> & Stack) {
    visited[v] = true;

    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); + + i)
        if (!visited[*i])
            topologicalSortUtil(*i, visited, Stack);

    Stack.push(v);
}

void Graph::topologicalSort() {
    stack<int> Stack;

    bool *visited = new bool[V];
    for (int i = 0; i < V; i + + )
        visited[i] = false;

    for (int i = 0; i < V; i + + )
      if (visited[i] == false)
        topologicalSortUtil(i, visited, Stack);

    while (Stack.empty() == false) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

As said in “Human Weakness”: “People are more likely to accept and understand new knowledge that is related to what they already know.” The DFS method in this code is similar to how we learn in life: we learn first Basic knowledge and then build more complex knowledge on top of that.

Topological sort is not just about finding an order. It’s about understanding the dependencies between things, and how to organize those things efficiently to ensure that each thing happens after all of its dependencies. This way of thinking can help us better understand and solve many problems in life.

4. Characteristics of topological sorting Topological Sorting)

4.1 Uniqueness and non-uniqueness

A distinctive feature of topological sorting is its possible uniqueness. For a given directed acyclic graph (DAG), there may be multiple valid topological sortings. This means that for the same DAG, we can get multiple different vertex orders, each of which satisfies the conditions of topological sorting.

For example, consider a simple DAG where A depends on B and B depends on C. Possible topological sortings are: C, B, A or B, C, A.

As said in “Human Weakness”: “People are more likely to accept new information that is consistent with their existing knowledge structure.” This means that when we are faced with multiple possible topological rankings, we are more likely to choose those A ranking that is consistent with our existing knowledge or experience.

4.2 Time complexity analysis

Common algorithms for topological sorting, such as depth-first search (DFS) and Kahn’s algorithm, have linear time complexity, that is, O(V + E), where V is the number of vertices and E is the number of edges.

Why are the time complexities of both algorithms linear? This is because each vertex and each edge is visited only once. This efficiency makes topological sorting widely used in large systems, such as software dependency management and task scheduling.

//Simplified code example using DFS for topological sorting
void topologicalSortDFS(int node, vector<int> & visited, stack<int> & result) {
    visited[node] = 1;
    for (int adjacent : graph[node]) {
        if (!visited[adjacent]) {
            topologicalSortDFS(adjacent, visited, result);
        }
    }
    result.push(node); // All neighbors of the current node have been visited, add them to the result
}

In this code, we first mark the current node as visited and then recursively visit all its unvisited neighbors. When all neighbors of a node have been visited, we add it to the results stack.

As it is said in the Tao Te Ching: “Knowing what it is, seek why it is.” When we deeply explore the characteristics of topological sorting and the principles behind it, we can not only understand its working mechanism, but also gain insight into its role in the real world. application and value.

5. Applications of topological sorting Topological Sorting)

Topological sorting is not just a purely mathematical concept, it has a wide range of applications in real life. The following are some of the main application areas of topological sorting:

5.1 Task Scheduling

In modern computer systems, task scheduling is a core issue. For example, when we have a series of tasks and dependencies between them, we need to determine an execution order to ensure that each task starts only after all its predecessors have completed.

Consider a simple example: before building a house, we need to first build the foundation, then build the walls, and finally install the roof. The dependencies between these tasks can be represented by a Directed Acyclic Graph (DAG), and topological sorting is used to determine the order of execution.

As said in “Human Weaknesses”: “People usually prefer to complete tasks in a certain order.” This human nature makes topological sorting particularly important in task scheduling.

5.2 Course Scheduling (Course Scheduling)

In the field of education, topological sorting is also widely used. Considering a university’s course structure, some courses may require prerequisites for other courses. For example, learning “Advanced Mathematics” may require learning “Basic Mathematics” first.

In order to develop a reasonable course schedule, we need to determine a sequence of courses that ensures that each course is scheduled after all of its prerequisite courses. This is exactly the application scenario of topological sorting.

As said in “Free Choice”: “Freedom of choice is the key to human progress.” Through topological sorting, we can provide students with a reasonable and flexible learning path, allowing them to freely choose their own learning direction.

5.3 Project Management (Project Management)

In project management, topological sorting also plays a key role. When we are faced with a large project that contains multiple subtasks and dependencies between them, it is crucial to determine a reasonable order of task execution.

For example, consider a software development project. Before we start coding, we may need to complete requirements analysis and design. And before testing, we need to complete the coding. The dependencies between these tasks can be represented by a DAG, and topological sorting is used to determine the order of execution.

As said in “Creativity”: “Creative thinking often requires finding a balance between structure and freedom.” Through topological sorting, project managers can ensure the structure of the project while giving the team enough freedom to stimulate their creativity. creativity.

6. C/C + + Implementation (C/C + + Implementation)

6.1 Using Adjacency List to Represent DAG (Using Adjacency List to Represent DAG)

In computer science, Directed Acyclic Graph (DAG) is a very important data structure that can be used to represent dependencies between tasks. Adjacency lists are a common way to represent DAGs.

An adjacency list is an array in which each element is a list representing all other vertices reachable from a vertex. This representation is both concise and efficient.

#include <vector>
#include <list>
using namespace std;

class Graph {
    int V; //Number of vertices
    list<int> *adj; // Adjacency list (Adjacency list)

public:
    Graph(int V); // Constructor
    void addEdge(int v, int w); // Add an edge
};

6.2 Topological Sorting using DFS (Topological Sorting using DFS)

A common approach to topological sorting is to use depth-first search (DFS). The core idea of this method is to start from a vertex without a predecessor, recursively visit all reachable vertices, and then arrange these vertices in reverse order according to the time of completion of the visit.

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> & amp;Stack) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); + + i)
        if (!visited[*i])
            topologicalSortUtil(*i, visited, Stack);

    Stack.push(v);
}

void Graph::topologicalSort() {
    stack<int> Stack;
    bool *visited = new bool[V];
    for (int i = 0; i < V; i + + )
        visited[i] = false;

    for (int i = 0; i < V; i + + )
        if (visited[i] == false)
            topologicalSortUtil(i, visited, Stack);

    while (Stack.empty() == false) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

The advantage of this approach is that it can easily handle complex dependencies and can be done in a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.

6.3 Using in-degree table for topological sorting (Topological Sorting using In-degree Table)

Another common topological sorting method is to use an in-degree table. The indegree table is an array that records the indegree of each vertex (the number of edges pointing to that vertex).

The core idea of this method is to repeatedly find the vertex with in-degree 0 and remove all edges starting from this vertex until all vertices have been visited.

void Graph::topologicalSortUsingIndegree() {
    vector<int> indegree(V, 0);
    for (int u = 0; u < V; u + + ) {
        list<int>::iterator itr;
        for (itr = adj[u].begin(); itr != adj[u].end(); itr + + )
            indegree[*itr] + + ;
    }

    queue<int> q;
    for (int i = 0; i < V; i + + )
        if (indegree[i] == 0)
            q.push(i);

    int cnt = 0;
    vector<int> top_order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        top_order.push_back(u);
        list<int>::iterator itr;
        for (itr = adj[u].begin(); itr != adj[u].end(); itr + + )
            if (--indegree[*itr] == 0)
                q.push(*itr);
        cnt + + ;
    }

    if (cnt != V) {
        cout << "There exists a cycle in the graph\\
";
        return;
    }

    for (int i = 0; i < top_order.size(); i + + )
        cout << top_order[i] << " ";
    cout << endl;
}

The advantage of this approach is that it can easily handle large DAGs and can be completed in O(V + E) time complexity.

As said in “Thinking, Fast and Slow”: “The way we think is shaped by our experience and knowledge.” These two topological sorting methods are based on our in-depth understanding of graph theory and the results of accumulated experience . They all provide us with an effective way to deal with complex dependencies and task scheduling issues.

7. Topological sorting from the perspective of advanced mathematics< /font>