图
背景
线性表和树都只能有一个前驱节点,也就是父节点,当需要表示多对多关系的时候就需要使用图。图是一种数据结构,其中:节点可以具有 0 个或多个相邻元素,两个节点之间的连接称为边(Edge),节点也被称为顶点(Vertices)。
无向图
顶点之间的连接没有方向,例如:
有向图
顶点之间有方向,只能从一点到另一点,但不能直接返回
带权图
路径有权值(个人看起来像EIGRP),也叫网
图的表示方式
二维数组(邻接矩阵)
邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵的行和列表示1到n个点。
例如:左侧列中4(代表图中的 4)所在的行,和上方行中的2(代表图中的2)所在的列的交点值(4,2)是1,表示可以直接连接。
链表表示(邻接表)
由于邻接矩阵有一个缺点:它需要为每个顶点都分配 n 个边的空间,其实有很多边都是不存在的(比如上面的 0,0 不链接,也需要表示出来),这 会造成空间的一定损失。
邻接表只关心存在的边,因此没有空间浪费,由 数组 + 链表组成。
例如:标号为 0 的链表表示图中的 0 和哪些顶点直接相连。
图的创建
分析
- 保存顶点 ArrayList
- 保存矩阵 int[][] deges
代码
import java.util.ArrayList;
import java.util.Arrays;
public class GraphExample {
public static void main(String[] args) {
Graph graph = new Graph(5);
String vertexValue[]={"A","B","C","D","E"};
for (String VertexValue:vertexValue) {
graph.addVertex(VertexValue);
}
//A-B A-C B-C B-D B-E
graph.addEdge(0,1,1);
graph.addEdge(0,2,1);
graph.addEdge(1,2,1);
graph.addEdge(1,3,1);
graph.addEdge(1,4,1);
graph.showGraph();
}
}
class Graph {
private ArrayList<String> vertexList;
private int[][] edge;
private int numOfEdges; //number of edges
public Graph(int numOfVertex) {
edge = new int[numOfVertex][numOfVertex];
vertexList = new ArrayList<>(numOfVertex);
numOfEdges = 0;
}
public void addVertex(String vertex) {
vertexList.add(vertex);
}
/**
* add edge
*
* @param vertex1 first vertex
* @param vertex2 second vertex
* @param weight weight of edge
*/
public void addEdge(int vertex1, int vertex2, int weight) {
edge[vertex1][vertex2] = weight;
edge[vertex2][vertex1] = weight;
numOfEdges++;
}
public int getNumOfVertex() {
return vertexList.size();
}
public int getNumOfEdges() {
return numOfEdges;
}
public String getValueByIndex(int i) {
return vertexList.get(i);
}
public int getWeight(int vertex1, int vertex2) {
return edge[vertex1][vertex2];
}
public void showGraph() {
for (int[] link : edge) {
System.out.println(Arrays.toString(link));
}
}
}
深度优先遍历 Depth First Search, DFS
从初始访问节点出发,初始访问节点可能有多个邻接节点(直连)
深度优先遍历的策略为:初始节点出发,访问第一个邻节点,再将访问到的邻节点视为初始节点,访问它的第一个邻节点,以此类推。
算法步骤:
- 访问初始节点 v ,并标记已访问
- 查找节点的第一个邻节点 w
- 若 w 存在,执行步骤 4 ,若不存在返回第一步,从 v 的下一个节点继续
- 若 w 未被访问,对 w 进行深度优先遍历递归(把 w 看成 v,继续执行1、2、3)
- 若 w 被访问过,查找节点 w 的下一个邻节点,转到步骤 3
在本例中,以 A 为初始节点,在 vertexList 中,顶点的储存方式为 { A, B, C, D, E }
- 从 A 出发,标记成已访问
- 它的第一个节点是 B,存在且未被访问,访问 B 的第一个邻节点 C
- C存在,访问 C ,标记为已访问,C 的下一个节点的 D,但无法到达(不存在),回溯至上一步
- B 的第一个节点是 C,被访问,查找下一个邻节点 D
- D存在,访问 D ,标记为已访问,D 的下一个节点的 E,但无法到达(不存在),回溯至上一步
- B 的第一个、第二个邻节点都被访问,访问第三个邻节点 E
- E 存在,访问 E ,标记为已访问(回溯/打断)
广度优先遍历 Broad First Search, BFS
类似于分层搜索,广度优先遍历需要使用一个队列来保存访问过的节点的顺序。按此顺序来访问这些节点的邻接节点
算法步骤:
- 访问初始节点 v ,并标记已访问
- 将 v 加入队列
- 当 v 为非空时,继续执行,否则算法结束
- 出队列,取得头节点 u
- 查找 u 的第一个邻节点 w
- 若 w 不存在,转到步骤 3,否则:
6.1. 若 w 未访问,标记为已访问
6.2. 节点 w 入队
6.3. 查找节点 u 的继 w 零界点后的下一个邻节点 w,转到步骤 6