数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历
程序员文章站
2022-06-13 11:46:43
...
图有两种表示方法:邻接矩阵和l邻接表,这里使用java实现一个简单的邻接矩阵。
来个栗子尝一尝:
使用邻接矩阵来表示该图
首先定义顶点数组,以及二维数组代表邻接矩阵:
private int MAXVEX = 0;//顶点个数,顶点数组长度
private VertexArray<T>[] vertexArray = null;//顶点数组
private int[][] adjacencyArray = null;//邻接矩阵
/**
* 内部类,自定义顶点类型
*
* @param <T>
*/
private class VertexArray<T> {
private T vertexDate = null;//数据域
private boolean visited = false;//标记顶点是否访问过
//此处省略get,set方法
}
通过构造方法初始化顶点数组及邻接矩阵
/**
* 构造方法初始化顶点数组,邻接矩阵
*
* @param vertexArray
*/
public AdjacencyMatrix(T[] vertexArray) {
this.MAXVEX = vertexArray.length;
this.vertexArray = new VertexArray[MAXVEX];
this.adjacencyArray = new int[MAXVEX][MAXVEX];
for (int i = 0; i < MAXVEX; i++) {
this.vertexArray[i] = new VertexArray<T>();
this.vertexArray[i].setVertexDate(vertexArray[i]);
for (int j = 0; j < MAXVEX; j++) {
this.adjacencyArray[i][j] = 0;
}
}
}
利用二维数组传入各顶点之间的边关系:
/**
* 二维数组传入边关系
*/
public boolean buildMatrix(T[][] side) {
boolean state = false;
int p1 = -1;
int p2 = -1;
for (int i = 0; i < side.length; i++) {
p1 = getPosition(side[i][0]);
p2 = getPosition(side[i][1]);
if (p1 != -1 && p2 != -1) {
this.adjacencyArray[p1][p2] = 1;
this.adjacencyArray[p2][p1] = 1;
if (!state) state = true;
}
}
return state;
}
/**
* 返回顶点位置
*/
private int getPosition(T vertex) {
for (int i = 0; i < MAXVEX; i++) {
if (vertex.equals(this.vertexArray[i].getVertexDate())) {
return i;
}
}
return -1;
}
广度优先遍历(利用栈实现遍历):
/**
* 广度优先遍历
*/
public void BFS() {
Queue<VertexArray> queue = new LinkedList<VertexArray>();
for (int i = 0; i < MAXVEX; i++) {
if (!this.vertexArray[i].getVisited()) {
queue.offer(this.vertexArray[i]);
this.vertexArray[i].setVisited(true);
System.out.println(this.vertexArray[i].getVertexDate());
while (queue.size() != 0) {
queue.poll();
for (int j = 0; j < MAXVEX; j++) {
if (this.adjacencyArray[i][j] == 1 && !this.vertexArray[j].getVisited()) {
queue.offer(this.vertexArray[j]);
this.vertexArray[j].setVisited(true);
System.out.println(this.vertexArray[j].getVertexDate());
}
}
}
}
}
}
测试代码:
public class AdjacencyMatrixTest {
public static void main(String[] args) {
String[] ver = {"v0", "v1","v2","v3","v4","v5"};
AdjacencyMatrix<String> adj=new AdjacencyMatrix<String>(ver);
boolean state=adj.buildMatrix(new String[][]{
{"v0","v1"},
{"v0","v2"},
{"v0","v3"},
{"v1","v2"},
{"v1","v4"},
{"v2","v3"},
{"v3","v4"},
{"v4","v5"}
});
System.out.println(state);
adj.BFS();
}
}
上一篇: 图 邻接矩阵 深度优先遍历 广度优先遍历
推荐阅读
-
无向图 深度优先遍历 c语言实现
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
(浙大-19-夏-数据结构学习笔记+代码)图的遍历+深度优先+广度优先(Graph)
-
PHP实现图的邻接矩阵表示及几种简单遍历算法分析
-
无向图的邻接矩阵和邻接表实现各种操作 -- C++语言描述
-
数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历
-
数据结构之图:邻接矩阵和邻接表、深度优先遍历和广度优先遍历
-
邻接矩阵无向图的深度优先遍历C/C++代码实现