数据结构day8（2023.7.25）

**数据结构 Day8**

**2023 年7 月25 日**

### 前言在前面的几天里，我们已经学习了栈、队列、树等基本的数据结构。今天，我们将继续学习另一种重要的数据结构——图。

### 图的定义和特性图是一种非线性的数据结构，它由一组顶点（也称为结点）和一组边组成，每条边连接两个顶点。图可以看作是树的一般化形式，顶点可以有多个父节点，而不是只有一个父节点。

图的特性包括：

* 图中的每个顶点都可以有多个邻居。
* 每条边都连接两个顶点。
* 图中可能存在环（即一条边连接了一个顶点到另一个顶点，且从另一个顶点又回到了第一个顶点）。

### 图的应用图在计算机科学和其他领域有着广泛的应用。例如：

* 网络拓扑：图可以用来表示网络中的设备和连接。
* 路径规划：图可以用来找到从一地到另一地的最短路径。
* 社会网络分析：图可以用来研究社会关系。

### 图的存储图可以使用邻接矩阵或邻接链表来存储。邻接矩阵是一种二维数组，每个元素表示两个顶点之间是否存在边。如果有边，则该元素为1；否则，为0。邻接链表是一种链式数据结构，用于存储图中的每条边。

### 图的遍历图的遍历是指按照一定的顺序访问图中所有顶点的过程。常见的遍历算法包括：

* 深度优先搜索（DFS）：从一个顶点开始，沿着边向下探索，直到达到叶子结点。
* 广度优先搜索（BFS）：从一个顶点开始，沿着边向下探索，但每层都访问完毕后再往下一层。

### 图的应用代码示例

import networkx as nximport matplotlib.pyplot as plt# 创建一个空图G = nx.Graph()

# 添加顶点G.add_node(1)
G.add_node(2)
G.add_node(3)

# 添加边G.add_edge(1,2)
G.add_edge(2,3)
G.add_edge(3,1)

# 使用DFS遍历图def dfs(graph):
 visited = set()
 def dfs_helper(node):
 visited.add(node)
 for neighbor in graph[node]:
 if neighbor not in visited:
 dfs_helper(neighbor)
 dfs_helper(1)
 return visitedvisited_nodes = dfs(G)
print("Visited nodes:", visited_nodes)

# 使用BFS遍历图from collections import dequedef bfs(graph):
 visited = set()
 queue = deque([1])
 while queue:
 node = queue.popleft()
 if node not in visited:
 visited.add(node)
 for neighbor in graph[node]:
 if neighbor not in visited:
 queue.append(neighbor)
 return visitedvisited_nodes_bfs = bfs(G)
print("Visited nodes (BFS):", visited_nodes_bfs)

# 使用matplotlib绘制图pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_color='lightblue')
nx.draw_networkx_edges(G, pos, edge_color='gray', arrows=False)
nx.draw_networkx_labels(G, pos, font_size=10, font_family='sans-serif')

plt.show()