在图论中，图（Graph）是由一组顶点（Vertex）和一组边（Edge）组成的数学结构。图可以用于表示网络结构、关联关系、流程图等多种实际问题。以下是关于图的定义、种类、特点以及存储示例。
1. 图的定义
图 ( G ) 可以表示为一个有序对 ( G = (V, E) )，其中：
-
( V ) 是顶点集，包含图中的所有顶点。
-
( E ) 是边集，包含图中的所有边。每一条边连接两个顶点。
-
对于无向图，边没有方向，表示两个顶点之间的双向关系。
-
对于有向图，边有方向，表示从一个顶点到另一个顶点的单向关系。
2. 图的种类
根据顶点和边的性质，图可以分为以下几类：
1. 无向图（Undirected Graph）
- 在无向图中，边没有方向，即如果顶点 ( u ) 和顶点 ( v ) 之间有边，那么 ( (u, v) ) 和 ( (v, u) ) 被视为相同。
- 例如，社交网络中的朋友关系通常是无向的。
2. 有向图（Directed Graph or Digraph）
- 在有向图中，边有方向，表示从一个顶点指向另一个顶点。
- 例如，网页之间的链接关系是有向的。
3. 加权图（Weighted Graph）
- 每条边都附带一个权重（或成本），表示边之间的关系强度或传输代价。
- 例如，在城市间的道路网络中，边的权重可以表示两座城市之间的距离。
4. 无权图（Unweighted Graph）
- 边没有任何权重，只有顶点之间的连接关系。
- 例如，社交网络中的朋友关系图。
5. 完全图（Complete Graph）
- 完全图是每对不同的顶点都有一条边连接的图。
- 对于 ( n ) 个顶点的完全图，其边的数量是 ( \frac{n(n-1)}{2} )（无向图）或 ( n(n-1) )（有向图）。
6. 连通图（Connected Graph）
- 无向图中，如果任意两个顶点都有路径相连，则称该图为连通图。
- 有向图中，如果任意两个顶点都有路径相连（考虑有向边的方向），则称该图为强连通图。
7. 树（Tree）
- 树是一种特殊的连通无向图，没有环，并且有 ( n-1 ) 条边，其中 ( n ) 是顶点的数量。
- 树广泛用于表示层次结构。
8. 森林（Forest）
- 森林是一个由多个不连通的树组成的图。
3. 图的特点
图的特点取决于它的种类和结构。常见的图的特点包括：
- 连通性：一个图是连通的意味着图中的每一对顶点都有路径相连。
- 度数：图中每个顶点的度数是与该顶点相连接的边的数量。
- 入度：有向图中，某个顶点的入度是指有多少条边指向该顶点。
- 出度：有向图中，某个顶点的出度是指有多少条边从该顶点指向其他顶点。
- 环：图中的环是指从一个顶点出发，通过若干条边，最终回到该顶点的路径。
- 图的表示方式：图可以使用多种数据结构来表示，如邻接矩阵、邻接表等。
4. 图的存储示例
下面是如何使用 Java 来实现图的存储。常见的存储方法包括邻接矩阵和邻接表。
(1) 邻接矩阵表示
邻接矩阵是一个二维数组，元素 matrix[i][j] 表示顶点 i 和顶点 j 之间是否有边。
import java.util.Arrays;public class Graph {private int[][] adjacencyMatrix;private int vertexCount;public Graph(int vertexCount) {this.vertexCount = vertexCount;this.adjacencyMatrix = new int[vertexCount][vertexCount];}// 添加边（无向图）public void addEdge(int start, int end) {adjacencyMatrix[start][end] = 1;adjacencyMatrix[end][start] = 1; // 无向图}// 打印邻接矩阵public void printAdjacencyMatrix() {for (int i = 0; i < vertexCount; i++) {System.out.println(Arrays.toString(adjacencyMatrix[i]));}}public static void main(String[] args) {Graph graph = new Graph(4); // 4个顶点的图graph.addEdge(0, 1);graph.addEdge(1, 2);graph.addEdge(2, 3);graph.printAdjacencyMatrix();}
}
(2) 邻接表表示
邻接表使用一个数组，每个数组元素是一个链表或列表，表示与该顶点直接相连的所有顶点。
import java.util.ArrayList;
import java.util.List;public class Graph {private List<Integer>[] adjacencyList;private int vertexCount;public Graph(int vertexCount) {this.vertexCount = vertexCount;adjacencyList = new ArrayList[vertexCount];for (int i = 0; i < vertexCount; i++) {adjacencyList[i] = new ArrayList<>();}}// 添加边（无向图）public void addEdge(int start, int end) {adjacencyList[start].add(end);adjacencyList[end].add(start); // 无向图}// 打印邻接表public void printAdjacencyList() {for (int i = 0; i < vertexCount; i++) {System.out.println(i + " -> " + adjacencyList[i]);}}public static void main(String[] args) {Graph graph = new Graph(4); // 4个顶点的图graph.addEdge(0, 1);graph.addEdge(1, 2);graph.addEdge(2, 3);graph.printAdjacencyList();}
}
5. 图的应用
图广泛应用于很多领域，如：
- 网络路由：通过图表示计算机网络，寻找最短路径。
- 社交网络：通过图表示人际关系。
- 电路设计：通过图表示电路的连接。
- 任务调度：通过有向图表示任务之间的依赖关系。