图与树的基本概念

By 4627488

幻灯片PDF

关键词：图、邻接矩阵、邻接表、树、遍历算法

图的基本概念

定义与组成

图 $G = (V, E)$ ，其中 $V$ 是顶点集合， $E$ 是边集合。

顶点（Vertex）：图中的节点。
边（Edge）：顶点间的连接关系。

alt text

图的分类

类型	特点	例子
无向图	边无方向， $(u, v) = (v, u)$	社交网络好友关系
有向图	边有方向， $u \to v \neq v \to u$	网页超链接关系

若 $G$ 的每条边 $e_{k} = (u_{k}, v_{k})$ 都被赋予一个数作为该边的权，则称 $G$ 为 赋权图。如果这些权都是正实数，就称 $G$ 为 正权图。

形象地说，图是由若干点以及连接点与点的边构成的。

度（Degree）

无向图：顶点连接的边数。
有向图：入度（指向顶点的边数）、出度（顶点指向外部的边数）。

路径与环路

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。
定义
形式化地说，一条有限途径 $w$ 是一个边的序列 $e_{1}, e_{2}, \dots, e_{k}$ ，使得存在一个顶点序列 $v_{0}, v_{1}, \dots, v_{k}$ 满足 $e_{i} = (v_{i - 1}, v_{i})$ ，其中 $i \in [1, k]$ 。这样的途径可以简写为 $v_{0} \to v_{1} \to v_{2} \to \dots \to v_{k}$ 。通常来说，边的数量 $k$ 被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和，题目中也可能另有定义）。
路径（path）：顶点序列 $v_{1} \to v_{2} \to \dots \to v_{k}$ ，相邻顶点间有边。
简单路径（simple path）：没有重复顶点的路径。
环路/圈（cycle）：起点和终点相同的路径（如 $v_{1} \to v_{2} \to v_{1}$ ）。
自环：起点和终点相同的边（如 $(v_{1}, v_{1})$ ）。
重边：连接同一顶点的多条边（如 $(v_{1}, v_{2})$ 和 $(v_{1}, v_{2})$ ）。
注意
在无向图中 $(u, v)$ 和 $(v, u)$ 算一组重边，而在有向图中， $u \to v$ 和 $v \to u$ 不为重边。
在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑。

连通性

连通图：任意两顶点间存在路径（无向图）。
强连通图：任意两顶点双向可达（有向图）。

子图

无向图

定义： $G^{'} = (V^{'}, E^{'})$ 是 $G = (V, E)$ 的子图，当且仅当 $V^{'} \subseteq V$ 且 $E^{'} \subseteq E$ 。
若对 $H \subseteq G$ ，满足 $\forall u, v \in V^{'}$ ，只要 $(u, v) \in E$ ，均有 $(u, v) \in E^{'}$ ，则称 $H$ 是 $G$ 的 导出子图/诱导子图 (induced subgraph)。

有向图

定义： $G^{'} = (V^{'}, E^{'})$ 是 $G = (V, E)$ 的子图，当且仅当 $V^{'} \subseteq V$ 且 $E^{'} \subseteq E$ 。
若对 $H \subseteq G$ ，满足 $\forall u, v \in V^{'}$ ，只要 $u \to v \in E$ ，均有 $u \to v \in E^{'}$ ，则称 $H$ 是 $G$ 的 导出子图/诱导子图 (induced subgraph)。

连通

无向图：对于一张无向图 $G = (V, E)$ ，对于 $u, v \in V$ ，若存在一条途径使得 $v_{0} = u, v_{k} = v$ ，则称 $u$ 和 $v$ 是 连通的 (connected)。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。若一张无向图的节点两两互相连通，则称这张图是 连通的 (connected)。
有向图：对于一张有向图 $G = (V, E)$ ，对于 $u, v \in V$ ，若存在一条途径使得 $v_{0} = u, v_{k} = v$ ，则称 $u$ 可达 $v$ 。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。（无向图中的连通也可以视作双向可达。）若一张有向图的节点两两互相可达，则称这张图是 强连通的 (strongly connected)。

应用场景

社交网络：无向图表示用户对称关系。
交通导航：权重图优化最短路径（Dijkstra算法）。
状态机建模：有向图描述系统状态转移（如JK触发器制作模20计数器）。

图的存储方式

1. 邻接矩阵

实现方式：
- 二维数组 matrix[u][v] 表示顶点 $u$ 和 $v$ 的连接关系。
- 权重图：matrix[u][v] 存储权重值，无边时标记为 $0$ 或 $\infty$ 。
复杂度分析：
操作时间复杂度空间复杂度
查询边是否存在 $O (1)$ $O (V^{2})$
适用场景：稠密图（边数接近顶点数平方）。

操作	时间复杂度	空间复杂度
查询边是否存在	$O (1)$	$O (V^{2})$

2. 邻接表

实现方式：
- 每个顶点维护一个链表/数组，存储其所有邻接顶点。
- 权重图：存储邻接顶点及权重（如 (v, weight)）。
复杂度分析：
操作时间复杂度空间复杂度
遍历某顶点的邻接点 $O (d)$ （ $d$ 为度） $O (V + E)$
适用场景：稀疏图（边数远小于顶点数平方）。

操作	时间复杂度	空间复杂度
遍历某顶点的邻接点	$O (d)$ （ $d$ 为度）	$O (V + E)$

3. 存储方式对比

特性	邻接矩阵	邻接表
空间效率	低（稠密图适用）	高（稀疏图适用）
查询边效率	$O (1)$	$O (d)$
动态增删边效率	$O (1)$	$O (1)$ （链表实现）
适用算法	Floyd-Warshall	DFS/BFS

树的基本性质

1. 定义与特性

树是特殊的图：
- 连通无环的无向图。
- 数学性质： $| E | = | V | - 1$ 。
森林：由多棵树组成的非连通无环图。

2. 树的结构分类

根树（Rooted Tree）：
- 层次结构：根节点、父节点、子节点。
- 示例：文件系统目录树。
二叉树（Binary Tree）：
- 每个节点最多有两个子节点（左子节点、右子节点）。
- 特殊类型：
  - 满二叉树：所有非叶节点均有2个子节点。
  - 完全二叉树：除最后一层外，其他层节点全满。

有关树的定义

适用于无根树和有根树

森林（forest）：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林。
生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 $n - 1$ 条，将所有顶点连通。
无根树的叶结点（leaf node）：度数不超过 $1$ 的结点。（考虑 $n = 1$ 。）
有根树的叶结点（leaf node）：没有子结点的结点。

只适用于有根树

父亲（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。
根结点没有父结点。
祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。
根结点的祖先集合为空。
子结点（child node）：如果 $u$ 是 $v$ 的父亲，那么 $v$ 是 $u$ 的子结点。
子结点的顺序一般不加以区分，二叉树是一个例外。
结点的深度（depth）：到根结点的路径上的边数。
树的高度（height）：所有结点的深度的最大值。
兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
后代（descendant）：子结点和子结点的后代。或者理解成：如果 $u$ 是 $v$ 的祖先，那么 $v$ 是 $u$ 的后代。

树的遍历算法

深度优先遍历（DFS）

递归实现模板（以二叉树为例）：

PythonC++

Python

def dfs(node):  
    if node is None:  
        return  
    # 前序遍历  
    print(node.val)  
    dfs(node.left)  
    dfs(node.right)  
    # 中序：调整print位置  
    # 后序：调整print位置

C++

void dfs(TreeNode* node) {
    if (node == nullptr) return;
    // 前序遍历
    cout << node->val << endl;
    dfs(node->left);
    dfs(node->right);

    // 中序：调整print位置
    // 后序：调整print位置
}

应用场景：
- 前序：克隆树结构、序列化。
- 中序：二叉搜索树（BST）升序输出。
- 后序：释放树内存（先处理子节点）。

广度优先遍历（BFS）

队列辅助实现

PythonC++

Python

from collections import deque  
def bfs(root):  
    queue = deque([root])  
    while queue:  
        node = queue.popleft()  
        print(node.val)  
        if node.left:  
            queue.append(node.left)  
        if node.right:  
            queue.append(node.right)

C++

#include <queue>
using namespace std;

void bfs(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << endl;
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

应用场景：最短路径问题、社交网络好友推荐。

遍历结果对比

遍历方式	输出顺序（例子：根1，左2，右3）
前序	$1 \to 2 \to 3$
中序	$2 \to 1 \to 3$
后序	$2 \to 3 \to 1$
层次	$1 \to 2 \to 3$

一种新的二叉树非递归遍历方法 AtomFirst

一种新的二叉树非递归遍历方法

点击查看代码

原版导演剪辑版

cpp

#include <iostream>
#include <cstring>
using namespace std;

typedef int Status;
#define RET_OK 1
#define RET_FAIL -1

#define ORDER_MAX_LEN 3

typedef struct BiNode
{
    char val;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

typedef struct StackNode
{
    BiTree T;
    int tagIndex; // r, L, R
} StackNode;

typedef struct Stack
{
    int top;
    StackNode data[100];
} Stack;

char gInputStr[100];
int gIndex = 0;
char gTraverseOrder[20]; // rLR, LrR, LRr

void InitStack(Stack &S)
{
    S.top = 0;
}

void Push(Stack &S, BiTree T, int tagIndex)
{
    S.data[S.top].T = T;
    S.data[S.top].tagIndex = tagIndex;
    S.top++;
}

Status Pop(Stack &S, BiTree &T, int &tagIndex)
{
    if (S.top == 0)
        return RET_FAIL;
    S.top--;
    T = S.data[S.top].T;
    tagIndex = S.data[S.top].tagIndex;
    return RET_OK;
}

bool IsEmpty(Stack S)
{
    return S.top == 0;
}
void TraverseBiTree(BiTree T, char order[])
{
    Stack S;
    InitStack(S);
    BiTree p = T;
    int tagIndex;

    Push(S, p, 0);
    while (!IsEmpty(S))
    {
        Pop(S, p, tagIndex);

        if (tagIndex + 1 < ORDER_MAX_LEN)
        {
            Push(S, p, tagIndex + 1);
        }
        switch (order[tagIndex])
        {
        case 'L':
            if (p->lchild)
                Push(S, p->lchild, 0);
            break;
        case 'R':
            if (p->rchild)
                Push(S, p->rchild, 0);
            break;
        case 'r':
            cout << p->val << " ";
            break;
        default:
            cerr << "invaild order!";
            exit(-1);
        }
    }
}

BiTree CreateBiTree()
{
    BiTree T;

    if (gInputStr[gIndex] == '#')
    {
        T = NULL;
        gIndex++;
    }
    else
    {
        T = (BiTree)malloc(sizeof(BiNode));
        T->val = gInputStr[gIndex];
        gIndex++;
        T->lchild = CreateBiTree();
        T->rchild = CreateBiTree();
    }
    return T;
}

void DestroyBiTree(BiTree T)
{
    if (T)
    {
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        free(T);
    }
}

void PreOrder(BiTree T)
{
    if (T)
    {
        cout << T->val << " ";
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTree T)
{
    if (T)
    {
        InOrder(T->lchild);
        cout << T->val << " ";
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T)
{
    if (T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->val << " ";
    }
}

int main()
{
    strcpy(gInputStr, "ABD#G###CE##F##");
    gIndex = 0;
    BiTree T = CreateBiTree();

    cout << "PreOrder: ";
    cout << "\n";
    strcpy(gTraverseOrder, "rLR");
    TraverseBiTree(T, gTraverseOrder);
    cout << "\n";
    PreOrder(T);
    cout << "\n";

    cout << "InOrder: ";
    cout << "\n";
    strcpy(gTraverseOrder, "LrR");
    TraverseBiTree(T, gTraverseOrder);
    cout << "\n";
    InOrder(T);
    cout << "\n";

    cout << "PostOrder: ";
    cout << "\n";
    strcpy(gTraverseOrder, "LRr");
    TraverseBiTree(T, gTraverseOrder);
    cout << "\n";
    PostOrder(T);
    cout << "\n";

    DestroyBiTree(T);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

cpp

// https://github.com/AtomFirst/MyDataStructureHomework/blob/master/report/bitree.cpp
#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

template <typename T>
struct BiNode
{
    T elem;
    BiNode *lson, *rson;
    BiNode(const T &elem) : elem(elem), lson(nullptr), rson(nullptr) {}
};

template <typename T>
BiNode<char> *create(T &&in)
{
    char cur;
    if (not(in >> cur) or cur == '#')
    {
        return nullptr;
    }

    BiNode<char> *rt = new BiNode<char>(cur);
    rt->lson = create(forward<T>(in));
    rt->rson = create(forward<T>(in));
    return rt;
}

template <typename T>
void PreOrderTraverse(BiNode<T> *rt)
{
    cout << (rt->elem) << " "; // addr 0
    if (rt->lson)
        PreOrderTraverse(rt->lson); // addr 1
    if (rt->rson)
        PreOrderTraverse(rt->rson); // addr 2
}

template <typename T>
void Traverse(BiNode<T> *rt, const char order[])
{
    cout << "Traverse(Order: " << order << "): ";

    stack<pair<BiNode<T> *, int>> s;
    s.emplace(rt, 0);
    while (s.size())
    {
        auto [x, i] = s.top();
        s.pop();
        if (i + 1 < 3)
            s.emplace(x, i + 1);
        switch (order[i])
        {
        case 'L':
            if (x->lson)
                s.emplace(x->lson, 0);
            break;
        case 'R':
            if (x->rson)
                s.emplace(x->rson, 0);
            break;
        case 'r':
            cout << (x->elem) << " ";
            break;
        default:
            cerr << "invaild order!";
            exit(-1);
        }
    }

    cout << endl;
}

int main()
{
    BiNode<char> *rt = create(istringstream("ABD#G###CE##F##"));

    Traverse(rt, "rLR");
    Traverse(rt, "LrR");
    Traverse(rt, "LRr");

    return 0;
}

递归函数转非递归的一般方法

找到函数的所有局部变量 $S$ （包括参数）
用一个变量 PC 表示函数内应执行的下一条语句
使用栈存储 $S$ 和 PC
每次根据栈顶信息执行指令，并更新 $S$ 和 PC 及进行入栈（函数调用）和出栈（函数结束）操作

总结

关键知识点

图与树的关系：树是连通无环图，森林是多棵树。
存储方式选择：稠密图用邻接矩阵，稀疏图用邻接表。
树遍历的核心逻辑：DFS递归 / BFS队列。

思考题

如何判断图是否为树？
1. 检查是否连通（通过DFS/BFS遍历所有顶点）。
2. 验证边数是否满足 $| E | = | V | - 1$ 。

附录

扩展阅读

《算法导论》第20章：基本图算法
《一种新的二叉树非递归遍历方法》

图与树的基本概念 ​

图的基本概念 ​

定义与组成 ​

图的分类 ​

度（Degree） ​

路径与环路 ​

连通性 ​

子图 ​

无向图 ​

有向图 ​

连通 ​

应用场景 ​

图的存储方式 ​

1. 邻接矩阵 ​

2. 邻接表 ​

3. 存储方式对比 ​

树的基本性质 ​

1. 定义与特性 ​

2. 树的结构分类 ​

有关树的定义 ​

适用于无根树和有根树 ​

只适用于有根树 ​

树的遍历算法 ​

深度优先遍历（DFS） ​

广度优先遍历（BFS） ​

遍历结果对比 ​

一种新的二叉树非递归遍历方法 AtomFirst ​

递归函数转非递归的一般方法 ​

总结 ​

关键知识点 ​

思考题 ​

附录 ​

扩展阅读 ​