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

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

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

*@parami頂點(diǎn)索引

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

privatevoidDFS(inti,boolean[]visited){

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

visited[i]=true;

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

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

LNodenode=vertexs[i].firstEdge;

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

while(node!=null){

if(!visited[node.vertex]){

DFS(node.vertex,visited);

node=node.nextEdge;

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

publicvoidDFS(){

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

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

//初始化所有頂點(diǎn)都沒有被訪問

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

visited[i]=false;

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

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

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

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

if(!visited[i]){

DFS(i,visited);

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

System.out.println();

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

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

publicvoidBFS(){

//輔組隊(duì)列

QueueIntegerindexLinkedList=newLinkedList();

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

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

//初始化所有頂點(diǎn)都沒有被訪問

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);

//判斷隊(duì)列是否有值,有就開始遍歷

if(!indexLinkedList.isEmpty()){

//出隊(duì)列

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ù)入隊(duì)列

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){

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

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

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

Character[][]edges={

{'A','C'},

//對(duì)于無(wú)向圖來說是多余的邊關(guān)系,在linkLast方法中做了判斷,并不會(huì)重復(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();

}

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

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

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

/**

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

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

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

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

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

*@authorlx

publicclassAdjacencyListE{

*頂點(diǎn)類

*@paramE

privateclassNodeE{

*頂點(diǎn)信息

Edata;

*指向第一條依附該頂點(diǎn)的邊

LNodefirstEdge;

publicNode(Edata,LNodefirstEdge){

this.data=data;

this.firstEdge=firstEdge;

*邊表節(jié)點(diǎn)類

privateclassLNode{

*該邊所指向的頂點(diǎn)的索引位置

intvertex;

*指向下一條弧的指針

LNodenextEdge;

*頂點(diǎn)數(shù)組

privateNodeE[]vertexs;

*創(chuàng)建圖

*@paramvexs頂點(diǎn)數(shù)組

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

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

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

vertexs=newNode[vexs.length];

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

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

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

for(E[]edge:edges){

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

intp1=getPosition(edge[0]);

intp2=getPosition(edge[1]);

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

LNodelnode1=newLNode();

lnode1.vertex=p2;

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

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

vertexs[p1].firstEdge=lnode1;

}else{

linkLast(vertexs[p1].firstEdge,