图的两种存储方式和遍历方式代码实现
时间: 2023-10-16 12:07:14 浏览: 86
图的两种存储方式:
1. 邻接矩阵存储方式
邻接矩阵是一种二维数组,其中每一个元素都代表着两个顶点之间的边。如果两个顶点之间有边相连,则对应的数组元素值为 1,否则为 0。
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, v1, v2):
self.matrix[v1][v2] = 1
self.matrix[v2][v1] = 1
def remove_edge(self, v1, v2):
self.matrix[v1][v2] = 0
self.matrix[v2][v1] = 0
```
2. 邻接表存储方式
邻接表是由一个数组和一个链表组成。数组中每个元素对应一个顶点,链表中存储该顶点连接的其他顶点。
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, v1, v2):
self.adj_list[v1].append(v2)
self.adj_list[v2].append(v1)
def remove_edge(self, v1, v2):
self.adj_list[v1].remove(v2)
self.adj_list[v2].remove(v1)
```
图的遍历方式:
1. 深度优先遍历(DFS)
深度优先遍历是一种通过对每个节点深度优先搜索来遍历整个图的算法。从起点开始遍历,访问一个节点后,递归地访问它的所有邻居节点。
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, v1, v2):
self.adj_list[v1].append(v2)
self.adj_list[v2].append(v1)
def dfs(self, start):
visited = [False] * self.num_vertices
self._dfs(start, visited)
def _dfs(self, vertex, visited):
visited[vertex] = True
print(vertex, end=' ')
for neighbor in self.adj_list[vertex]:
if not visited[neighbor]:
self._dfs(neighbor, visited)
```
2. 广度优先遍历(BFS)
广度优先遍历是一种通过对每个节点广度优先搜索来遍历整个图的算法。从起点开始遍历,访问一个节点后,访问它的所有邻居节点。
```python
from queue import Queue
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adj_list = [[] for _ in range(num_vertices)]
def add_edge(self, v1, v2):
self.adj_list[v1].append(v2)
self.adj_list[v2].append(v1)
def bfs(self, start):
visited = [False] * self.num_vertices
queue = Queue()
visited[start] = True
queue.put(start)
while not queue.empty():
vertex = queue.get()
print(vertex, end=' ')
for neighbor in self.adj_list[vertex]:
if not visited[neighbor]:
visited[neighbor] = True
queue.put(neighbor)
```