图
- 阅读本文的一些约定：
- 顶点==节点
- 当前节点==该节点
- 何为邻接矩阵：表示顶点之间相邻关系的矩阵
-
何为权值：是路由器通过路径选择算法为网络上的路径产生的一个数字。
-
规范：
| 变量名 | 数学意思 |
|---|---|
| vertex(节点) | 节点代表顶点 |
| edges | 邻接矩阵 |
1.0创建图及其常用方法
-
思路
- 存储顶点用ArrayList集合；存储邻接矩阵用int[] [] edges
- 添加边
- 说明：根据顶点的下标进行添加到邻接矩阵
- 插入顶点（节点）
- 其他图常用方法
- 返回节点的个数
- 返回边的数目
- 返回节点i对应的数据（i为下标，前面已经说过我们只是根据顶点下标添加边）
- 返回两个顶点的权值
核心代码
private ArrayList<String> vertexList;//存储顶点集合 private int[][] edges;//存储图对应的邻接矩阵 private int numOfEdges;//表示边的数目 private boolean[] isVisited;//记录某个节点是否被访问到 public Graph(int n) { //n为节点个数 //初始化矩阵 和 vertexList edges = new int[n][n]; vertexList = new ArrayList<>(n); numOfEdges =0; }//插入节点 public void insertVertex(String vertex){ vertexList.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++;//边加一 }
2.0深度优先遍历
-
规律：递归实现遍历，一个图中一个节点可能有多个邻接节点，当访问第一个节点后，将该节点设为已被访问，然后访问该节点的第一个邻接节点；如果该邻接节点未被访问，则将该邻接节点设未当前节点，并且该邻接节点设为已访问，然后继续以当前节点继续访问当前节点的邻接节点，依此类推，直到所有节点都被访问后，递归回去，结束程序。
-
思路步骤：
- 首先访问初始节点 v，并立刻标记节点v为已访问。
- 接着查找节点v的第一个邻接节点w。
- 如果w存在，则继续执行4，如果w不存在，则回到第一步，从v的下一个节点继续扫描执行以上步骤
- 如果w存在却未被访问，对w进行深度优先遍历递归（也就是把w当作另一个v，然后从头执行以上步骤）。
- 查找节点v的w邻接节点的下一个邻接节点，转到步骤3
核心代码
//重载dfs public void dfs(){ isVisited = new boolean[vertexList.size()]; for (int i = 0;i<getNumOfVertex();i++){ if (!isVisited[i]){ dfs(isVisited,i); } } } /** * 深度优先遍历算法 * * @param isVisited 是否被访问 * @param i 第一次为 0 */ private void dfs(boolean[] isVisited, int i) { //访问==输出 System.out.print(getValueByIndex(i)+"=>"); //设为被访问 isVisited[i] = true; //查找节点i的第一个邻接节点w int w = getFirstNeighbor(i); //如果w未被访问，则将w设为当前节点，继续充当i的角色 //因为获取邻接节点方法有可能返回一个-1，则需要循环语句 while (w!=-1){ if (!isVisited[w]){ dfs(isVisited,w); } //步骤5,根据当前节点v的下标，获取当前节点v的w的邻接节点的下标，并更新旧w，即充当w w = getNextNeighbor(i,w); } }
3.0广度优先遍历
- 思路
- 访问初始节点 v 并标记节点v为已访问
- 节点v入队列
- 当队列为空时，结束；否则继续
- 出队列，取得队头节点 u
- 查找节点u的第一个邻接节点 w
- 若节点u的邻接节点w不存在，则转到第三步；否则循环执行以下步骤：
- 若节点w还未被访问，则访问w并标记已访问
- 节点w入队列
- 查找节点u的继w后的，u的其他邻接节点，转到第六步
- 核心代码
//广度遍历所有节点
public void bfs(){
isVisited = new boolean[vertexList.size()];
for (int i = 0; i < vertexList.size(); i++) {
if (!isVisited[i]){
bfs(isVisited,i);
}
}
}
//一个队头节点：进行广度优先遍历算法
public void bfs(boolean[] isVisited,int i){
int u;//表示队列的头节点对应的下标
int w;//邻接节点
//队列，记录节点访问的顺序?
LinkedList<Integer> queue= new LinkedList<>();
///访问节点
System.out.print(getValueByIndex(i) + "=>");
//标记已访问
isVisited[i] = true;
//将节点加入队列
queue.addLast(i);
while (!queue.isEmpty()){
//取出队列的头节点下标
u = queue.removeFirst();
//得到第一个邻接节点的下标
w = getFirstNeighbor(u);
//
while (w!=-1){
if (!isVisited[w]){
//如果w还未被访问
System.out.print(getValueByIndex(w)+"=>");
//标记已经访问
isVisited[w]=true;
//入队
queue.addLast(w);
}
//以u为前驱节点，找到w后面的下一个邻接点
w = getNextNeighbor(u,w);
}
}
}
区别与总结
深度优先：先根遍历；
广度优先：层次遍历；
总结：
- 图是多对多关系，一个顶点有多个邻接节点，深度遍历和广度遍历都是先访问初始节点后，以该节点继续访问该节点的第一个邻接节点；后面步骤不同：
- 深度遍历是标记了一个节点后，以该节点作为中心，继续遍历该节点的第一个邻接节点
- 广度遍历是先把第一个作为参照物的节点，把所有与该节点有边关系的节点都先标识