地图是否存在一个路径使的可以从起始点(图的左上角)走出去(到达另一个点,一般为图的右下角)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;//图
public class Graph {
private ArrayList<String> vertextList;//存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges;//表示边的数目
private boolean[] isVisited;
public static void main(String[] args) {int n = 5;//结点个数
String vertexs[] = {"A", "B", "C", "D", "E"};
Graph graph = new Graph(n);
//添加结点
for (int i = 0; i < vertexs.length; i++) {
graph.insertVertex(vertexs[i]);
}
//添加边
//A-B A-C B-C B-D B-E
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);graph.showGraph();
System.out.println("\n深度遍历");
graph.dfs();
System.out.println("\n广度遍历");
graph.bfs();
}public Graph(int n) {
this.edges = new int[n][n];
this.vertextList = new ArrayList<String>(n);
this.numOfEdges = 0;}
//遍历所有结点,进行广度优先遍历
private void bfs() {
isVisited = new boolean[5];
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}}
//对一个结点进行广度优先遍历
private void bfs(boolean[] isVisited, int i) {
int u;//表示队列的头结点
int w;//邻接结点
//队列
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(getValueByIndex(i) + "->");
isVisited[i] = true;
//将结点加入队列
queue.add(i);
while (!queue.isEmpty()) {
//拿到队列头结点
u = queue.removeFirst();
//得到邻接结点
w = getFirstNeighbor(u);
while (w != -1) {
if (!isVisited[w]) {
System.out.print(getValueByIndex(w) + "->");
isVisited[w] = true;
//入队
queue.addLast(w);
}
//w已经访问过了,找下一个邻接结点
w = getNextNeighbor(u, w);
}
}}
//重载dfs,遍历所有结点
public void dfs() {
isVisited = new boolean[5];
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
//深度优先遍历算法
private void dfs(boolean[] isVisited, int i) {
//访问
System.out.print(getValueByIndex(i) + "->");
//将结点设置为已经访问
isVisited[i] = true;
//找到i的领接结点
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isVisited[w]) {
dfs(isVisited, w);
}
//如果w已经被访问过
w = getNextNeighbor(i, w);
}}
/**
* 得到第一个邻接结点的下标
*
* @param index 给定节点
* @return 返回相邻结点下标
*/
public int getFirstNeighbor(int index) {
for (int i = 0; i < vertextList.size(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}//根据前一个邻接结点的下标来获取下一个邻接结点
public int getNextNeighbor(int v1, int v2) {
for (int i = v2 + 1; i < vertextList.size(); i++) {
if (edges[v1][i] > 0) {
return i;
}
}
return -1;
}
//插入结点
public void insertVertex(String vertex) {
vertextList.add(vertex);
}
/**
* 插入边
*
* @param v1 表示第一个点的下标
* @param v2 表示第二个点的下标
* @param weight 权值
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}public int getNumOfVertex() {
return vertextList.size();
}public int getNumOfEdges() {
return numOfEdges;
}//返回结点的值
public String getValueByIndex(int i) {
return vertextList.get(i);
}//返回权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}//显示图矩阵
public void showGraph() {
for (int[] edge : edges) {
System.out.println(Arrays.toString(edge));
}
}
}