数据结构第一弹-图
大家好，今天和大家一起学习一下数据结构中的图~
图（Graph）是一种非线性的数据结构，它由节点（也称为顶点，Vertices）和边（Edges）组成。图可以用来表示各种关系网络，如社交网络、交通网络、计算机网络等。图的灵活性使得它在许多领域中都有广泛的应用，包括但不限于算法设计、数据库系统、编译器优化以及机器学习。
1. 图的基本概念
1.1 节点与边
- 节点（Vertex/Node）: 图中的基本单位，代表一个实体。
- 边（Edge）: 连接两个节点的连线，表示这两个节点之间的某种关系。
1.2 图的类型
- 无向图（Undirected Graph）: 边没有方向性，如果存在一条从A到B的边，则也存在一条从B到A的边。
- 有向图（Directed Graph）: 边具有方向性，一条从A到B的边并不意味着存在一条从B到A的边。
- 加权图（Weighted Graph）: 每条边都关联有一个权重值，用于表示边上的成本或距离。
- 连通图（Connected Graph）: 在无向图中，任意两个顶点之间都存在路径；在有向图中，至少存在一个顶点能够到达其他所有顶点。
- 完全图（Complete Graph）: 每对不同的顶点之间都恰好有一条边相连。
1.3 常见术语
- 度（Degree）: 一个节点连接的边的数量。
- 入度（In-degree）: 在有向图中，指向该节点的边数。
- 出度（Out-degree）: 在有向图中，从该节点出发的边数。
- 路径（Path）: 一系列相邻节点组成的序列。
- 环（Cycle）: 一条起始节点和结束节点相同的路径。
- 最短路径（Shortest Path）: 两节点间所有可能路径中最短的一条。
2. 图的存储方式
图可以通过多种方式存储，其中最常见的两种是邻接矩阵和邻接表。
2.1 邻接矩阵
邻接矩阵是一个二维数组，用于表示图中各节点间的连接情况。如果A[i][j]为1，则表示节点i和节点j之间存在一条边；如果是0，则表示不存在边。对于加权图，可以用具体权重代替1。
public class AdjacencyMatrix {
private final int V; // 顶点数量
private int[][] adjMatrix; // 邻接矩阵
public AdjacencyMatrix(int v) {
V = v;
adjMatrix = new int[V][V];
}
public void addEdge(int u, int v, int weight) {
adjMatrix[u][v] = weight;
if (u != v) { // 对于无向图
adjMatrix[v][u] = weight;
}
}
public void printMatrix() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
System.out.print(adjMatrix[i][j] + " ");
}
System.out.println();
}
}
}2.2 邻接表
邻接表使用链表或数组来存储每个节点的所有邻居节点。这种方式在稀疏图中更加高效。
import java.util.ArrayList;
import java.util.List;
public class AdjacencyList {
private final int V; // 顶点数量
private List<List<Integer>> adjList; // 邻接表
public AdjacencyList(int v) {
V = v;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; ++i) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int u, int v) {
adjList.get(u).add(v);
if (u != v) { // 对于无向图
adjList.get(v).add(u);
}
}
public void printList() {
for (int i = 0; i < V; i++) {
System.out.print("Adjacency list of vertex " + i + ":");
for (int j : adjList.get(i)) {
System.out.print(" -> " + j);
}
System.out.println();
}
}
}3. 图的遍历算法
图的遍历是指访问图中所有顶点的过程。常用的遍历方法有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。
3.1 深度优先搜索（DFS）
DFS从一个给定的起点开始，尽可能深地探索每个分支，直到无法继续为止，然后回溯并尝试另一条路径。
import java.util.*;
public class DFS {
private boolean[] visited;
public DFS(int vertices) {
visited = new boolean[vertices];
}
public void dfs(AdjacencyList graph, int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int s = stack.pop();
if (!visited[s]) {
System.out.print(s + " ");
visited[s] = true;
}
for (int n : graph.adjList.get(s)) {
if (!visited[n]) {
stack.push(n);
}
}
}
}
}3.2 广度优先搜索（BFS）
BFS则从一个给定的起点开始，逐层向外扩展，先访问离起点最近的所有节点，然后再访问更远一层的节点。
import java.util.*;
public class BFS {
private boolean[] visited;
public BFS(int vertices) {
visited = new boolean[vertices];
}
public void bfs(AdjacencyList graph, int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int s = queue.poll();
System.out.print(s + " ");
for (int n : graph.adjList.get(s)) {
if (!visited[n]) {
queue.add(n);
visited[n] = true;
}
}
}
}
}4. 图的应用实例
4.1 社交网络分析
社交网络可以看作是有向图，用户作为节点，好友关系作为边。通过图论算法，我们可以计算用户的影响力、社区检测等。
4.2 路径规划
在地图应用中，城市作为节点，道路作为边。利用Dijkstra算法或A*算法，可以找到两点之间的最短路径。
import java.util.*;
public class Dijkstra {
private static final int INF = Integer.MAX_VALUE;
public static int[] dijkstra(AdjacencyList graph, int start) {
int n = graph.V;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0];
if (dist[u] < current[1]) continue;
for (int v : graph.adjList.get(u)) {
if (dist[u] + 1 < dist[v]) { // 假设所有边的权重都是1
dist[v] = dist[u] + 1;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
}4.3 数据库索引
在数据库中，图可以用来表示表之间的关系。例如，在关系型数据库中，外键约束可以形成一张图，帮助优化查询性能。
4.4 编译器优化
编译器在进行代码优化时，可以将程序转换成控制流图（CFG），通过对图的操作来识别冗余代码、循环不变量等，从而提高程序效率。
图作为一种强大的数据结构，提供了丰富的表达能力和灵活的处理机制。无论是简单的关系表示还是复杂的网络分析，图都能提供有效的解决方案，欢迎大家一起在评论区讨论~
原文地址：https://blog.csdn.net/fengxiaotao_cool/article/details/144300839
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！