【数据结构-图】

💖💝亲亲， 创作不易 看完点点专注呀♥❤💕💞

目录：

图的基本概念与表示方法知识点总结及示例

1. 图的定义

• 知识点总结：图（Graph）是由顶点（Vertex）的集合和边（Edge）的集合组成的一种数据结构，通常用 $G=(V,E)$ 表示，其中 $V$ 是顶点的有限非空集合，$E$ 是边的集合，边表示顶点之间的关系图可以用来模拟各种现实世界中的关系，如社交网络、交通网络等。
• 示例：在一个社交网络中，每个人可以看作是图中的一个顶点，人与人之间的好友关系可以看作是图中的边。假设有三个人 A、B、C，A 和 B 是好友，B 和 C 是好友，那么这个社交网络就可以用一个包含三个顶点（A、B、C）和两条边（A - B，B - C）的图来表示。

2. 无向图

• 知识点总结：无向图中的边没有方向，即如果顶点 $u$ 和顶点 $v$ 之间有一条边，那么可以从 $u$ 到 $v$，也可以从 $v$ 到 $u$，边用无序对 $(u,v)$ 表示。无向图常用于表示对称关系，如朋友关系、道路连接等。
• 示例：

城市之间的道路连接可以用无向图来表示。假设有三个城市 A、B、C，城市 A 和城市 B 之间有一条双向道路，城市 B 和城市 C
之间也有一条双向道路。那么可以用一个无向图来表示这个道路网络，其中顶点 A、B、C 分别代表三个城市，边 $(A,B)$ 和 $(B,C)$ 分别代表两条道路。

3. 有向图

• 知识点总结：有向图中的边是有方向的，每条边都有一个起始顶点和一个终止顶点，用有序对 $⟨u,v⟩$ 表示从顶点 $u$ 到顶点 $v$ 的一条有向边。有向图常用于表示非对称关系，如网页链接、任务依赖关系等。
• 示例：网页之间的链接关系可以用有向图来表示。假设有三个网页 A、B、C，网页 A 中有一个链接指向网页 B，网页 B 中有一个链接指向网页 C。那么可以用一个有向图来表示这个网页链接网络，其中顶点 A、B、C 分别代表三个网页，有向边 $⟨A,B⟩$ 和 $⟨B,C⟩$ 分别代表两个链接。
  

4. 图的邻接矩阵表示

• 知识点总结：邻接矩阵是一个二维数组，对于一个有 $n$ 个顶点的图，矩阵的大小为 $n\times n$。如果顶点 $i$ 和顶点 $j$ 之间有边相连，则矩阵中第 $i$ 行第 $j$ 列的元素为 1（或边的权重），否则为 0。邻接矩阵的优点是可以快速判断两个顶点之间是否有边相连，缺点是空间复杂度较高，为 $O(n^2)$。
• 示例：对于一个有 4 个顶点的无向图，其邻接矩阵如下：

这个邻接矩阵表示顶点 0 和顶点 1、2 之间有边相连，顶点 1 和顶点 0、2 之间有边相连，顶点 2 和顶点 0、1、3 之间有边相连，顶点 3 和顶点 2 之间有边相连。

5. 图的邻接表表示

• 知识点总结：邻接表是一个数组，数组的每个元素是一个链表，数组的每个元素对应一个顶点，链表中存储与该顶点相邻的顶点。邻接表的优点是空间复杂度较低，为 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数，缺点是判断两个顶点之间是否有边相连的时间复杂度较高，为 $O(degree(u))$，其中 $degree(u)$ 是顶点 $u$ 的度。
• 示例：对于上述有 4 个顶点的无向图，其邻接表表示如下：
• 顶点 0：1 -> 2->3
• 顶点 1：0 -> 2
• 顶点 2：0 -> 1 -> 3
• 顶点 3：2
  这个邻接表表示顶点 0 与顶点 1、2 相邻，顶点 1 与顶点 0、2 相邻，顶点 2 与顶点 0、1、3 相邻，顶点 3 与顶点 2 相邻。

1. 图的邻接矩阵表示

有向图邻接矩阵实现

#include <iostream>
#include <vector>

class DirectedGraphAdjMatrix {
private:
    int V; // 顶点数
    std::vector<std::vector<int>> adjMatrix;

public:
    DirectedGraphAdjMatrix(int vertices) : V(vertices) {
        adjMatrix.resize(V, std::vector<int>(V, 0));
    }

    // 添加有向边
    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
    }

    // 打印邻接矩阵
    void printAdjMatrix() {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                std::cout << adjMatrix[i][j] << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    DirectedGraphAdjMatrix digraph(4);
    digraph.addEdge(0, 1);
    digraph.addEdge(0, 2);
    digraph.addEdge(1, 2);
    digraph.addEdge(2, 3);
    std::cout << "Directed Graph Adjacency Matrix:" << std::endl;
    digraph.printAdjMatrix();
    return 0;
}

无向图邻接矩阵实现

#include <iostream>
#include <vector>

class UndirectedGraphAdjMatrix {
private:
    int V; // 顶点数
    std::vector<std::vector<int>> adjMatrix;

public:
    UndirectedGraphAdjMatrix(int vertices) : V(vertices) {
        adjMatrix.resize(V, std::vector<int>(V, 0));
    }

    // 添加无向边
    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;
    }

    // 打印邻接矩阵
    void printAdjMatrix() {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                std::cout << adjMatrix[i][j] << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    UndirectedGraphAdjMatrix undigraph(4);
    undigraph.addEdge(0, 1);
    undigraph.addEdge(0, 2);
    undigraph.addEdge(1, 2);
    undigraph.addEdge(2, 3);
    std::cout << "Undirected Graph Adjacency Matrix:" << std::endl;
    undigraph.printAdjMatrix();
    return 0;
}

2. 图的邻接表表示

有向图邻接表实现

#include <iostream>
#include <vector>

class DirectedGraphAdjList {
private:
    int V; // 顶点数
    std::vector<std::vector<int>> adjList;

public:
    DirectedGraphAdjList(int vertices) : V(vertices) {
        adjList.resize(V);
    }

    // 添加有向边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }

    // 打印邻接表
    void printAdjList() {
        for (int i = 0; i < V; ++i) {
            std::cout << "Vertex " << i << ": ";
            for (int v : adjList[i]) {
                std::cout << v << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    DirectedGraphAdjList digraph(4);
    digraph.addEdge(0, 1);
    digraph.addEdge(0, 2);
    digraph.addEdge(1, 2);
    digraph.addEdge(2, 3);
    std::cout << "Directed Graph Adjacency List:" << std::endl;
    digraph.printAdjList();
    return 0;
}

无向图邻接表实现

#include <iostream>
#include <vector>

class UndirectedGraphAdjList {
private:
    int V; // 顶点数
    std::vector<std::vector<int>> adjList;

public:
    UndirectedGraphAdjList(int vertices) : V(vertices) {
        adjList.resize(V);
    }

    // 添加无向边
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    // 打印邻接表
    void printAdjList() {
        for (int i = 0; i < V; ++i) {
            std::cout << "Vertex " << i << ": ";
            for (int v : adjList[i]) {
                std::cout << v << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main() {
    UndirectedGraphAdjList undigraph(4);
    undigraph.addEdge(0, 1);
    undigraph.addEdge(0, 2);
    undigraph.addEdge(1, 2);
    undigraph.addEdge(2, 3);
    std::cout << "Undirected Graph Adjacency List:" << std::endl;
    undigraph.printAdjList();
    return 0;
}

代码解释

• 邻接矩阵：
  • 对于有向图，若顶点 u 到顶点 v 有边，则 adjMatrix[u][v] = 1。
  • 对于无向图，由于边是无向的，若顶点 u 和 v 之间有边，则 adjMatrix[u][v] = 1 且 adjMatrix[v][u] = 1。
• 邻接表：
  • 对于有向图，将目标顶点 v 加入源顶点 u 的邻接表中。
  • 对于无向图，需要同时将 v 加入 u 的邻接表和 u 加入 v 的邻接表。

复杂度分析

• 邻接矩阵：
  • 空间复杂度：$O(V^2)$，其中 $V$ 是顶点数。
  • 添加边的时间复杂度：$O(1)$。
  • 查找边的时间复杂度：$O(1)$。
• 邻接表：
  • 空间复杂度：$O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。
  • 添加边的时间复杂度：$O(1)$。
  • 查找边的时间复杂度：平均 $O(degree(u))$，其中 $degree(u)$ 是顶点 u 的度。

完全图

1. 定义

完全图是一种特殊的图，根据边是否有方向，可分为无向完全图和有向完全图。

• 无向完全图：在一个具有 $n$ 个顶点的无向图中，如果任意两个不同顶点之间都存在一条无向边，那么这个图就被称为无向完全图。也就是说，对于无向完全图中的任意两个顶点 $u$ 和 $v$（$u\ne v$），都有边 $(u,v)$ 存在。
• 有向完全图：在一个具有 $n$ 个顶点的有向图中，如果任意两个不同顶点之间都存在两条方向相反的有向边，即对于任意两个不同顶点 $u$ 和 $v$（$u\ne v$），都有有向边 $⟨u,v⟩$ 和 $⟨v,u⟩$ 存在，那么这个图就被称为有向完全图。

2. 边的数量

• 无向完全图：对于一个具有 $n$ 个顶点的无向完全图，边的数量可以通过组合数公式计算。从 $n$ 个顶点中任选 2 个顶点的组合数为 $C_n^2=\frac{n(n-1)}{2}$，所以无向完全图的边数为 $\frac{n(n-1)}{2}$。
• 有向完全图：在有向完全图中，每两个不同顶点之间有两条方向相反的有向边。所以边的数量是无向完全图边数的 2 倍，即 $n(n-1)$。

3. 特点

• 连通性：无向完全图和有向完全图都是高度连通的。在无向完全图中，任意两个顶点之间都有路径相连；在有向完全图中，从任意一个顶点出发都可以到达其他所有顶点。
• 对称性：无向完全图具有很强的对称性，每个顶点的度（与该顶点相连的边的数量）都相同，均为 $n-1$；有向完全图中每个顶点的入度（指向该顶点的边的数量）和出度（从该顶点出发的边的数量）也都相同，均为 $n-1$。

示例

无向完全图示例

假设我们有一个无向完全图 $G=(V,E)$，其中顶点集 V = { A , B , C } V = \{A, B, C\} V={A,B,C}。由于是无向完全图，任意两个不同顶点之间都有边相连，所以边集 $E=\{(A,B),(A,C),(B,C)\}$。这里 $n=3$，根据边数公式 $\frac{n(n-1)}{2}=\frac{3\times (3-1)}{2}=3$，与实际边数相符。每个顶点的度都是 $n-1=2$，例如顶点 $A$ 与顶点 $B$ 和 $C$ 相连，度为 2。

有向完全图示例

考虑一个有 3 个顶点的有向完全图，顶点集 V = { 1 , 2 , 3 } V=\{1, 2, 3\} V={1,2,3}。边集 $E=\{⟨1,2⟩,⟨2,1⟩,⟨1,3⟩,⟨3,1⟩,⟨2,3⟩,⟨3,2⟩\}$。这里 $n=3$，根据边数公式 $n(n-1)=3\times (3-1)=6$，与实际边数一致。每个顶点的入度和出度都是 $n-1=2$，比如顶点 1 有两条出边 $⟨1,2⟩$ 和 $⟨1,3⟩$，两条入边 $⟨2,1⟩$ 和 $⟨3,1⟩$。

代码实现（Python）

# 无向完全图的邻接矩阵表示
def undirected_complete_graph(n):
    graph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            graph[i][j] = 1
            graph[j][i] = 1
    return graph

# 有向完全图的邻接矩阵表示
def directed_complete_graph(n):
    graph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                graph[i][j] = 1
    return graph

# 示例：创建 3 个顶点的无向和有向完全图
n = 3
undirected_graph = undirected_complete_graph(n)
directed_graph = directed_complete_graph(n)

print("无向完全图的邻接矩阵:")
for row in undirected_graph:
    print(row)

print("\n有向完全图的邻接矩阵:")
for row in directed_graph:
    print(row)

代码解释

• undirected_complete_graph 函数：该函数用于创建一个具有 $n$ 个顶点的无向完全图的邻接矩阵。通过两层循环遍历顶点对，对于不同的顶点 $i$ 和 $j$（$i<j$），将邻接矩阵中
  graph[i][j] 和 graph[j][i] 置为 1，表示有边相连。
• directed_complete_graph 函数：该函数用于创建一个具有 $n$ 个顶点的有向完全图的邻接矩阵。通过两层循环遍历所有顶点对，当 $i\ne j$ 时，将邻接矩阵中 graph[i][j] 置为
  1，表示有从 $i$ 到 $j$ 的有向边。
• 主程序部分：创建了一个有 3 个顶点的无向完全图和有向完全图，并打印出它们的邻接矩阵。

图的常见存储方式有邻接矩阵、邻接表、邻接多重表和十字链表，下面将分别介绍这些存储方式并给出对应的代码示例。

1. 邻接矩阵

知识点总结

邻接矩阵是一个二维数组，对于一个具有 $n$ 个顶点的图，其邻接矩阵是一个 $n\times n$ 的矩阵。若顶点 $i$ 和顶点 $j$ 之间有边相连，矩阵中第 $i$ 行第 $j$ 列的元素值为 1（无权图）或边的权重（带权图）；若无边相连，则元素值为 0（无权图）或无穷大（带权图）。

代码示例（Python）

# 无向无权图的邻接矩阵表示
class GraphAdjMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 初始化邻接矩阵，元素全为 0
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, u, v):
        # 无向图，对称位置都置为 1
        self.adj_matrix[u][v] = 1
        self.adj_matrix[v][u] = 1

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


# 创建一个有 4 个顶点的无向无权图
graph = GraphAdjMatrix(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()

2. 邻接表

知识点总结

邻接表是一种数组和链表相结合的存储方式。对于每个顶点，使用一个链表来存储与该顶点相邻的所有顶点。在实际实现中，也可以用 Python 的列表或 C++ 的 std::vector 来代替链表。

代码示例（Python）

# 无向无权图的邻接表表示
class GraphAdjList:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # 初始化邻接表，每个顶点对应一个空列表
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        # 无向图，两个顶点的邻接表都要添加对方
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def print_adj_list(self):
        for i in range(self.num_vertices):
            print(f"Vertex {i}: {self.adj_list[i]}")


# 创建一个有 4 个顶点的无向无权图
graph = GraphAdjList(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.print_adj_list()

3. 邻接多重表（主要用于无向图）

知识点总结

邻接多重表是对邻接表的一种改进，主要用于解决无向图中边的重复存储问题。在邻接多重表中，每条边只存储一次，通过一些指针来表示边与顶点的关联关系。

代码示例（Python）

# 边节点类
class EdgeNode:
    def __init__(self, mark, ivex, jvex, ilink, jlink):
        self.mark = mark  # 标记该边是否被访问过
        self.ivex = ivex  # 边的一个顶点
        self.jvex = jvex  # 边的另一个顶点
        self.ilink = ilink  # 指向下一条依附于 ivex 的边
        self.jlink = jlink  # 指向下一条依附于 jvex 的边


# 顶点节点类
class VertexNode:
    def __init__(self, data, firstedge):
        self.data = data  # 顶点的数据
        self.firstedge = firstedge  # 指向第一条依附于该顶点的边


# 邻接多重表类
class AMLGraph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_multi_list = [VertexNode(i, None) for i in range(num_vertices)]

    def add_edge(self, u, v):
        new_edge = EdgeNode(0, u, v, None, None)
        # 处理依附于 u 的边
        if not self.adj_multi_list[u].firstedge:
            self.adj_multi_list[u].firstedge = new_edge
        else:
            p = self.adj_multi_list[u].firstedge
            while p.ilink and p.ivex == u:
                p = p.ilink
            if p.ivex == u:
                p.ilink = new_edge
        # 处理依附于 v 的边
        if not self.adj_multi_list[v].firstedge:
            self.adj_multi_list[v].firstedge = new_edge
        else:
            p = self.adj_multi_list[v].firstedge
            while p.jlink and p.jvex == v:
                p = p.jlink
            if p.jvex == v:
                p.jlink = new_edge


# 创建一个有 4 个顶点的无向图
graph = AMLGraph(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

4. 十字链表（主要用于有向图）

知识点总结

十字链表是有向图的一种链式存储结构，它结合了邻接表和逆邻接表的特点，能够方便地找到以某个顶点为起点的边和以某个顶点为终点的边。

代码示例（Python）

# 弧节点类
class ArcNode:
    def __init__(self, tailvex, headvex, hlink, tlink):
        self.tailvex = tailvex  # 弧的起点
        self.headvex = headvex  # 弧的终点
        self.hlink = hlink  # 指向相同终点的下一条弧
        self.tlink = tlink  # 指向相同起点的下一条弧


# 顶点节点类
class VertexNode:
    def __init__(self, data, firstin, firstout):
        self.data = data  # 顶点的数据
        self.firstin = firstin  # 指向第一条以该顶点为终点的弧
        self.firstout = firstout  # 指向第一条以该顶点为起点的弧


# 十字链表类
class OLGraph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.orthogonal_list = [VertexNode(i, None, None) for i in range(num_vertices)]

    def add_edge(self, u, v):
        new_arc = ArcNode(u, v, None, None)
        # 处理以 u 为起点的弧
        if not self.orthogonal_list[u].firstout:
            self.orthogonal_list[u].firstout = new_arc
        else:
            p = self.orthogonal_list[u].firstout
            while p.tlink:
                p = p.tlink
            p.tlink = new_arc
        # 处理以 v 为终点的弧
        if not self.orthogonal_list[v].firstin:
            self.orthogonal_list[v].firstin = new_arc
        else:
            p = self.orthogonal_list[v].firstin
            while p.hlink:
                p = p.hlink
            p.hlink = new_arc


# 创建一个有 4 个顶点的有向图
graph = OLGraph(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。常见的图的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS），下面将分别介绍这两种遍历方法的知识点及代码示例。

深度优先搜索（DFS）

知识点总结

• 基本思想：深度优先搜索是一种递归的搜索算法，它沿着一条路径尽可能深地访问顶点，直到无法继续，然后回溯到前一个顶点，继续探索其他路径。类似于树的先序遍历。
• 实现步骤：
  1. 选择一个起始顶点，标记该顶点为已访问。
  2. 递归地访问该顶点的所有未访问的邻接顶点。
  3. 回溯到上一个顶点，继续探索其他未访问的邻接顶点。
• 复杂度分析：
  • 时间复杂度：使用邻接矩阵存储图时，时间复杂度为 $O(V^2)$，其中 $V$ 是顶点数；使用邻接表存储图时，时间复杂度为 $O(V+E)$，其中 $E$ 是边数。
  • 空间复杂度：主要是递归栈的空间，最坏情况下为 $O(V)$。

代码示例（Python，使用邻接表存储图）

# 图的邻接表表示
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2]
}

# 记录顶点是否被访问过
visited = [False] * len(graph)

def dfs(v):
    # 标记当前顶点为已访问
    visited[v] = True
    print(v, end=' ')
    # 递归访问所有未访问的邻接顶点
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(neighbor)

# 从顶点 0 开始进行深度优先搜索
print("深度优先搜索结果:")
dfs(0)

广度优先搜索（BFS）

知识点总结

• 基本思想：广度优先搜索是一种基于队列的搜索算法，它从起始顶点开始，逐层地访问顶点，先访问距离起始顶点最近的所有顶点，然后再依次访问更远的顶点。类似于树的层序遍历。
• 实现步骤：
  1. 选择一个起始顶点，标记该顶点为已访问，并将其加入队列。
  2. 当队列不为空时，取出队列的队首顶点，访问其所有未访问的邻接顶点，标记为已访问，并将它们加入队列。
  3. 重复步骤 2，直到队列为空。
• 复杂度分析：
  • 时间复杂度：使用邻接矩阵存储图时，时间复杂度为 $O(V^2)$；使用邻接表存储图时，时间复杂度为 $O(V+E)$。
  • 空间复杂度：主要是队列的空间，最坏情况下为 $O(V)$。

代码示例（Python，使用邻接表存储图）

from collections import deque

# 图的邻接表表示
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2]
}

# 记录顶点是否被访问过
visited = [False] * len(graph)

def bfs(v):
    # 创建一个队列
    queue = deque()
    # 标记起始顶点为已访问，并加入队列
    visited[v] = True
    queue.append(v)

    while queue:
        # 取出队首顶点
        s = queue.popleft()
        print(s, end=' ')
        # 访问所有未访问的邻接顶点
        for neighbor in graph[s]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

# 从顶点 0 开始进行广度优先搜索
print("\n广度优先搜索结果:")
bfs(0)

总结

• 深度优先搜索更适合探索图的深层次结构，常用于寻找连通分量、拓扑排序等问题。
• 广度优先搜索更适合寻找最短路径等问题，因为它是逐层访问顶点的。
  

💖💝亲亲， 创作不易 看完点点专注呀♥❤💕💞