图
一、图的概述
1、图的概念
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。（结点也可以称为顶点）
2、图的基本概念
- 顶点（vertex）
- 边（edge）
- 路径
- 无向图：顶点之间的连接没有方向
- 有向图：顶点之间的连接有方向
- 带权图（网）：边带权值的图
3、图的实现方式
图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）
1）邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵（二维数组），对于n个顶点的图而言，矩阵是的row 和col 表示的是 1..n个点。
2）邻接表
邻接矩阵需要为每个顶点都分配n 个边的空间，其实有很多边都是不存在,会造成空间的一定损失。
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。
二、深度优先搜索（dfs）
深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策路就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。
每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
深度优先搜索是一个递归的过程
三、广度优先搜索（bfs）
图的广度优先搜索(Broad First Search)，类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
c++
void bfs(起始点) {
将起始点放入队列中;
标记起点访问;
while(如果队列不为空){
访问队首元素x;
删除队首元素;
for(x的相邻点) {
if(没被标记) {
加入队尾并标记;
}
}
}
队列为空，广搜结束;
}四、图的代码实现
java
package work.rexhao.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 图的基础及dfs、bfs遍历
*
* @author 王铭颢
* @Date 2022/7/11 22:26
*/
public class Graph {
int[][] edges; // 邻接矩阵
int n; // 节点个数
List<String> vertex;// 顶点名称
boolean[] flag; // 记录是否被访问过
public static void main(String[] args) {
Graph graph = new Graph(5);
String[] strs = {"a", "b", "c", "d", "e"};
graph.addVertex(strs);
graph.addEdges(0, 1, 1); // a -- b
graph.addEdges(0, 2, 1); // a -- c
graph.addEdges(2, 3, 1); // c -- d
graph.addEdges(0, 4, 1); // a -- e
graph.showGraph();
System.out.println("-----------");
graph.dfs();
graph.bfs();
}
/**
* 广度优先遍历
*/
private void bfs() {
flag = new boolean[n];
System.out.print("bfs:");
ArrayQueue queue = new ArrayQueue(n);
queue.addQueue(0);
while (!queue.isEmpty()) {
// 出队列
int i = queue.getQueue();
System.out.print(getValueByIndex(i));
// 标记
flag[i] = true;
// 把该节点连接的节点加入队列
for (int j = 0; j < n; j++) {
if (!flag[j] && edges[i][j] != 0) {
queue.addQueue(j);
}
}
}
System.out.println();
}
/**
* 深度优先遍历
*/
public void dfs() {
flag = new boolean[n];
System.out.print("dfs:");
for (int i = 0; i < n; i++) {
dfs(i);
}
System.out.println();
}
public void dfs(int i) {
// 标记过 -> return
if (flag[i]) {
return;
}
// 没被标记 -> 输出该节点 -> 标记
System.out.print(getValueByIndex(i));
flag[i] = true;
// 找到该节点的后续节点
for (int j = 0; j < n; j++) {
if (edges[i][j] != 0) {
dfs(j);
}
}
}
/**
* 构造器
*
* @param n 节点个数
*/
Graph(int n) {
this.n = n;
edges = new int[n][n];
vertex = new ArrayList<>(n);
}
/**
* 添加节点名称
*
* @param strs 节点名称数组
*/
public void addVertex(String[] strs) {
vertex.addAll(Arrays.asList(strs));
}
/**
* 添加边
*
* @param v1 节点1
* @param v2 节点2
* @param weight 权重
*/
public void addEdges(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
}
/**
* 打印邻接矩阵
*/
public void showGraph() {
for (int[] edge : edges) {
for (int i : edge) {
System.out.print(i + " ");
}
System.out.println();
}
}
/**
* 根据下标获取节点数据
*
* @param i 节点下标
* @return 节点数据
*/
public String getValueByIndex(int i) {
return vertex.get(i);
}
}
class ArrayQueue {
private int maxSize; // 数组最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 队列的数据
/**
* 创建队列的构造器
*/
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[arrMaxSize];
front = -1;// 指向队列头的前一个位置
rear = -1;// 指向队列尾
}
/**
* 判断队列是否满
*/
public boolean isFull() {
return rear == maxSize - 1;
}
/**
* 判断队列是否为空
*/
public boolean isEmpty() {
return rear == front;
}
/**
* 添加队列数据
*/
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列满，添加失败！");
return;
}
arr[++rear] = n;
}
/**
* 出队列
*/
public int getQueue() {
if (isEmpty()) {
// 抛出异常 -- 不需要写return
throw new RuntimeException("队列空");
}
return arr[++front];
}
/**
* 遍历
*/
public void showQueue() {
if (isEmpty()) {
System.out.println("队列空！");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d] = %d\n", i, arr[i]);
}
}
/**
* 显示头数据（不取出）
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空");
}
return arr[front + 1];
}
}