轉載：http://blog.csdn.net/yxmmao/article/details/51586540

1 . 創建圖的鄰接矩陣數據結構

public class MGraph {/*圖的鄰接矩陣表示*/int vexs; //圖中結點數目char data[]; //存放結點數據int [][]weight; //存放邊public MGraph(int ve){vexs=ve;data=new char[ve];weight=new int[ve][ve];} }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

2 . 創建圖的鄰接矩陣，顯示鄰接矩陣，實現圖的深度遍歷

import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue;public class GraphMetrix {/*圖的鄰接矩陣表示，各中操作*//*創建圖的鄰接矩陣*/public void CreateGraph(MGraph graph,int vexs,char data[],int [][]weight){int i,j;for(i=0;i<vexs;i++){graph.data[i]=data[i];for(j=0;j<vexs;j++){graph.weight[i][j]=weight[i][j];}}}/*顯示圖的鄰接矩陣*/public void ShowGraph(MGraph graph){int vexs=graph.vexs;int [][]weight=graph.weight;int i,j;for(i=0;i<vexs;i++){System.out.print(graph.data[i]+":");for(j=0;j<vexs;j++){System.out.print(weight[i][j]+" ");}System.out.println();}}/*獲取當前頂點K的第一個鄰接頂點位置*/public int GetFirst(MGraph graph,int k){int i;if(k<0||k>graph.vexs-1){System.out.println("參數k值超出范圍");return -1;}for(i=0;i<graph.vexs;i++){if(graph.weight[k][i]==1)return i;}return -1;}/*獲取當前頂點K的第t個鄰接頂點下一個鄰接頂點的位置*/public int GetNext(MGraph graph,int k,int t){int i;if(k<0||k>graph.vexs-1||t<0||t>graph.vexs-1){System.out.println("參數k或t值超出范圍");return -1;}for(i=t+1;i<graph.vexs;i++){if(graph.weight[k][i]==1)return i;}return -1;}/*遞歸方式深度優先遍歷圖的鄰接矩陣*/public void DFSVGraph(MGraph graph,int k,int visited[]){/*graph為圖的鄰接矩陣表示，k為起始頂點，visited[]為訪問過標記數組*/int u; //k的鄰接頂點System.out.print(graph.data[k]+", ");visited[k]=1;//表示頂點k被訪問過u=GetFirst(graph,k);//獲取k的第一個鄰接頂點uwhile(u!=-1){if(visited[u]==0){ //如果u未被訪問過，則遞歸訪問u的鄰接點DFSVGraph(graph,u,visited);}u=GetNext(graph,k,u);//獲取k的下一個鄰接頂點}}/*廣度優先遍歷圖的鄰接矩陣*/public void BFSVGraph(MGraph graph,int k,int visited[]){/*graph為圖的鄰接矩陣表示，k為起始頂點，visited[]為訪問過標記數組*/Queue <Integer>queue=new LinkedList <Integer>();int u;queue.add(k);//頂點k進入隊列visited[k]=1;//頂點k標記被訪問過while(!queue.isEmpty()){u=queue.remove();//取出隊列頂元素System.out.print(graph.data[u]+", ");int v=GetFirst(graph,u);//獲取u的第一個鄰接頂點v while(v!=-1){if(visited[v]==0){ //如果v未被訪問過，則遞歸訪問v的鄰接點queue.add(v);visited[v]=1;//頂點v標記被訪問過}v=GetNext(graph,u,v);//獲取u的下一個鄰接頂點} }}public static void main(String args[]){char []data=new char[]{'A','B','C','D','E'};int vexs=data.length;int visited[]=new int [vexs];/*定義訪問標記數組*/int [][]weight=new int[][]{{0,1,0,0,1},{1,0,1,1,0},{0,1,0,0,0},{0,1,0,0,1},{1,0,0,1,0}};for(int i=0;i<vexs;i++){/*初始化訪問標記數組*/visited[i]=0;}MGraph graph=new MGraph(vexs);GraphMetrix gam=new GraphMetrix();gam.CreateGraph(graph,vexs,data,weight);gam.ShowGraph(graph);//gam.DFSVGraph(graph, 0, visited);gam.BFSVGraph(graph, 0, visited);}}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113
• 114
• 115
• 116
• 117
• 118
• 119
• 120
• 121
• 122
• 123
• 124
• 125

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113
• 114
• 115
• 116
• 117
• 118
• 119
• 120
• 121
• 122
• 123
• 124

總結

以上是生活随笔為你收集整理的java 图的邻接矩阵表示，深度优先遍历，广度优先遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。