图论入门：认识图的基本结构与表示方式

### 1. 引言
#### 简介
图论是数学的一个分支，研究的对象是图，它是由若干的顶点和连接这些顶点的边组成的一种数学模型。图论作为离散数学的一个重要分支，在计算机科学与信息技术领域有着广泛的应用，如网络分析、路径规划、最优化、图像处理等。正因如此，掌握图论基础知识对于从事IT行业的专业人士来说至关重要。

#### 图论在IT领域中的重要性
图论在计算机科学与信息技术领域中具有广泛的应用，例如在网络安全领域中，可以使用图模型来分析网络拓扑结构，发现异常节点与连接；在社交网络分析中，可以利用图模型来识别社区结构、发现潜在关系等。此外，在路径规划与导航系统、匹配问题与最优化、图像处理与计算机视觉等方面也有着重要的应用价值。因此，深入理解图论的基本概念和算法对于从事IT行业的人员具有重要意义。

### 2. 图的基本概念
#### 顶点与边
在图论中，图是由顶点集合和边集合组成的。顶点表示图中的个体，可以是任何事物的抽象模型；边表示顶点之间的连接关系，可以是有向的或无向的，可以带有权值或者不带权值。

#### 有向图与无向图
有向图是由顶点的有序对（u，v）的集合以及连接这些有序对的边的集合组成的一种图模型。每条边是一个有序对，表示由顶点u指向顶点v。无向图是由顶点的无序对（u，v）的集合以及连接这些无序对的边的集合组成的一种图模型。每条边是一个无序对，表示连接顶点u和顶点v，没有方向之分。

#### 带权图与无权图
带权图是图的边上带有权值的图模型，这些权值可以代表不同的含义，比如距离、成本等。无权图则是图的边上没有带权值的图模型，表示两个顶点之间的连接关系。

### 3. 图的表示方式

在图论中，为了方便理解和处理图的相关算法，我们需要将图的结构进行适当的表示。下面介绍三种常用的图的表示方式：邻接矩阵表示法、邻接表表示法和关联矩阵表示法。

#### 3.1 邻接矩阵表示法

邻接矩阵是一种基于二维矩阵的图的表示方式。对于一个有n个顶点的图，可以使用一个n×n的矩阵来表示，矩阵中的元素表示两个顶点之间是否存在边。

例如，对于无向图来说，如果从顶点i到顶点j存在边，则邻接矩阵中的第(i, j)和第(j, i)个元素都为1；如果不存在边，则为0。如果图是有权图，那么矩阵中的元素可以表示边的权值。

下面是使用邻接矩阵表示法表示的图的示例代码（Python实现）：

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, src, dest):
        self.adj_matrix[src][dest] = 1
        self.adj_matrix[dest][src] = 1

    def print_adj_matrix(self):
        for row in self.adj_matrix:
            print(row)


# 创建一个无向图并添加边
graph = Graph(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

# 打印邻接矩阵
graph.print_adj_matrix()

代码解析：
- `class Graph` 定义了一个图的类，其中`__init__`方法初始化了图的顶点数和邻接矩阵，`add_edge`方法用于添加边，`print_adj_matrix`方法用于打印邻接矩阵。
- 使用`add_edge`方法添加了几条边。
- 调用`print_adj_matrix`方法打印了邻接矩阵。

运行上述代码，将输出以下结果：

[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 0, 1]
[0, 0, 1, 0]

以上结果表示了一个有4个顶点的无向图的邻接矩阵。

#### 3.2 邻接表表示法

除了使用邻接矩阵表示法，我们还可以使用邻接表来表示图的结构。邻接表是一种基于链表的表示方式，对于每个顶点，使用一个链表来存储与其相连的顶点。

下面是使用邻接表表示法表示的图的示例代码（Python实现）：

from collections import defaultdict


class Graph:
    def __init__(self):
        self.