图论基础：顶点、边和连接性的概念

# 1. 图论基础概述

图论作为离散数学的一个分支，研究的是图这种数学结构。图论可以用来描述各种实际问题，比如网络拓扑结构、社交网络关系等。图论的基础知识对于计算机科学领域的算法设计和问题求解也具有重要意义。

## 1.1 图论简介

图是由节点（顶点）和节点之间连线（边）组成的一种抽象数学模型。图论研究的是图的性质和在其中进行特定操作的方法。图可以分为有向图和无向图，边可以带权重。

## 1.2 图的基本概念

- **顶点（Vertex）**：图中的节点，可以表示为一个数据结构。
- **边（Edge）**：连接顶点的线，描述顶点之间的关系。
- **路径（Path）**：顶点序列，使得相邻顶点之间都有边相连。
- **环（Cycle）**：形成闭合路径的路径，起点和终点相同。
- **度数（Degree）**：与顶点相关联的边的数量。
- **连通性（Connectivity）**：描述图中顶点之间是否存在路径相连的性质。

## 1.3 图的应用领域

图论在实际中有着广泛的应用，比如：

- **网络拓扑**：描述计算机网络中设备之间的连接方式。
- **社交网络分析**：研究社交网络中个体之间的关系。
- **路径规划**：寻找图中两个顶点之间的最短路径。
- **最优匹配**：在图中找到最佳的匹配方式。

图论基础的掌握对于后续学习更复杂的图算法和应用是至关重要的。

# 2. 顶点和边的概念

在图论中，顶点和边是构成图结构的基本要素。理解和掌握顶点和边的概念对于深入学习图论非常重要。在本章中，我们将介绍顶点和边的定义、属性，以及有向图和无向图的区别。

### 2.1 顶点的定义和属性

顶点（Vertex）是图中的基本元素，通常用于表示一个实体或节点。每个顶点可以携带一些属性信息，例如顶点的标识符、权重等。在图论中，顶点也常被称为节点（Node）。

### 2.2 边的定义和属性

边（Edge）是连接顶点之间的关系。一条边可以是有向的，也可以是无向的，分别对应有向图和无向图。边也可以携带一些属性信息，比如边的权重。在有向图中，边由起始顶点和终止顶点组成；而在无向图中，边则是连接两个顶点的线段。

### 2.3 有向图和无向图的区别

有向图（Directed Graph）是由一组有序的顶点和边组成的图，其中每条边都有一个方向，即从一个顶点指向另一个顶点。无向图（Undirected Graph）则是没有方向的图，边仅表示连接两个顶点的关系，不区分起始点和终止点。

掌握顶点和边的概念是理解图论的基础，也为后续学习图的表示方法和算法打下了基础。在下一章节中，我们将介绍图的表示方法，以便更好地操作和处理图结构数据。

# 3. 图的表示方法

在图论中，图的表示方法是非常重要的，不同的表示方法适用于不同的场景，下面我们将介绍三种常用的图的表示方法。

#### 3.1 邻接矩阵

邻接矩阵是最常见、最直接的一种图的表示方法。在邻接矩阵中，图的顶点被映射为矩阵中的行和列，而边则通过矩阵中的元素表示。对于无向图，若顶点 i 与顶点 j 之间有边，则矩阵中 (i, j) 和 (j, i) 的元素为 1；若无边，则为 0。对于有向图，仅在顶点 i 指向顶点 j 的情况下，矩阵中 (i, j) 的元素为 1。

# 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, v1, v2):
        self.adj_matrix[v1][v2] = 1
        self.adj_matrix[v2][v1] = 1

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

# 创建一个包含 4 个顶点的无向图，并添加边
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)

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

**代码总结：** 以上是使用Python实现的邻接矩阵表示图的示例。顶点之间的边通过矩阵元素的值表示，1 代表存在边，0 代表无边。

**结果说明：** 运行上述代码后，将打印出无向图的邻接矩阵表示，展示顶点间的连接关系。

#### 3.2 邻接表

邻接表是另一种常用的图的表示方法，它将图的顶点以及与之相邻的边以链表的形式存储起来，适用于稀疏图。每个顶点对应一个链表，链表中存储与该顶点相连的其他顶点。

// Java代码示例：邻接表表示图
import java.util.*;

class Graph {
    private int numVertices;
    private LinkedList<Integer>[] adjList;

    @SuppressWarnings("unchecked")
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int v1, int v2) {
        adjList[v1].add(v2);
        adjList[v2].add(v1); // 无向图需添加反向边
    }

    public void printAdjList() {
        for (int i = 0; i < numVertices; i++) {
            System.out.print(i + " -> ");
            for (int v : adjList[i]) {
                System.out.print(v + " ");
            }
            System.out.println();