Java如何實(shí)現(xiàn)拓?fù)渑判蛩惴?/h1>

發(fā)布時(shí)間：2021-06-16 13:50:06 來源：億速云 閱讀：239 作者：小新 欄目：開發(fā)技術(shù)

這篇文章主要介紹了Java如何實(shí)現(xiàn)拓?fù)渑判蛩惴?，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、介紹

百科上這么定義的：

對(duì)一個(gè)有向無環(huán)圖(Directed Acyclic Graph簡(jiǎn)稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個(gè)線性序列，使得圖中任意一對(duì)頂點(diǎn)u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡(jiǎn)稱拓?fù)湫蛄?。?jiǎn)單的說，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉?/p>

為什么會(huì)有拓?fù)渑判?？拓?fù)渑判蛴泻巫饔茫?/p>

舉個(gè)例子，學(xué)習(xí)java系列的教程

就比如學(xué)習(xí)java系類(部分)從java基礎(chǔ)，到j(luò)sp/servlet，到ssm，到springboot，springcloud等是個(gè)循序漸進(jìn)且有依賴的過程。在jsp學(xué)習(xí)要首先掌握java基礎(chǔ)和html基礎(chǔ)。學(xué)習(xí)框架要掌握jsp/servlet和jdbc之類才行。那么，這個(gè)學(xué)習(xí)過程即構(gòu)成一個(gè)拓?fù)湫蛄小．?dāng)然這個(gè)序列也不唯一，你可以對(duì)不關(guān)聯(lián)的學(xué)科隨意選擇順序(比如html和java可以隨便先開始哪一個(gè)。)

那上述序列可以簡(jiǎn)單表示為：

二、拓?fù)渑判蛩惴ǚ治?/h3>

從DGA圖中找到一個(gè)沒有前驅(qū)的頂點(diǎn)輸出。(可以遍歷，也可以用優(yōu)先隊(duì)列維護(hù))

刪除以這個(gè)點(diǎn)為起點(diǎn)的邊。(它的指向的邊刪除，為了找到下個(gè)沒有前驅(qū)的頂點(diǎn))

重復(fù)上述，直到最后一個(gè)頂點(diǎn)被輸出。如果還有頂點(diǎn)未被輸出，則說明有環(huán)！

對(duì)于上圖的簡(jiǎn)單序列，可以簡(jiǎn)單描述步驟為：

1：刪除1或2輸出

新建node類，包含節(jié)點(diǎn)數(shù)值和它的指向(這里直接用list集合替代鏈表了)

一個(gè)數(shù)組包含node(這里默認(rèn)編號(hào)較集中)。初始化，添加每個(gè)節(jié)點(diǎn)指向的時(shí)候同時(shí)被指的節(jié)點(diǎn)入度+1！(A—>C)那么C的入度+1；

掃描一遍所有node。將所有入度為0的點(diǎn)加入一個(gè)棧(隊(duì)列)。

當(dāng)棧(隊(duì)列)不空的時(shí)候，拋出其中任意一個(gè)node(棧就是尾，隊(duì)就是頭，順序無所謂，上面分析了只要同時(shí)入度為零可以隨便選擇順序)。將node輸出，并且node指向的所有元素入度減一。如果某個(gè)點(diǎn)的入度被減為0，那么就將它加入棧(隊(duì)列)。

重復(fù)上述操作，直到棧為空。

這里主要是利用?；蛘哧?duì)列儲(chǔ)存入度只為0的節(jié)點(diǎn)，只需要初次掃描表將入度為0的放入棧(隊(duì)列)中。

• 這里你或許會(huì)問為什么。

• 因?yàn)楣?jié)點(diǎn)之間是有相關(guān)性的，一個(gè)節(jié)點(diǎn)若想入度為零，那么它的父節(jié)點(diǎn)(指向節(jié)點(diǎn))肯定在它為0前入度為0，拆除關(guān)聯(lián)箭頭。從父節(jié)點(diǎn)角度，它的這次拆除聯(lián)系，可能導(dǎo)致被指向的入讀為0，也可能不為0(還有其他節(jié)點(diǎn)指向兒子)

至于具體demo：

package 圖論;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class tuopu {
	static class node
	{
		int value;
		List<Integer> next;
		public node(int value) {
			this.value=value;
			next=new ArrayList<Integer>();
		}
		public void setnext(List<Integer>list) {
			this.next=list;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		node []nodes=new node[9];//儲(chǔ)存節(jié)點(diǎn)
		int a[]=new int[9];//儲(chǔ)存入度
		List<Integer>list[]=new ArrayList[10];//臨時(shí)空間，為了存儲(chǔ)指向的集合
		for(int i=1;i<9;i++)
		{
			nodes[i]=new node(i);
			list[i]=new ArrayList<Integer>();
		}
		initmap(nodes,list,a);
		
		//主要流程
		//Queue<node>q1=new ArrayDeque<node>();
		Stack<node>s1=new Stack<node>();
		for(int i=1;i<9;i++)
		{
			//System.out.print(nodes[i].next.size()+" 55 ");
			//System.out.println(a[i]);
			if(a[i]==0) {s1.add(nodes[i]);}
			
		}
		while(!s1.isEmpty())
		{
			node n1=s1.pop();//拋出輸出
		    
			System.out.print(n1.value+" ");
			
			List<Integer>next=n1.next;
			for(int i=0;i<next.size();i++)
			{
				a[next.get(i)]--;//入度減一
				if(a[next.get(i)]==0)//如果入度為0
				{
					s1.add(nodes[next.get(i)]);
				}
			}
		}
	}

	private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
		list[1].add(3);
		nodes[1].setnext(list[1]);
		a[3]++;
		list[2].add(4);list[2].add(6);
		nodes[2].setnext(list[2]);
		a[4]++;a[6]++;
		list[3].add(5);
		nodes[3].setnext(list[3]);
		a[5]++;
		list[4].add(5);list[4].add(6);
		nodes[4].setnext(list[4]);
		a[5]++;a[6]++;
		list[5].add(7);
		nodes[5].setnext(list[5]);
		a[7]++;
		list[6].add(8);
		nodes[6].setnext(list[6]);
		a[8]++;
		list[7].add(8);
		nodes[7].setnext(list[7]);
		a[8]++;
		
	}
}

輸出結(jié)果

2 4 6 1 3 5 7 8

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java如何實(shí)現(xiàn)拓?fù)渑判蛩惴ā边@篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!