Java數(shù)據(jù)結(jié)構(gòu)之圖的原理與實現(xiàn)

第Java數(shù)據(jù)結(jié)構(gòu)之圖的原理與實現(xiàn)*深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn),類似于樹的先序遍歷

*因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧

*@parami頂點索引

*@paramvisited訪問標(biāo)志數(shù)組

privatevoidDFS(inti,boolean[]visited){

//索引索引標(biāo)記為true,表示已經(jīng)訪問了

visited[i]=true;

System.out.print(vertexs[i].data+"");

//獲取該頂點的邊表頭結(jié)點

LNodenode=vertexs[i].firstEdge;

//循環(huán)遍歷該頂點的鄰接點,采用同樣的方式遞歸搜索

while(node!=null){

if(!visited[node.vertex]){

DFS(node.vertex,visited);

node=node.nextEdge;

*深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,

publicvoidDFS(){

//新建頂點訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點

boolean[]visited=newboolean[vertexs.length];

//初始化所有頂點都沒有被訪問

for(inti=0;ivertexs.length;i++){

visited[i]=false;

System.out.println("DFS:");

/*循環(huán)搜索*/

for(inti=0;ivertexs.length;i++){

//如果對應(yīng)索引的頂點的訪問標(biāo)記為false,則搜索該頂點

if(!visited[i]){

DFS(i,visited);

/*走到這一步,說明頂點訪問標(biāo)記數(shù)組全部為true,說明全部都訪問到了,深度搜索結(jié)束*/

System.out.println();

*廣度優(yōu)先搜索圖,類似于樹的層序遍歷

*因此模仿樹的層序遍歷,同樣借用隊列結(jié)構(gòu)

publicvoidBFS(){

//輔組隊列

QueueIntegerindexLinkedList=newLinkedList();

//新建頂點訪問標(biāo)記數(shù)組,對應(yīng)每個索引對應(yīng)相同索引的頂點數(shù)組中的頂點

boolean[]visited=newboolean[vertexs.length];

//初始化所有頂點都沒有被訪問

for(inti=0;ivertexs.length;i++){

visited[i]=false;

System.out.println("BFS:");

for(inti=0;ivertexs.length;i++){

//如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問

if(!visited[i]){

visited[i]=true;

System.out.print(vertexs[i].data+"");

indexLinkedList.add(i);

//判斷隊列是否有值,有就開始遍歷

if(!indexLinkedList.isEmpty()){

//出隊列

Integerj=indexLinkedList.poll();

LNodenode=vertexs[j].firstEdge;

while(node!=null){

intk=node.vertex;

if(!visited[k]){

visited[k]=true;

System.out.print(vertexs[k].data+"");

//繼續(xù)入隊列

indexLinkedList.add(k);

node=node.nextEdge;

System.out.print("\n");

@Override

publicStringtoString(){

StringBuilderstringBuilder=newStringBuilder();

for(inti=0;ivertexs.length;i++){

stringBuilder.append(i).append("(").append(vertexs[i].data).append("):");

LNodenode=vertexs[i].firstEdge;

while(node!=null){

stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");

node=node.nextEdge;

if(node!=null){

stringBuilder.append("-

}else{

break;

stringBuilder.append("\n");

returnstringBuilder.toString();

publicstaticvoidmain(String[]args){

//頂點數(shù)組添加的先后順序?qū)τ诒闅v結(jié)果有影響

Character[]vexs={'A','B','C','D','E','F','G'};

//邊二維數(shù)組添加的先后順序?qū)τ诒闅v結(jié)果有影響

Character[][]edges={

{'A','C'},

//對于無向圖來說是多余的邊關(guān)系,在linkLast方法中做了判斷,并不會重復(fù)添加

{'A','D'},

{'A','D'},

{'D','A'},

{'A','F'},

{'B','C'},

{'C','D'},

{'E','G'},

{'E','B'},

{'D','B'},

{'F','G'}};

//構(gòu)建圖

UndirectedAdjacencyListCharacterundirectedAdjacencyList=newUndirectedAdjacencyList(vexs,edges);

//輸出圖

System.out.println(undirectedAdjacencyList);

//深度優(yōu)先遍歷

undirectedAdjacencyList.DFS();

//廣度優(yōu)先遍歷

undirectedAdjacencyList.BFS();

}

測試無向圖對應(yīng)的邏輯結(jié)構(gòu)如下：

測試圖的遍歷結(jié)果如下：

4.2有向圖的鄰接表實現(xiàn)

/**

*有向圖鄰接鏈表簡單實現(xiàn)

*{@linkAdjacencyList#AdjacencyList(E[],E[][])}構(gòu)建有向圖

*{@linkAdjacencyList#DFS()}深度優(yōu)先遍歷有向圖

*{@linkAdjacencyList#BFS()}廣度優(yōu)先遍歷有向圖

*{@linkAdjacencyList#toString()}()}輸出有向圖

*@authorlx

publicclassAdjacencyListE{

*頂點類

*@paramE

privateclassNodeE{

*頂點信息

Edata;

*指向第一條依附該頂點的邊

LNodefirstEdge;

publicNode(Edata,LNodefirstEdge){

this.data=data;

this.firstEdge=firstEdge;

*邊表節(jié)點類

privateclassLNode{

*該邊所指向的頂點的索引位置

intvertex;

*指向下一條弧的指針

LNodenextEdge;

*頂點數(shù)組

privateNodeE[]vertexs;

*創(chuàng)建圖

*@paramvexs頂點數(shù)組

*@paramedges邊二維數(shù)組

publicAdjacencyList(E[]vexs,E[][]edges){

/*初始化頂點數(shù)組,并添加頂點*/

vertexs=newNode[vexs.length];

for(inti=0;ivertexs.length;i++){

vertexs[i]=newNode(vexs[i],null);

/*初始化邊表,并添加邊節(jié)點到邊表尾部,即采用尾插法*/

for(E[]edge:edges){

//讀取一條邊的起始頂點和結(jié)束頂點索引值

intp1=getPosition(edge[0]);

intp2=getPosition(edge[1]);

//初始化lnode1邊節(jié)點即表示p1指向p2的邊

LNodelnode1=newLNode();

lnode1.vertex=p2;

//將LNode鏈接到"p1所在鏈表的末尾"

if(vertexs[p1].firstEdge==null){

vertexs[p1].firstEdge=lnode1;

}else{

linkLast(vertexs[p1].firstEdge,