撰写图是一种广泛用于表示网络关系的数据结构。它由顶点（节点）和边组成，其中边连接两个顶点。图在许多应用中都非常有用，比如社交网络、地图导航、电路设计等。
图的基本概念
-
顶点 (Vertex) :
- 一个图中的基本元素，也称为节点。
- 示例：在社交网络中，每个用户可以表示为一个顶点。
-
边 (Edge) :
- 连接两个顶点的线段。
- 可以有方向（有向图）或无方向（无向图）。
- 边还可以带有权重，表示某种关系的强度。
-
路径 (Path) :
- 从一个顶点到另一个顶点的一系列边。
- 简单路径：不包含重复顶点。
- 循环：起始顶点和结束顶点相同。
-
连通性 (Connectivity) :
- 图中的顶点是否可以通过一系列边相互到达。
- 强连通图（有向图）：每个顶点都有一条路径到达其他所有顶点。
- 连通分量（无向图）：无法通过额外的边将更多的顶点连接在一起的最大子图。
-
度 (Degree) :
- 无向图中，一个顶点连接的边的数量。
-
有向图中，分为入度和出度：
- 入度：指向该顶点的边的数量。
- 出度：从该顶点出发的边的数量。
图的类型
-
无向图 (Undirected Graph) :
- 边没有方向，是双向的。
- 示例：社交网络中的朋友关系。
-
有向图 (Directed Graph) :
- 边有方向，是单向的。
- 示例：网页之间的链接关系。
-
加权图 (Weighted Graph) :
- 边带有权重，表示某种距离或成本。
- 示例：地图上的道路距离。
-
稀疏图 (Sparse Graph) :
- 边的数量远少于顶点数量的平方。
- 常用邻接表来存储。
-
稠密图 (Dense Graph) :
- 边的数量接近顶点数量的平方。
- 常用邻接矩阵来存储。
图的表示方法
-
邻接矩阵 (Adjacency Matrix) :
- 使用二维数组表示，大小为 VxV（其中 V 是顶点数）。
- 如果顶点 i 和 j 之间有边，则 matrix[i][j] = 1 或权重值；否则为 0 或无穷大。
- 特点：实现简单，空间复杂度 O(V^2)，但不适合稀疏图。
-
邻接表 (Adjacency List) :
- 使用链表或数组列表表示每个顶点的邻居。
- 每个顶点有一个列表，存储所有直接相连的顶点及其权重（如果有）。
- 特点：适合稀疏图，空间复杂度为 O(E + V)，其中 E 是边的数量。
图的基本操作
-
添加顶点 (Add Vertex) :
- 在邻接表中创建一个新的节点，并将其加入顶点列表。
-
添加边 (Add Edge) :
- 在无向图中，将两个顶点的邻居列表相互添加。
- 在有向图中，只在起始顶点的邻居列表中添加目标顶点。
-
删除顶点 (Remove Vertex) :
- 从邻接表中移除该顶点，并更新所有相邻顶点的邻居列表。
-
删除边 (Remove Edge) :
- 在无向图中，从两个顶点的邻居列表中移除彼此。
- 在有向图中，只在起始顶点的邻居列表中移除目标顶点。
图的遍历
-
深度优先搜索 (DFS, Depth-First Search) :
- 使用栈或递归来遍历图。
- 从一个起始顶点开始，访问该顶点的所有相邻未访问顶点，直到无法再深入，然后回溯到上一个顶点继续。
-
广度优先搜索 (BFS, Breadth-First Search) :
- 使用队列来遍历图。
- 从一个起始顶点开始，逐层访问所有相邻顶点，直到所有顶点都被访问过。
图的应用
-
社交网络分析：
- 查找朋友关系、推荐系统等。
-
地图导航：
- 寻找最短路径（如 Dijkstra 算法、A* 算法）。
-
电路设计：
- 优化电路布局。
-
任务调度：
- 拓扑排序，确定任务执行顺序。
示例代码
以下是一个使用邻接表表示图的简单实现，并包含基本的添加顶点和边的操作：
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, vertex):
if vertex not in self.adj_list:
self.adj_list[vertex] = []
def add_edge(self, vertex1, vertex2):
if vertex1 in self.adj_list and vertex2 in self.adj_list:
self.adj_list[vertex1].append(vertex2)
self.adj_list[vertex2].append(vertex1)
def print_graph(self):
for vertex in self.adj_list:
print(f"{vertex} -> {self.adj_list[vertex]}")
# 创建图并添加顶点和边
graph = Graph()
vertices = ['A', 'B', 'C', 'D']
for v in vertices:
graph.add_vertex(v)
edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')]
for e in edges:
graph.add_edge(*e)
graph.print_graph()