数据结构——图

**数据结构——图**

图是一种非线性的数据结构，它由一组顶点（也称为结点或节点）和一组边连接这些顶点而成。每条边都代表着两个顶点之间的关系。

**图的定义**

一个图G可以用以下方式定义：

* G = (V, E)，其中V是顶点集合，E是边集合。
* 每个顶点v∈V都有一个唯一的标识符或名称。
* 每条边e∈E都连接两个顶点u和v，并且可以表示为(u,v)。

**图的类型**

根据图中边的方向性质，图可以分为以下几种类型：

* **无向图（Undirected Graph）**：每条边都是无向的，即不论从哪个顶点出发，都可以到达相应的另一个顶点。
* **有向图（Directed Graph）**：每条边都有方向性，意味着从某个顶点出发，可以到达相应的另一个顶点，但不能反过来。

**图的应用**

图在计算机科学和其他领域中有广泛的应用：

* **网络分析**：图可以用来表示复杂的网络结构，如社交网络、交通网络等。
* **路由算法**：图可以用来实现路由算法，例如Dijkstra算法、Bellman-Ford算法等。
* **推荐系统**：图可以用来表示用户之间的关系和兴趣，从而实现推荐系统。

**图的操作**

以下是对图进行的一些基本操作：

* **插入顶点（Insert Vertex）**：将一个新顶点添加到图中。
* **删除顶点（Delete Vertex）**：从图中移除一个顶点，并且更新所有与该顶点相关的边。
* **插入边（Insert Edge）**：将一条新的边连接两个顶点。
* **删除边（Delete Edge）**：从图中移除一条边。

**图的遍历**

以下是对图进行的一些基本遍历：

* **深度优先搜索（Depth-First Search，DFS）**：从一个起始顶点出发，沿着图中的边向下探索，直到达到叶子结点。
* **广度优先搜索（Breadth-First Search，BFS）**：从一个起始顶点出发，沿着图中的边向下探索，但每次只访问距离起始顶点最近的顶点。

**图的实现**

以下是对图进行的一些基本实现：

* **邻接矩阵（Adjacency Matrix）**：使用一个二维数组来表示图中所有可能的边。
* **邻接链表（Adjacency List）**：使用一个链表来表示每个顶点所连接的其他顶点。

以下是对图进行的一些基本实现代码示例：

class Graph:
 def __init__(self):
 self.V =0 self.E =0 self.adj_matrix = None def add_vertex(self, v):
 if self.V ==0:
 self.V =1 self.E =0 self.adj_matrix = [[0 for _ in range(v)] for _ in range(v)]
 else:
 self.V +=1 self.E += v def add_edge(self, u, v):
 if u < self.V and v < self.V:
 self.adj_matrix[u][v] =1 self.E +=1 def print_graph(self):
 for i in range(self.V):
 for j in range(self.V):
 print(self.adj_matrix[i][j], end=' ')
 print()

# 创建一个图g = Graph()
g.add_vertex(5)
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,3)
g.add_edge(2,4)

# 打印图g.print_graph()