上期填坑
leetcode, 888. 公平的糖果交换.
爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。
两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。
返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。
public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
int sumA = Arrays.stream(aliceSizes).sum();
int sumB = Arrays.stream(bobSizes).sum();
int delta = (sumA - sumB) / 2;
Set<Integer> rec = new HashSet<Integer>();
for (int num : aliceSizes) { //将alice的糖果数量存入hashSet便于快速查找
rec.add(num);
}
int[] ans = new int[2];
for (int y : bobSizes) {// sumA - x + y = sumB - y + x
for (int y : bobSizes) {// sumA - x + y = sumB - y + x
int x = y + delta; // x = (sumA - sumB)/2 + y
if (rec.contains(x)) {// x = delta + y
ans[0] = x;
ans[1] = y;
break;
}
}
return ans;
}
图的概念
也许你听说过六度分隔理论，即你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。
通过六度分隔理论，可以知道我们生活在一个巨大的网络且复杂的网络中，我们只是这个网络中的一个节点。
这就引出了，今天我们要学的新的数据结构——图。
图由顶点和边组成，顶点用有穷非空集合V(G)={v1,v2,...,vn}表示，顶点之间的边用集合E(G)={(u,v)|u∈V,v∈V}表示，图可以表示为：G=(V,E)。其中G表示图，V表示顶点，E表示边。|V|表示顶点的个数，也称图的阶，|E|表示边的条数。这就是一张图的定义，如下图所示：
从上图中可以看出，图相比之前所学的数据结构在逻辑结构上更为复杂：线形-->树形-->图形，如下图，复杂的逻辑结构为更为复杂的场景应用带来解决之道。
图的分类
-
无向图与有向图：顾名思义，根据图中边是否有方向来划分。 -
带权图:权即权重，在实际应用中，一般会给边附加上权重属性，表示两个顶点间关系的程度、大小等。 -
完全图:在无向图中任意两个顶点之间都有一条边相连，在有向图总任意两个顶点之间都有两条相反的边相连。 -
稀疏图与稠密图：相对于图的边的稀疏与稠密而言，没有绝对的界限。一般越接近完全图，越稠密。
图比较.png
图的术语
• 路径：指顶点v到顶点u所经过的顶点序列。
• 路径长度：顶点序列中的顶点个数。
• 环：起点和终点相同的路径，也叫回路。
• 连通图：无向图中，如果图中任意两个节点之间都存在路径，则图是连通的。
• 连通分量：无向图中的极大连通子图称为连通分量。
• 强连通图：有向图，如果图中任意两个节点之间都存在路径，则图是强连通的。
• 强连通分量：有向图中的极大连通子图称为强连通分量。 这里需要注意的是：连通图/强连通图的连通分量/强连通分量，是其本身，且唯一。
• 入度和出度：有向图中节点的入度表示指向该节点的边的数量，出度表示从该节点出发的边的数量。
• 子图:若存在图G1能够在图G中找到，即G1是G的子集，那么G1是G的子图。
图的实现
图的实现通常使用邻接矩阵和邻接表来表示，一般情况下，稠密图多采用邻接矩阵存储，稀疏图多采用邻接表存储。
邻接矩阵：
利用二维矩阵表示图中各顶点之间的关系，对于有n个顶点的图来说，用n阶方阵来表示该图，矩阵中的元素的值为1或者权重值，表示对应的顶点相连，值为0或者无穷，这表示不相连。如图：
邻接矩阵的Java代码示例：
public class Graph {
private int V; // 节点数量
private int[][] adjMatrix; // 邻接矩阵
public Graph(int v) {
V = v;
adjMatrix = new int[V][V];
}
public void addEdge(int i, int j) {
adjMatrix[i][j] = 1;
adjMatrix[j][i] = 1; // 无向图需将对称位置也设为 1
}
// 其他方法：如遍历、查找、删除边等
}
邻接表
邻接表是一种链表数组，数组中的每个元素是一个链表，用于存储与对应节点相连的其他节点。
邻接表的Java代码示例：
public class Graph {
private int V; // 节点数量
private LinkedList<Integer>[] adjList; // 邻接表
public Graph(int v) {
V = v;
adjList = new LinkedList[V];
for (int i = 0; i < V; ++i) {
adjList[i] = new LinkedList<>();
}
}
public void addEdge(int i, int j) {
adjList[i].add(j);
adjList[j].add(i); // 无向图需在两个节点的链表中都添加对方
}
// 其他方法：如遍历、查找、删除边等
}
图的搜索
图的搜索是指在图中查找特定节点或路径的过程。常见的图搜索算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索（DFS）
深度优先搜索是一种通过沿着图的深度方向遍历节点的搜索算法。它从图的某一起始节点开始，沿着一条路径尽可能深地访问节点，直到该路径上的所有节点都被访问过，然后回溯到前一节点继续搜索。
使用递归或栈来实现深度优先搜索。
从起始节点开始，递归地访问其邻居节点，直到没有未访问的邻居节点为止。 代码示例：
// 无向图的表示
class Graph {
private int V; // 顶点数
private LinkedList<Integer> adj[]; // 邻接表
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// 添加边到图中
void addEdge(int v, int w) {
adj[v].add(w);
}
// 从顶点v开始DFS遍历
void DFSUtil(int v, boolean visited[]) {
// 当前顶点标记为已访问
visited[v] = true;
System.out.print(v + " ");
// 遍历邻接节点
Iterator<Integer> it = adj[v].listIterator();
while (it.hasNext()) {
int n = it.next();
// 如果邻接节点未被访问，则递归调用DFSUtil
if (!visited[n])
DFSUtil(n, visited);
}
}
// 以顶点v为起点进行DFS
void DFS(int v) {
// 标记所有顶点为未访问
boolean visited[] = new boolean[V];
// 调用DFSUtil开始遍历
DFSUtil(v, visited);
}
// 对整个图进行DFS
void DFS() {
// 标记所有顶点为未访问
boolean visited[] = new boolean[V];
// 对每个未访问的顶点调用DFSUtil
for (int i=0; i<V; ++i) {
if (!visited[i])
DFSUtil(i, visited);
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("从顶点2开始的DFS：");
g.DFS(2);
System.out.println("\n整个图的DFS：");
g.DFS();
}
}
广度优先搜索（BFS）
广度优先搜索是一种通过按照图的广度方向遍历节点的搜索算法。
它从图的某一起始节点开始，首先访问其所有的邻居节点，然后逐层地向下访问其他邻居节点，直到找到目标节点或所有节点都被访问过。
使用队列来实现广度优先搜索。
从起始节点开始，依次将其邻居节点加入队列，并标记为已访问，然后继续处理队列中的下一个节点。 代码示例：
// 无向图的表示
class Graph {
private int V; // 顶点数
private LinkedList<Integer> adj[]; // 邻接表
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// 添加边到图中
void addEdge(int v, int w) {
adj[v].add(w);
}
// 以顶点v开始BFS
void BFS(int v) {
// 创建一个标记数组来跟踪访问状态
boolean visited[] = new boolean[V];
// 创建一个队列用于BFS
LinkedList<Integer> queue = new LinkedList<>();
// 标记当前顶点为已访问，并将其加入队列
visited[v] = true;
queue.add(v);
// 迭代BFS过程直到队列为空
while (queue.size() != 0) {
// 出队并打印
v = queue.poll();
System.out.print(v + " ");
// 获取所有未访问的邻接节点，并标记它们为已访问，并将其加入队列
Iterator<Integer> it = adj[v].listIterator();
while (it.hasNext()) {
int n = it.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("从顶点2开始的BFS：");
g.BFS(2);
}
}
图的应用
我们生活中各种场景应用都可以抽象成一种图，因此图，这个强大的数据结构，在实际中有着广泛的用途：
1.社交网络：社交网络中的好友关系可以用图来表示，节点表示用户，边表示好友关系。
-
地图导航：地图导航系统中的路网可以表示为图，节点表示交叉路口，边表示道路。 -
网络路由：网络路由中的路由器连接关系可以用图来表示，节点表示路由器，边表示连接。
4.组织结构：组织结构可以用图来表示，节点表示员工或部门，边表示管理或从属关系。 -
棋类游戏：棋类游戏中的棋盘布局可以用图来表示，节点表示棋子的位置，边表示合法移动。
小试牛刀
leetcode, 1791. 找出星型图的中心节点 有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。 给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点
