编写一份图的存储和基本操作的课程设计(包括源代码)
时间: 2024-10-01 21:03:09 浏览: 14
在编写一份关于图的存储和基本操作的课程设计时,我们通常会涉及数据结构的选择(如邻接矩阵、邻接表)、图的创建、节点和边的操作以及一些常见的算法,例如深度优先搜索(DFS)和广度优先搜索(BFS)。下面是一个简单的Python示例,展示如何使用邻接列表实现无向图:
```python
# 定义一个Node类,表示图中的节点
class Node:
def __init__(self, value):
self.value = value
self.neighbors = []
# 定义Graph类,用于存储和操作图
class Graph:
def __init__(self):
self.nodes = {}
# 添加节点
def add_node(self, value):
if value not in self.nodes:
new_node = Node(value)
self.nodes[value] = new_node
# 添加边(无向图)
def add_edge(self, from_value, to_value):
if from_value in self.nodes and to_value in self.nodes:
self.nodes[from_value].neighbors.append(to_value)
self.nodes[to_value].neighbors.append(from_value)
# 深度优先搜索
def dfs(self, start_node):
visited = set()
stack = [start_node]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node.value, end=" ")
stack.extend(n for n in self.nodes[node.value] if n not in visited)
# 示例:创建并操作图
g = Graph()
g.add_node(1)
g.add_node(2)
g.add_node(3)
g.add_edge(1, 2)
g.add_edge(2, 3)
# 进行深度优先搜索,从节点1开始
g.dfs(1)
```
阅读全文