图
- 阅读本文的一些约定：
- 顶点==节点
- 当前节点==该节点
- 何为邻接矩阵：表示顶点之间相邻关系的矩阵
-
何为权值：是路由器通过路径选择算法为网络上的路径产生的一个数字。
-
规范：
| 变量名 | 数学意思 |
|---|---|
| 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);
}
}
}
区别与总结
深度优先：先根遍历；
广度优先：层次遍历；
总结：
- 图是多对多关系，一个顶点有多个邻接节点，深度遍历和广度遍历都是先访问初始节点后，以该节点继续访问该节点的第一个邻接节点；后面步骤不同：
- 深度遍历是标记了一个节点后，以该节点作为中心，继续遍历该节点的第一个邻接节点
- 广度遍历是先把第一个作为参照物的节点，把所有与该节点有边关系的节点都先标识
- 完整代码
package com.guodaxia.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
/**
* 图的学习
* @ author Guo daXia
* @ create 2022/12/1
*/
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges;//存储图对应的邻接矩阵
private int numOfEdges;//表示边的数目
private boolean[] isVisited ;//记录某个节点是否被访问到
public static void main(String[] args) {
//测试图是否创建成功
int n = 8;//节点的个数
String[] vertexs = {"1", "2", "3", "4", "5", "6", "7", "8"};//顶点数
Graph graph = new Graph(n);//创建图对象
//循环着添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//添加边 A-B A-C B-C B-D B-E
graph.insertEdge(0, 1, 1);//代表添加边 A-B
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
//显示邻接矩阵
graph.showGraph();
//测试深度优先遍历dfs是否ok
System.out.println("深度优先遍历~");
//graph.dfs();
System.out.println();
//测试广度优先遍历dfs是否ok
System.out.println("广度优先");
graph.bfs();
}
public Graph(int n) { //n为节点个数
//初始化矩阵 和 veqrtexList
edges = new int[n][n];
vertexList = new ArrayList<>(n);
numOfEdges = 0;
}
//广度遍历所有节点
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);
}
}
}
//重载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);
}
}
//根据前一个邻接节点的下标，来获取下一个邻接节点的下标
private int getNextNeighbor(int v1, int v2) {
//从哪开始？
//w的下一个邻接节点
for (int j =v2 +1;j<vertexList.size();j++){
if (edges[v1][j]>0){//如果两顶点有权值，说明有边
return j;
}
}
return -1;
}
private int getFirstNeighbor(int i) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[i][j] > 0) {
return j;
}
}
return -1;
}
//以下方法为图常用的
/**
* @return 返回节点的个数
*/
public int getNumOfVertex() {
return vertexList.size();//集合类方法
}
//显示图对应的矩阵
public void showGraph() {
//遍历，邻接矩阵
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
//获得边的数目
public int getNumOfEdges() {
return numOfEdges;
}
//返回节点 i（下标）对应的数据，如：0->"A" 1->"B" 2-"C"
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回 v1 和 v2 的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
//插入节点
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++;//边加一
}
}