c语言拓扑排序界面_C和C ++中的拓扑排序

桃扇骨 2022-12-07 13:56 169阅读 0赞

![da779e4a3ad6a2dc782747c884352980.png][]

c语言拓扑排序界面

Here you will learn and get program for topological sort in C and C++.

在这里，您将学习并获得使用C和C ++进行拓扑排序的程序。

We know many sorting algorithms used to sort the given data. It may be numeric data or strings. Take a situation that our data items have relation. They are related with some condition that one should happen only after other one happened.

我们知道许多用于对给定数据进行排序的排序算法。 它可以是数字数据或字符串。 假设我们的数据项有关联。 它们与某种条件相关，即一个条件只有在另一个条件发生之后才应该发生。

For example shoe should wear after socks only. Another example, in academic course one should study Applications of Algorithms subject only after studying Designing of Algorithms. And Designing of Algorithms should study only after learning any programming language. We can observe that a work requires pre-requisite. In these situations we represent our data in a graph and we use directed edges from pre-requisite to next one. And we apply Topological sorting to solve.

例如，鞋只应在袜子后穿。 另一个例子，在学术课程中，只有在学习了算法设计之后才应该学习算法应用学科。 算法设计应该仅在学习任何编程语言之后才进行学习。 我们可以看到，一项工作需要先决条件。 在这些情况下，我们用图表表示数据，并使用从先决条件到下一个的有向边。 并且我们应用拓扑排序来解决。

Most important condition to do Topological sorting on any graph is that Graph should be Connected Directed Acyclic graph. It is not possible to apply Topological sorting either graph is not directed or it have a Cycle.

在任何图上进行拓扑排序的最重要条件是图应为Connected Directed Acyclic图。 无法应用拓扑排序，要么图形未定向，要么具有循环。

One more condition is that graph should contain a sink vertex. The vertex which doesn’t have any outgoing edge is called sink vertex. Idea behind this sink vertex is that if every vertex has an outgoing edge in a directed graph it definitely forms a cycle, which violates the condition.

还有一个条件是图形应包含一个汇点顶点。 没有任何输出边的顶点称为宿顶点。 该汇聚顶点背后的想法是，如果每个顶点在有向图中都有出线边，则它肯定会形成一个循环，这违反了条件。

**Note:** Topological sorting on a graph results non-unique solution

**注意：**对图形进行拓扑排序会导致非唯一解

### 拓扑排序示例 **(**Topological Sort Example**)** ###

![Topological Sort in C and C++][Topological Sort in C and C]

**Solving Using In-degree Method**

**使用度数法求解**

**Step 1:** Write in-degree of all vertices:

**步骤1：**写入所有顶点的度数：

<table> 
 <tbody> 
  <tr> 
   <td>Vertex</td> 
   <td>in-degree</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

**Step 2:** Write the vertex which has in-degree 0 (zero) in solution. Here vertex 1 has in-degree 0. So,

**步骤2：**在解中写入度数为0(零)的顶点。 此处顶点1的度数为0。因此，

**Solution is: 1 -> (not yet completed )**

**解决方法是：1->(尚未完成)**

Decrease in-degree count of vertices who are adjacent to the vertex which recently added to the solution.

减少与最近添加到解决方案中的顶点相邻的顶点的度数计数。

Here vertex 1 is recently added to the solution. Vertices 2 and 3 are adjacent to vertex 1. So decrease the in-degree count of those and update.

这里顶点1最近被添加到解决方案中。 顶点2和3与顶点1相邻。因此，减少这些顶点的入度计数并进行更新。

Updated result is:

更新结果是：

<table> 
 <tbody> 
  <tr> 
   <td>Vertex</td> 
   <td>in-degree</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>Already added to solution</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> 顶点 </td> 
   <td> 学位 </td> 
  </tr> 
  <tr> 
   <td> 1个 </td> 
   <td> 已经添加到解决方案中 </td> 
  </tr> 
  <tr> 
   <td> 2 </td> 
   <td> 0 </td> 
  </tr> 
  <tr> 
   <td> 3 </td> 
   <td> 0 </td> 
  </tr> 
  <tr> 
   <td> 4 </td> 
   <td> 2 </td> 
  </tr> 
 </tbody> 
</table>

Again repeat the same thing which we have done in step1 that, write the vertices which have degree 0 in solution.

再次重复我们在步骤1中所做的相同的事情，编写在解中具有度0的顶点。

Here we can observe that two vertices (2 and 3) have in-degree 0 (zero). Add any vertex into the solution.

在这里我们可以观察到两个顶点(2和3)的度数为0(零)。 将任何顶点添加到解决方案中。

Note that, you may add vertex 2 into solution, and I may add vertex 3 to solution. That means the solution to topological sorting is not unique.

请注意，您可以将顶点2添加到解决方案中，而我可以将顶点3添加到解决方案中。 这意味着拓扑排序的解决方案不是唯一的。

Now add vertex 3.

现在添加顶点3。

**Solution is: 1->3->**

**解决方案是：1-> 3->**

Again decrease the in-degree count of vertices which are adjacent to vertex 3.

再次减少与顶点3相邻的顶点的度数计数。

Updated result is:

更新结果是：

<table> 
 <tbody> 
  <tr> 
   <td>Vertex</td> 
   <td>in-degree</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>Already added to solution</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>Already added to solution</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>1</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> 顶点 </td> 
   <td> 学位 </td> 
  </tr> 
  <tr> 
   <td> 1个 </td> 
   <td> 已经添加到解决方案中 </td> 
  </tr> 
  <tr> 
   <td> 2 </td> 
   <td> 0 </td> 
  </tr> 
  <tr> 
   <td> 3 </td> 
   <td> 已经添加到解决方案中 </td> 
  </tr> 
  <tr> 
   <td> 4 </td> 
   <td> 1个 </td> 
  </tr> 
 </tbody> 
</table>

Now add vertex 2 to solution because it only has in-degree 0.

现在将顶点2添加到解决方案中，因为它只有度数为0。

**Solution is: 1->3->2->**

**解决方案是：1-> 3-> 2->**

Updated result is:

更新结果是：

<table> 
 <tbody> 
  <tr> 
   <td>Vertex</td> 
   <td>in-degree</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>Already added to solution</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Already added to solution</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>Already added to solution</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> 顶点 </td> 
   <td> 学位 </td> 
  </tr> 
  <tr> 
   <td> 1个 </td> 
   <td> 已经添加到解决方案中 </td> 
  </tr> 
  <tr> 
   <td> 2 </td> 
   <td> 已经添加到解决方案中 </td> 
  </tr> 
  <tr> 
   <td> 3 </td> 
   <td> 已经添加到解决方案中 </td> 
  </tr> 
  <tr> 
   <td> 4 </td> 
   <td> 0 </td> 
  </tr> 
 </tbody> 
</table>

Finally add 4 to solution.

最后将4添加到解决方案中。

**Final solution is: 1->3->2->4**

**最终的解决方案是：1-> 3-> 2-> 4**

## C中的拓扑排序程序 **(**Program for Topological Sort in C**)** ##

#include <stdio.h>
     
    int main(){
    	int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;
     
    	printf("Enter the no of vertices:\n");
    	scanf("%d",&n);
     
    	printf("Enter the adjacency matrix:\n");
    	for(i=0;i<n;i++){
    		printf("Enter row %d\n",i+1);
    		for(j=0;j<n;j++)
    			scanf("%d",&a[i][j]);
    	}
     
    	for(i=0;i<n;i++){
            indeg[i]=0;
            flag[i]=0;
        }
     
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                indeg[i]=indeg[i]+a[j][i];
     
        printf("\nThe topological order is:");
     
        while(count<n){
            for(k=0;k<n;k++){
                if((indeg[k]==0) && (flag[k]==0)){
                    printf("%d ",(k+1));
                    flag [k]=1;
                }
     
                for(i=0;i<n;i++){
                    if(a[i][k]==1)
                        indeg[k]--;
                }
            }
     
            count++;
        }
     
        return 0;
    }

**Output**

**输出量**

*Enter the no of vertices:* *4* *Enter the adjacency matrix:* *Enter row 1* *0 1 1 0* *Enter row 2* *0 0 0 1* *Enter row 3* *0 0 0 1* *Enter row 4* *0 0 0 0*

*输入顶点数：* *4* *输入邻接矩阵：* *输入行1* *0 1 1 0* *输入行2* *0 0 0 1* *输入行3* *0 0 0 1* *输入行4* *0 0 0 0*

*The topological order is:1 2 3 4*

*拓扑顺序为：1 2 3 4*

## C ++拓扑排序程序 **(**Program for Topological Sort in C++**)** ##

#include<iostream>
     
    using namespace std;
     
    int main(){
    	int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;
     
    	cout<<"Enter the no of vertices:\n";
    	cin>>n;
     
    	cout<<"Enter the adjacency matrix:\n";
    	for(i=0;i<n;i++){
    		cout<<"Enter row "<<i+1<<"\n";
    		for(j=0;j<n;j++)
    			cin>>a[i][j];
    	}
     
    	for(i=0;i<n;i++){
            indeg[i]=0;
            flag[i]=0;
        }
     
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                indeg[i]=indeg[i]+a[j][i];
     
        cout<<"\nThe topological order is:";
     
        while(count<n){
            for(k=0;k<n;k++){
                if((indeg[k]==0) && (flag[k]==0)){
                    cout<<k+1<<" ";
                    flag[k]=1;
                }
     
                for(i=0;i<n;i++){
                    if(a[i][k]==1)
                        indeg[k]--;
                }
            }
     
            count++;
        }
     
        return 0;
    }

Comment below if you have any queries related to above program for topological sort in C and C++.

如果您对以上程序在C和C ++中的拓扑排序有任何疑问，请在下面评论。

> 翻译自: [https://www.thecrazyprogrammer.com/2017/05/topological-sort.html][https_www.thecrazyprogrammer.com_2017_05_topological-sort.html]

c语言拓扑排序界面

[da779e4a3ad6a2dc782747c884352980.png]: /images/20221123/224730923a7d40099277fc77e62b2de8.png
[Topological Sort in C and C]: /images/20221123/b83f01e9b3894ff8a5ea1991c76aa73a.png
[https_www.thecrazyprogrammer.com_2017_05_topological-sort.html]: https://www.thecrazyprogrammer.com/2017/05/topological-sort.html