您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

图的遍历(图文)

第十三双眼睛2023-10-22【数据结构与算法】人已围观

简介图的遍历

图的遍历
包括深度优先遍历与广度优先遍历

package com.xingchen.day015;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Graph {
private int[][] edges;//邻结矩阵
private int numOfEdges;//边
private List<String> vertexList;//顶点集合
private boolean[] isVisited;
public static void main(String[] args) {
//测试
int n = 5; //节点得个数
String[] vertex = {"a", "b", "c", "d", "e"};
Graph graph = new Graph(5);
for (String value : vertex) {
graph.insert(value);
}
//添加边
graph.insertEdges(0,1,1);
graph.insertEdges(0,2,1);
graph.insertEdges(1,2,1);
graph.insertEdges(1,3,1);
graph.insertEdges(1,4,1);
//graph.showGraph();
//graph.dfs();
graph.bfs();
}
public Graph(int n) {
this.edges = new int[n][n];
vertexList = new ArrayList<>(n);
numOfEdges = 0;
isVisited = new boolean[5];
}
//返回临接节点的下标，存在就返回不存在就返回-1
public int getFirstNeighbor(int index) {
for (int j=0; j<vertexList.size();j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
public int getNextNeighbor(int v1,int v2) {
for (int j = v2+1;j<vertexList.size();j++) {
if (edges[v1][j]>0) {
return j;
}
}
return -1;
}
public void dfs(boolean[] isVisited,int i) {
//访问该节点
System.out.println(getValueByIndex(i));
//将该节点设置为已访问
isVisited[i] = true;
int w = getFirstNeighbor(i);
while (w != -1) {
//如果没有被访问
if (!isVisited[w]) {
dfs(isVisited,w);
} else {
//如果被访问
w = getNextNeighbor(i, w);
}
}
}
public void dfs() {
//遍历所有节点
for (int i=0;i<vertexList.size();i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
//对一个节点进行广度优先遍历
public void bfs(boolean[] isVisited, int i) {
int u;//表示队列的头节点
int w;//临接节点
//队列
LinkedList queue = new LinkedList();
//访问节点
System.out.println(getValueByIndex(i));
//标记为已访问
isVisited[i] = true;
queue.addLast(i);
while (!queue.isEmpty()) {
u = (Integer)queue.removeFirst();
w = getFirstNeighbor(u);
while (w != -1) {
if (!isVisited[w]) {
System.out.println(getValueByIndex(w));
isVisited[w] = true;
queue.addLast(w);
}
w = getNextNeighbor(u,w);
}
}
}
public void bfs() {
//遍历所有节点
for (int i=0;i<vertexList.size();i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}
}
public void insert(String vertex) {
vertexList.add(vertex);
}
//添加边
public void insertEdges(int v1,int v2,int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges ++;
}
public int getNumOfvertex() {
return vertexList.size();
}
public int getNumOfEdges() {
return numOfEdges;
}
//返回节点对应得数据
public String getValueByIndex(int i) {
return vertexList.get(i);
}
public int getWeight(int v1,int v2) {
return edges[v1][v2];
}
//显示图对应得矩阵
public void showGraph() {
for (int[] link: edges) {
System.out.println(Arrays.toString(link));
}
}
}

Tags：

很赞哦！ ()

上一篇：图的创建(图文)

下一篇：非递归二分查找算法(图文)