父节点数组表示法:
1.树中的节点数字化为他们的编号1,2......n
2.用一个一维数组存储每个节点的父结点,即:father[k]中是存放结点的编号
3.由于树中每个结点的父结点是唯一的,所以父结点数组表示法可以唯一表示任何一棵树
优点:可以快速查找某个节点的父节点
缺点:查找子节点需要遍历整个数组,靠父节点的值跟数组元素比较,相同值的下标即为该节点的子节点
儿子链表表示法:
把每个孩子节点排列起来,看成是一个线性表,且以单链表作为存储结构,则n个节点又那个孩子链表,而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构
如果要查找父节点,可以在数组中添加一个parent域,用来存储每个节点的父节点对应数组下标
堆:
使用数组a[i]存储编号为i的节点值
堆的根为a[1],并且利用完全二叉树的性质,父节点parent(i)的下标为i/2,左孩子节点left(i)的下标为2i,有孩子节点right(i)的下标为2i+1
除根以外的每个节点,a[parent(i)]>=a[i]。即除根节点外,所有结点的值都不得超过其父节点的值,堆中的最大元素存放在根节点中,且每一结点的子树都小于等于该结点的值,这种堆叫做“大根堆”;反之,对除根结点的每个节点,a[parent(i)]<=a[i]的堆叫做“小根堆”
void ma(int x,int y){
int fx=get(x),fy=get(y);
if(fx!=fy){
if(ranks[fx]>ranks[fy])f[fy][fx];
else{
f[fx]=fy;
if(ranks[fx]==ranks[fy])ranks[fy]++;
}
}
}
生成树满足的条件:
1.任意两点之间有且只有一条边
2.包含连通图中所有点,n-1条边联通这所有顶点
最小生成树:
对于带权的连通图,权值最小的生成树,就叫生成树
从n个不同元素中取m个元素,按照一定的顺序排成一列,叫做从n个不同元素中取m个元素的一个排列,这样的全部排列个数,叫做排列数,叫做:“AnmA^m_nAnm ”