拓扑排序（Java实现）

阳光穿透心脏的1/2处 2022-06-17 06:25 210阅读 0赞

仿照前面那个c++写的，具体思路请看上一个博客，只是用Java实现了一下

class Node\{  
    public int adjvex;  
    public Node next;  
\}  
public class Sort \{  
    private ArrayList<Integer> mystack=new ArrayList<>();  
    private Node p;  
    private Node\[\] adj;  
    private int\[\] indegree;  
    private int n;  
    private int m;  
    private int create(int n,int m)\{  
        this.n=n;  
        this.m=m;  
        adj=new Node\[n+1\];  
        int i;  
        Node p;  
        for(i=1;i<=n;i++)  
        \{  
            adj\[i\]=new Node();  
            adj\[i\].adjvex=i;  
            adj\[i\].next=null;  
        \}  
        for(i=1;i<=m;i++)  
        \{  
            System.out.println("请输入第"+i+"条边:");  
            int u,v;  
            Scanner sc = new Scanner(System.in);  
            u=sc.nextInt();  
            v=sc.nextInt();  
            p=new Node();  
            //把边的终点作为值,放到起点所在的链表中，把值插入链表的表头，减少遍历  
            p.adjvex=v;  
            p.next=adj\[u\].next;  
            adj\[u\].next=p;  
        \}  
        return 1;  
    \}  
    public void print()\{  
        int i;  
        Node p;  
        for(i=1;i<=n;i++)  
        \{  
            p=adj\[i\];  
            /\*  
             \* 打印以i为起点的所有边  
             \*/  
            while(p!=null)  
            \{  
                System.out.print(p.adjvex+" ");  
                p=p.next;  
            \}  
            System.out.println();  
        \}  
    \}  
    public void topsort()  
    \{  
        int i;  
        Node p;  
        indegree=new int\[n+1\];  
        for(i=1;i<=n;i++)  
        \{  
            p=adj\[i\].next;  
            while(p!=null)  
            \{  
                //算出所有点的入度个数  
                indegree\[p.adjvex\]++;  
                p=p.next;  
            \}  
        \}  
        for(i=1;i<=n;i++)  
        \{  
            //如果某个点的入度为0，就把这个点插入队列  
            if(indegree\[i\]==0)  
                mystack.add(i);  
        \}  
        int count=0;  
        //如果有某个点的入度为0了，就把这个点放入队列，然后取队列中的元素来排序  
        while(mystack.size()!=0)  
        \{  
            //打印队列中的元素并删除。  
            i=mystack.remove(mystack.size()-1);  
            System.out.print(i+" ");  
            count++;  
            //没删除一个队列中的元素，就把由队列中的点和自己产生入度的点的元素的度-1，如果改点度数变为0了，则插入队列  
            for(p=adj\[i\].next;p!=null;p=p.next)  
            \{  
                int k=p.adjvex;  
                indegree\[k\]--;  
                if(indegree\[k\]==0)  
                    mystack.add(k);  
            \}  
        \}  
        System.out.println();  
        if(count<n)\{  
            System.out.println("有回路！");  
        \}  
    \}  
    public static void main(String\[\] args)\{  
        Sort sort=new Sort();  
        int n;  
        int m;  
        System.out.println("请输入顶点数及边数：");  
        Scanner sc = new Scanner(System.in);  
        n=sc.nextInt();  
        m=sc.nextInt();  
        sort.create(n,m);  
        System.out.println("输入的邻接表为：");  
        sort.print();  
        System.out.println("拓扑排序结果为：");  
        sort.topsort();  
    \}  
\}

效果：

请输入顶点数及边数：  
6 8  
请输入第1条边:  
1 2  
请输入第2条边:  
1 3  
请输入第3条边:  
1 4  
请输入第4条边:  
3 2  
请输入第5条边:  
3 5  
请输入第6条边:  
4 5  
请输入第7条边:  
6 4  
请输入第8条边:  
6 5  
输入的邻接表为：  
1 4 3 2  
2  
3 5 2  
4 5  
5  
6 5 4  
拓扑排序结果为：  
6 1 3 2 4 5