文档介绍：精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
简答题
链表：链表就是一串存储数据的点个数为vi的入度。
邻接矩阵（有向、无向）
1．图的邻接矩阵表示法
在图的邻接矩阵表示法中：
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
2．图的邻接矩阵(Adacency Matrix)
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。
广度优先遍历
广度优先遍历是连通图的一种遍历策略。其基本思想如下：
1、从图中某个顶点V0出发，并访问此顶点；
2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
3、重复步骤2，直到全部顶点都被访问为止。
例如下图中：
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
，首先找到0的关联顶点3,4
，找到1，2；由4出发，找到1，但是1已经遍历过，所以忽略。
，没有关联顶点；由2出发，没有关联顶点。
所以最后顺序是0,3,4,1,2
深度优先遍历
深度优先遍历是连通图的一种遍历策略。其基本思想如下：
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。
例如下图中：
，首先找到0的关联顶点3
，找到1；由1出发，没有关联的顶点。
，从3出发，找到2；由2出发，没有关联的顶点。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
，出4出发，找到1，因为1已经被访问过了，所以不访问。
所以最后顺序是0,3,1,2,4
⑤Prim算法
基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：
在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。
Prim算法的核心:始终保持TE中的边集构成一棵生成树。
注意：prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
⑥Krusal算法
图中先将每个顶点看作独立的子图，然后查找最小权值边，这条边是有限制条件的，边得两个顶点必须不在同一个图中，如上图，第一个图中找到最小权值边为（v1，v3），且满足限制条件，继续查找到边（v4，v6），（v2，v5），（v3，v6），当查找到最后一条边时，仅仅只有（v2，v3）满足限制条件，其他的如（v3，v4），（v1，v4）都在一个子图里面，不满足条件，至此已经找到最小生成树的所有边。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
⑦拓扑排序
由某个集合上的一个偏