图也是一种数据结构,用来表示多对多的关系,两个节点(顶点)之间的连接称之为边
从一个顶点到另一个顶点的所经过的边连起来称之为路径
图的两种表现方式:二维数组(邻接矩阵),链表(邻接表)
图的深度优先遍历(DFS):
访问初始顶点找到最近的一个顶点,再以这个顶点为初始顶点继续找最近的顶点,以递归的方式把所有的顶点遍历完
图的广度优先遍历(BFS):
访问并标记初始节点已访问,将初始节点入队列
队列非空继续执行,否则结束
出队列,取队头节点u,查找u的第一个邻接节点w
若节点u的邻接节点w不存在,则转到非空判断上,否则继续循环执行下面的步骤
节点w未被访问,则访问后标记已访问,入队列,查找节点u的继w邻接节点后的下一个邻接节点w,转上一个步骤
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; 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 vertex : vertexs) { graph.insertVertex(vertex); } 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(); graph.bfs(); } public Graph(int n) { edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; isVisited = new boolean[5]; } 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; } //深度优先遍历 private void dfs(boolean[] isVisited, int i) { System.out.print(getValueByIndex(i) + " -> "); isVisited[i] = true; int w = getFirstNeighbor(i); while (w != -1) { if (!isVisited[w]) { dfs(isVisited, w); } w = getNextNeighbor(i, w); } } //对dfs进行重载 遍历所有节点(回溯) public void dfs() { for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { dfs(isVisited, i); } } } //对一个节点广度优先遍历方法 private void bfs(boolean[] isVisited, int i) { int u;//队列头结点的下标 int w;//临接节点的下标 //队列 节点访问顺序 LinkedList queue = new LinkedList(); System.out.print(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.print(getValueByIndex(w) + " -> "); isVisited[w] = true; queue.addLast(w); } w = getNextNeighbor(u, w); } } } public void bfs(){ for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisited[i]) { bfs(isVisited, i); } } } public int getNumOfVertex() { return vertexList.size(); } public void showGraph() { for (int[] link : edges) { System.out.println(Arrays.toString(link)); } } 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 insertVertex(String vertex) { vertexList.add(vertex); } public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }