教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

无向图

介绍

无向图(Undirected Graph)是图论中最基础的图结构之一,其中的边没有方向性,表示节点之间的双向连接关系。在无向图中,如果顶点A和顶点B之间有一条边,那么可以从A到达B,也可以从B到达A。这种对称的连接关系使无向图成为表示许多现实世界中双向关系的理想模型。

无向图中的关键概念包括:

  • 顶点(Vertex):图中的节点,通常用数字或字母标识。
  • 边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。在无向图中,边用无序对{u,v}表示,表明顶点u和v之间有连接。
  • 度(Degree):与某个顶点相连的边的数量。例如,如果顶点v连接了3条边,则顶点v的度为3。
  • 路径(Path):从一个顶点到另一个顶点经过的边的序列。
  • 连通图(Connected Graph):任意两个顶点之间都存在路径的图。
  • 连通分量(Connected Component):图中的极大连通子图。

核心特性

  • 双向连接:任何边都可以双向通行,从一个顶点可以到达相邻的任何顶点
  • 对称性:如果顶点A与顶点B相连,那么顶点B也与顶点A相连
  • 度的概念:顶点的度表示与该顶点相连的边的数量
  • 连通性:无向图的连通性比有向图更为简单,只需考虑是否存在路径,不需要考虑方向
  • 树与环:无环的连通无向图是一棵树;含有环的图至少有一条路径可以从一个顶点出发最终回到该顶点

...

目录