java实现图的创建、广度和深度优先遍历、输出邻接矩阵等操作

柔光的暖阳◎ 2023-03-14 10:43 16阅读 0赞

## 说明 ##

*  本程序中树是通过**邻接矩阵**实现的

## 源代码 ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    // 图的创建
    public class Graph { 
    	// 存储图的顶点 
    	private ArrayList<String> vertexList;
    	// 存储图的邻接矩阵
    	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(String v : vertexs) { 
    			graph.insertVertex(v);
    		}
    		// 添加边
    		graph.insertEdge("A", "B");
    		graph.insertEdge("A", "C");
    		graph.insertEdge("C", "B");
    		graph.insertEdge("B", "D");
    		graph.insertEdge("B", "E");
    		
    		// 输出图的邻接矩阵
    		graph.showGraph();
    		
    		System.out.println("深度优先遍历：");
    		// 深度优先遍历 
    		graph.dfs();
    		System.out.println("\n广度优先遍历 ：");
    		graph.bfs();
    	}
    	
    	// 构造函数：传入顶点个数 
    	public Graph(int n) { 
    		edges = new int[n][n];
    		vertexList = new ArrayList<String>(n);
    	}
    	
    	// 插入顶点 
    	public void insertVertex(String vertex) { 
    		vertexList.add(vertex);
    	}
    	
    	// 插入边
    	public void insertEdge(String v1,String v2) { 
    		int i = vertexList.indexOf(v1);
    		int j = vertexList.indexOf(v2);
    		
    		edges[i][j] = 1;
    		edges[j][i] = 1;
    		numOfEdges++;
    	}
    	
    	// 返回顶点数
    	public int getNumOfVertex() { 
    		return vertexList.size();
    	}
    	
    	// 返回边数
    	public int getNumOfEdges() { 
    		return numOfEdges;
    	}
    	
    	// 返回两点之间是否有边
    	public boolean isEdge(String v1, String v2) { 
    		int i = vertexList.indexOf(v1);
    		int j = vertexList.indexOf(v2);
    		
    		if(edges[i][j] == 1) { 
    			return true;
    		}else { 
    			return false;
    		}
    	}
    	
    	// 返回该节点第一个邻接节点的下标
    	private int getFirstNeighbor(int index) { 
    		for(int j = 0; j < vertexList.size(); j++) { 
    			if(edges[index][j] == 1) { 
    				return j;
    			}
    		}
    		return -1;
    	}
    	
    	// 返回该节点的下一个邻接节点
    	private int getNextNeighbor(int v1, int v2) { 
    		for(int j = v2+1; j < vertexList.size(); j++) { 
    			if(edges[v1][j] == 1) { 
    				return j;
    			}
    		}
    		return -1;
    	}
    	
    	// 深度优先遍历,从第i个节点开始
    	private void dfs(int i) { 
    		System.out.print(vertexList.get(i)+"->");
    		// 将节点设置为已访问
    		isVisited[i] = true;
    		
    		// 查找该节点的第一个邻接节点的下标
    		int w = getFirstNeighbor(i);
    		// 如果存在
    		while(w != -1) { 
    			// 如果此邻接节点没有被访问过，继续向下遍历 
    			if(!isVisited[w]) { 
    				dfs(w);
    			}
    			// 如果此邻接节点被访问过了，查找下一个邻接节点
    			w = getNextNeighbor(i, w);
    		}
    	}
    	
    	// dfs重载，依次对每一个节点进行深度优先遍历 
    	public void dfs() { 
    		isVisited = new boolean[getNumOfVertex()];
    		
    		for(int i = 0; i < getNumOfVertex(); i++) { 
    			if(!isVisited[i]) { 
    				dfs(i);
    			}
    		}
    	}
    	
    	// 广度优先遍历
    	private void bfs(int i) { 
    		// 队列头结点的下标
    		int u;
    		// 邻接结点
    		int w;
    		// 使用一个链表充当队列 
    		LinkedList<Integer> queue = new LinkedList<Integer>();
    		// 输出当前结点
    		System.out.print(vertexList.get(i) + "=>");
    		isVisited[i] = true;
    		// 将该结点入队
    		queue.addLast(i);
    		
    		while( !queue.isEmpty() ) { 
    			// 取出队头结点
    			u = queue.removeFirst();
    			// 获取队头结点的第一个邻接结点 
    			w = getFirstNeighbor(u);
    			// 如果能够找到
    			while(w != -1) { 
    				// 如果此结点没有被访问
    				if(!isVisited[w]) { 
    					System.out.print(vertexList.get(w) + "=>");
    					isVisited[w] = true;
    					// 将此结点入队
    					queue.addLast(w);
    				}
    				// 然后查找下一个邻接结点
    				w = getNextNeighbor(u, w);
    			}
    		}
    	}
    	
    	// 重载BFS
    	public void bfs() { 
    		isVisited = new boolean[getNumOfVertex()];
    		
    		for(int i = 0; i < getNumOfVertex(); i++) { 
    			if(!isVisited[i]) { 
    				bfs(i);
    			}
    		}
    	}
    	
    	// 输出图的邻接矩阵
    	public void showGraph() { 
    		for(String v : vertexList) { 
    			System.out.printf("%3s",v);
    		}
    		System.out.println();
    		
    		for(int i = 0; i < vertexList.size(); i++) { 
    			
    			System.out.println(vertexList.get(i) + Arrays.toString(edges[i]));
    		}
    	}
    
    }