الفرز الطوبولوجي

:
(G)
0 →
1→
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0

1:
(0), visited[0] = true
. .
0
2:
(1), visited[1] = true
. .
0 1
3:
(2),, visited[2] = true
(3),, visited[3] = true
1 .
0 1 3 2
4:
(4),, visited[4] = true
تمت زيارة القمم 0 و 1 بالفعل. لا مزيد من المكالمات العودية.
المكدس 0 1 3 2 4
الخطوة 5:
الفرز الطوبولوجي (5) ، تمت
الزيارة [5] = صحيح تم زيارة الذراعين 2 و 0 بالفعل. لا مزيد من المكالمات المتكررة ،
المكدس 0 1 3 2 4 5
الخطوة 6:
سحب جميع عناصر المكدس من الأعلى إلى الأسفل

C ++

//   C++     DAG
 
#include<iostream>
#include <list>
#include <stack>
using namespace std;
  
//    
class Graph
{
    int V;	//  
  
    //    ,   
    list<int> *adj;
  
    // ,  topologicalSort
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
    Graph(int V);   // 
  
     //      
    void addEdge(int v, int w);
  
    //    
    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); // Add w to v’s list.
}
  
//  ,  topologicalSort
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);
}
  
//     . 
//   topologicalSortUtil()
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();
    }
}
  
//    
int main()
{
    //  ,    
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
  
    cout << "Following is a Topological Sort of the given graph \n";
    g.topologicalSort();
  
    return 0;
}

جافا

//   Java    
import java.io.*;
import java.util.*;
  
//          
class Graph
{
    private int V;   //  
    private LinkedList<Integer> adj[]; //  
  
    // 
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }
  
    //      
    void addEdge(int v,int w) { adj[v].add(w); }
  
    //  ,  topologicalSort
    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        //      
        visited[v] = true;
        Integer i;
  
        //       
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }
  
        //       
        stack.push(new Integer(v));
    }
  
    //     .
    //   topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();
  
        //     
        boolean visited[] = new boolean[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)
            System.out.print(stack.pop() + " ");
    }
  
    //   
    public static void main(String args[])
    {
        //  ,    
        Graph g = new Graph(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);
  
        System.out.println("Following is a Topological " +
                           "sort of the given graph");
        g.topologicalSort();
    }
}
//      (Aakash Hasija)

بيثون

#  Python       DAG   import defaultdict
  
#   
class Graph:
    def __init__(self,vertices):
        self.graph = defaultdict(list) #dictionary containing adjacency List
        self.V = vertices #No. of vertices
  
    #      
    def addEdge(self,u,v):
        self.graph[u].append(v)
  
    #  ,  topologicalSort
    def topologicalSortUtil(self,v,visited,stack):
  
        #     
        visited[v] = True
  
        #       
        for i in self.graph[v]:
            if visited[i] == False:
                self.topologicalSortUtil(i,visited,stack)
  
        #       
        stack.insert(0,v)
  
    #     . 
    #   topologicalSortUtil()
    def topologicalSort(self):
        #     
        visited = [False]*self.V
        stack =[]
  
        #    
        #       
        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(i,visited,stack)
  
        #   
        print stack
  
g= Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
  
print "Following is a Topological Sort of the given graph"
g.topologicalSort()
#     (Neelam Yadav)

<b>:</b>
Following is a Topological Sort of the given graph
5 4 2 3 1 0

مقالات ذات صلة

المراجع