数据结构--图的基本操作

**图的基本操作**

图是一种非线性数据结构，用于表示复杂的关系网络。它由顶点（也称为结点或元胞）和边组成，每个顶点都有一个唯一标识符。图的基本操作包括创建图、插入顶点和边、删除顶点和边、遍历图等。

**1. 创建图**

创建图可以使用以下方法：

* 使用字典（或哈希表）来存储顶点和边的信息。
* 使用列表或数组来存储顶点和边的信息，并使用索引来访问它们。

下面是一个使用字典创建图的示例代码：

class Graph:
 def __init__(self):
 self.vertices = {}
 self.edges = {}

 def add_vertex(self, vertex_id):
 """添加一个顶点"""
 if vertex_id not in self.vertices:
 self.vertices[vertex_id] = set()

 def add_edge(self, vertex1, vertex2):
 """添加一条边"""
 if vertex1 not in self.vertices or vertex2 not in self.vertices:
 raise ValueError("Both vertices must exist")
 self.edges[(vertex1, vertex2)] = True self.vertices[vertex1].add(vertex2)
 self.vertices[vertex2].add(vertex1)

 def remove_vertex(self, vertex_id):
 """删除一个顶点"""
 if vertex_id in self.vertices:
 del self.vertices[vertex_id]
 for edges in self.edges.values():
 if vertex_id in edges:
 edges.remove(vertex_id)

 def remove_edge(self, vertex1, vertex2):
 """删除一条边"""
 if (vertex1, vertex2) in self.edges or (vertex2, vertex1) in self.edges:
 del self.edges[(vertex1, vertex2)]
 self.vertices[vertex1].remove(vertex2)
 self.vertices[vertex2].remove(vertex1)

# 创建一个图graph = Graph()
graph.add_vertex(0)
graph.add_vertex(1)
graph.add_edge(0,1)
print(graph.vertices) # {0: {1},1: {0}}

graph = Graph()
graph.add_vertex(0)
graph.add_vertex(1)
graph.add_edge(0,1)
print(graph.vertices) # {0: {1},1: {0}}

graph = Graph()
graph.add_vertex(0)
graph.add_vertex(1)
graph.add_edge(0,1)
print(graph.vertices) # {0: {1},1: {0}}
graph.remove_vertex(0)
print(graph.vertices) # {1: set()}
graph.remove_edge(0,1)
print(graph.vertices) # {1: set()}

class Graph:
 def __init__(self):
 self.vertices = {}
 self.edges = {}

 def dfs(self, start_vertex):
 """深度优先搜索"""
 visited = set()
 stack = [start_vertex]
 while stack:
 vertex = stack.pop()
 if vertex not in visited:
 visited.add(vertex)
 for neighbor in self.vertices[vertex]:
 stack.append(neighbor)

# 创建一个图graph = Graph()
graph.add_vertex(0)
graph.add_vertex(1)
graph.add_edge(0,1)
print(graph.dfs(0)) # [0,1]

class Graph:
 def __init__(self):
 self.vertices = {}
 self.edges = {}

 def degree(self, vertex_id):
 """计算顶点的度数"""
 return len(self.vertices[vertex_id])

 def is_connected(self):
 """检查图是否是连通的"""
 visited = set()
 for vertex in self.vertices:
 if vertex not in visited:
 stack = [vertex]
 while stack:
 v = stack.pop()
 if v not in visited:
 visited.add(v)
 for neighbor in self.vertices[v]:
 stack.append(neighbor)
 return len(visited) == len(self.vertices)

 def shortest_path(self, start_vertex, end_vertex):
 """找到最短路径"""
 queue = [(start_vertex, [start_vertex])]
 while queue:
 (vertex, path) = queue.pop(0)
 if vertex == end_vertex:
 return path for neighbor in self.vertices[vertex]:
 if neighbor not in path:
 queue.append((neighbor, path + [neighbor]))
 return None# 创建一个图graph = Graph()
graph.add_vertex(0)
graph.add_vertex(1)
graph.add_edge(0,1)
print(graph.degree(0)) #1print(graph.is_connected()) # Trueprint(graph.shortest_path(0,1)) # [0,1]