1.图的部分
1.连通，连通分量，强连通
2.图的存储方式
2.1邻接矩阵法
2.2邻接表，节点用顺序存。链表用链式去存，有哪些特点
2.3十字链表，有向图，为什么叫十字链表，因为节点了里存储了相关的两条边，边里存储了前后节点人
2.4邻接所重表，无向图，点存点的信息和依附于点的下一条边，边存依附的两个点和依附的两个点的吓一跳边。
2.图的遍历
BFS:先访问v1，再访问v1的的邻接节点，借用辅助数组，最短路径，依次遍历每个节点
DFS。空间复杂度，ov。时间复杂度ov的平方。
3.最短路劲
dj算法，初始dist（从开始节点到目标节点的距离，比如目标点是A，则dist[A]=0，与dist相邻的点初始化成距离。2.寻找dist边最小并未被访问的节点。标记为访问，更新dist，反复，直到没有这样的节点）
2.最小生成树
prime算法，边找点，初始化一个dist集初始化一个遍及和，dist代表边集合的最短距离，开始找邻接的未被收录节点的最小边，把该节点加入边集合。知道vt==v了n-1条边。
kruskal 算法：由边到点。把每个节点初始化一个一个节点的僧林，然后找链接最小的边。判断是否构成回路，是，舍弃，不是，不奢求。
5.拓扑排序：
1.Dag图：无环图
2.若有向dag图表示一个工程，vi，vj表示要执行vj必须先执行vi。则该图叫做AOV网。
1.拓扑排序获得方法，找到一个无前驱节点，拿出，按这个方法。一直走下去
二、树的部分
1.高度又称深度，第一层为1
性质：
节点数等于总度数+1；
非空树：no=n2+1;
2.二叉树的遍历：
线序
中序
后续
层序
3.线索二叉树
n个节点，有n+1个空指针。用那些空指针存储前驱或后继，有一个ltag，rtag。若左指数为空，左前驱，右后继。
线索二叉树的构造
用中序遍历，用一个指针pre表示先前访问的节点。
4.线索二叉树的遍历
2.二叉排序树。
、1.查找
2.构造
3.插入
5.平衡二叉树
建立：
在以A为根节点的树，在A的左子树的左子树插入影响了平衡。
网友评论