public class GraphDemo {
public static void main(String[] args) {
String[] s = {"A","B","C","D","E","F","G"};
Graph graph = new Graph(s);
//A-B A-C A-G A-F F-D F-E D-E E-G
graph.connect(0, 1);
graph.connect(0, 2);
graph.connect(0, 6);
graph.connect(0, 5);
graph.connect(5, 3);
graph.connect(5, 4);
graph.connect(3, 4);
graph.connect(4, 6);
graph.showGraphMatrix();
graph.dsf();//A -> B -> C -> F -> D -> E -> G ->
System.out.println();
graph.bfs();//A -> B -> C -> F -> G -> D -> E ->
}
}
//图形结构
class Graph {
//存储图中所有顶点
private List<String> vertexes;
//图形结构的邻接矩阵
private int[][] matrix;
//各顶点访问情况，true为已访问，false为未访问
private boolean[] visited;
/**
* 根据传入的顶点信息生成矩阵
* @param s
*/
public Graph(String s[]) {
vertexes = new ArrayList<>();
for (String vertex : s){
vertexes.add(vertex);
}
matrix = new int[s.length][s.length];
}
/**
* 将俩个顶点连接，即生成边
* @param index1 顶点在集合中的索引
* @param index2
*/
public void connect(int index1, int index2){
if (index1 < 0 || index1 > matrix.length || index2 < 0 || index2 > matrix.length){
throw new RuntimeException("该顶点未存在");
}
//将新的邻接添加的邻接矩阵中
matrix[index1][index2] = 1;
matrix[index2][index1] = 1;
}
/**
* 展示邻接矩阵
*/
public void showGraphMatrix(){
for (int arr[] : matrix){
System.out.println(Arrays.toString(arr));
}
}
public void dsf(){
visited = new boolean[vertexes.size()];
//以在集合中下标为0的顶点，进行深度优先搜索
dsf(visited, 0);
}
/**
* 深度优先搜索
* @param visited
* @param row
*/
public void dsf(boolean[] visited, int row){
//输出当前顶点
System.out.print(vertexes.get(row) + " -> ");
//将当前顶点设为已访问
visited[row] = true;
//获取当前顶点的邻接顶点下标
int index = getFirstNeighbor(row);
//如果当前顶点有邻接顶点则进行深度搜索
while (index != -1){
//当邻接顶点未访问时，则递归遍历
if (visited[index] != true){
dsf(visited, index);
}
//当邻接顶点已访问时，则寻找另一个邻接顶点
index = getNeighbor(row, index);
}
}
public void bfs(){
visited = new boolean[vertexes.size()];
以在集合中下标为0的顶点，进行广度优先搜索
bfs(visited, 0);
}
/**
* 广度优先搜索
* @param visited
* @param row
*/
public void bfs(boolean[] visited, int row){
//创建队列，存储遍历邻接顶点的顺序
Queue queue = new ArrayDeque();
//输出当前顶点
System.out.print(vertexes.get(row) + " -> ");
//将当前顶点设为已访问
visited[row] = true;
//将当前顶点加入队列中
queue.add(row);
//当队列不为空时，即有未搜索的邻接顶点，进行搜索
while (!queue.isEmpty()){
//按顺序从队列中弹出邻接顶点下标
int last = (Integer)queue.poll();
//获取该弹出顶点的邻接顶点下标
int index = getFirstNeighbor(last);
//当弹出顶点有邻接顶点时，进行广度搜索
while(index != -1){
//当邻接顶点未访问时
if(visited[index] != true){
//输出该邻接顶点
System.out.print(vertexes.get(index) + " -> ");
//把该邻接顶点设为已访问
visited[index] = true;
//将该邻接顶点加入队列
queue.add(index);
}
//继续寻找弹出顶点的另一个邻接顶点
index = getNeighbor(last, index);
}
}
}
/**
* 获取顶点在邻接矩阵对应行row中的第一个邻接顶点下标
* @param row
* @return 当有邻接顶点时返回邻接顶点下标，没有则返回-1
*/
public int getFirstNeighbor(int row){
for(int i =0; i<matrix.length; i++){
if (matrix[row][i] != 0){
return i;
}
}
return -1;
}
/**
* 获取顶点在邻接矩阵对于行row中col列的下一个邻接顶点
* @param row
* @param col
* @return 当有邻接顶点时返回邻接顶点下标，没有则返回-1
*/
public int getNeighbor(int row, int col){
for (int i=col+1; i<matrix.length; i++){
if (matrix[row][i] != 0){
return i;
}
}
return -1;
}
}
