0802-1
定义无向网络
An undirected net is a tuple G = ( V , w ) G = (\mathbf{V}, w) G=(V,w), where V \mathbf{V} V is the set of nodes, and w : V × V → R w:\mathbf{V} \times \mathbf{V} \to \mathbb{R} w:V×V→R is the weight function where w ( v i , v j ) w(v_i,v_j) w(vi,vj) is the weight of arc ⟨ v i , v j ⟩ \langle v_i,v_j \rangle ⟨vi,vj⟩and ⟨ v j , v i ⟩ \langle v_j,v_i \rangle ⟨vj,vi⟩.
0802-2
自己画一棵树, 将其元组各部分写出来 (特别是函数 p p p).
T
=
(
V
,
r
,
p
)
T=(\mathbf{V},r,p)
T=(V,r,p).
V
=
{
v
1
,
v
2
,
v
3
,
v
4
,
v
5
,
v
6
}
\mathbf{V}=\{v_1,v_2,v_3,v_4,v_5,v_6\}
V={v1,v2,v3,v4,v5,v6}.
r
=
v
1
r=v_1
r=v1.
p
:
V
→
V
∪
{
ϕ
}
p:\mathbf{V} \rightarrow \mathbf{V} \cup \{\phi\}
p:V→V∪{ϕ} is the parent mapping satisfying
- p ( r ) = ϕ p(r)=\phi p(r)=ϕ;
- ∀ v ∈ V , ∃ 1 n ≥ 0 , s t . p ( n ) ( v ) = r \forall v \in \mathbf{V}, \exist 1 n \ge 0, st. p^{(n)}(v) = r ∀v∈V,∃1n≥0,st.p(n)(v)=r.
针对该树, 将代码中的变量值写出来 (特别是parent数组).
public class Tree {
/**
* 节点数. 表示节点 v_0 至 v_{n-1}.
*/
int n;
/**
* 根节点. 0 至 n-1.
*/
int root;
/**
* 父节点.
*/
int[] parent;
/**
* 构造一棵树, 第一个节点为根节点, 其余节点均为其直接子节点, 也均为叶节点.
*/
public Tree(int paraN) {
n = paraN;
parent = new int[n];
parent[0] = -1; // -1 即 \phi
}// Of the constructor
}//Of class Tree
- n=6;
- root=1;
- parent[ ]= { − 1 , 0 , 1 , 1 , 1 , 2 , 4 } \{-1,0,1,1,1,2,4\} {−1,0,1,1,1,2,4}.
0802-3
画一棵三叉树, 并写出它的 child 数组.
以上图为例.
child[ ][ ]=
{
{
2
,
3
,
4
}
,
{
5
,
−
1
,
−
1
}
,
{
−
1
,
−
1
,
−
1
}
,
{
6
,
−
1
,
−
1
}
,
{
−
1
,
−
1
,
−
1
}
,
{
−
1
,
−
1
,
−
1
}
}
\{\{2,3,4\},\{5,-1,-1\},\{-1,-1,-1\},\{6,-1,-1\},\{-1,-1,-1\},\{-1,-1,-1\}\}
{{2,3,4},{5,−1,−1},{−1,−1,−1},{6,−1,−1},{−1,−1,−1},{−1,−1,−1}}.
按照本贴风格, 重新定义树. 提示: 还是应该定义 parent 函数, 字母表里面只有一个元素.
tree is a quadruple
T
=
(
Σ
,
V
,
r
,
f
)
T=(\Sigma, \bm{V}, r, f)
T=(Σ,V,r,f), where
a)
Σ
=
{
1
}
\Sigma=\{1\}
Σ={1} is the alphabet;
b)
V
=
{
v
1
,
…
,
v
n
}
\bm{V}=\{v_1,\ldots,v_n\}
V={v1,…,vn} is the set of nodes;
c)
r
∈
V
r \in \bm{V}
r∈V is the root node;
d)
ϕ
\phi
ϕ is the empty node;
e) f :
V
×
Σ
∗
→
V
∪
{
ϕ
}
\bm{V} \times \Sigma^* \to \bm{V}\cup\{\phi\}
V×Σ∗→V∪{ϕ} satisfying
- ∀ v ∈ V , ∃ 1 s ∈ Σ ∗ s t . f ( v , s ) = r \forall v\in\bm{V},\exists1 \,s∈\Sigma^∗ \,st. f ( v , s ) = r ∀v∈V,∃1s∈Σ∗st.f(v,s)=r.
- f ( r , s ) = ϕ f(r,s)=\phi f(r,s)=ϕ
根据图、树、m mm-叉树的学习, 谈谈你对元组的理解.
- 元组可以是包含多种数据结构，甚至还可以是集合或者是函数．
- 元组是可以重复的．
- 成员不可直接修改．