DFS (g, i): F 采用广度优先搜索遍历非连通无向图的算法如下 BFSI(ALGraph *g) for(i=0: i<g->n:i+) f (visited[i==0) FS(g, i): F 【例7.1】试以邻接表为存储结构,分别写出基于DFS和BPS遍历的算法来判别顶点i和顶点j(i≠j之间是 否有路径 解:先置全局变量 visited为0,然后从顶点i开始进行某种遍历,遍历之后,若 visited[j=0,说 明顶点i与顶点j之间没有路径:否则说明它们之间存在路径 基于DFS遍历的算法如下 int visited [MaxVertexNuml nt DFSTrave (aLgraph *G, int i, int j) int k for (k=0: k<G->n: k++) visited[k]=0 DFSG,i)://从顶点i开始进行深度优先遍历 if (visited]==0) return 0 else return I 基于BFS遍历的算法如下: int visited[MaxVertexNum int DFSTrave(ALGraph *G, int i, int j) for(k=0: k<G->n: k++) ted[k]=o BFSG,i);/从顶点i开始进行广度优先遍历 if (visited[j]==0) return 0 else return 1: I 4.最小生成树 (1)普里姆算法过程 不要求编写算法。 (2)克鲁斯卡尔算法过程不要求编写算法。 5.最短路径 (1)狄克斯特拉算法过程 不要求掌握算法。 (2)弗洛伊德算法过程 不要求掌握算法。 拓扑排序和关键路径不作考试内容。 第9章查找 1.线性表的查找在顺序表上进行 (1)顺序查找(过程和算法) (2)二分查找(过程和算法) (3)分块查找(只需过程) 2.树表的查找二叉排序树 (1)定义 (2)查找(过程和算法) (3)插入和删除(过程) 3.哈希表查找 (1)哈希函数(除留余数法) (2)哈希冲突解决方法(线性探查法) 第10章内排序 各种排序方法的过程和算法设计 排序和文件部分不作要求DFS(g,i); } 采用广度优先搜索遍历非连通无向图的算法如下： BFS1(ALGraph *g) { int i; for (i=0;i<g->n;i+) if (visited[i]==0) BFS(g,i); } 【例 7.1】 试以邻接表为存储结构，分别写出基于 DFS 和 BPS 遍历的算法来判别顶点 i 和顶点 j(i≠j)之间是 否有路径。 解：先置全局变量 visited[]为 0，然后从顶点 i 开始进行某种遍历，遍历之后，若 visited[j]=0，说 明顶点 i 与顶点 j 之间没有路径；否则说明它们之间存在路径。 基于 DFS 遍历的算法如下： int visited[MaxVertexNum]; int DFSTrave(ALGraph *G，int i，int j) { int k; for (k=0;k<G->n;k++) visited[k]=0; DFS(G，i); //从顶点 i 开始进行深度优先遍历 if (visited[j]==0) return 0; else return 1; } 基于 BFS 遍历的算法如下： int visited[MaxVertexNum]; int DFSTrave(ALGraph *G，int i，int j) { int k; for (k=0;k<G->n;k++) visited[k]=0; BFS(G，i); //从顶点 i 开始进行广度优先遍历 if (visited[j]==0) return 0; else return 1; } 4.最小生成树 （1）普里姆算法过程 不要求编写算法。 （2）克鲁斯卡尔算法过程 不要求编写算法。 5.最短路径 （1）狄克斯特拉算法过程 不要求掌握算法。 （2）弗洛伊德算法过程 不要求掌握算法。 拓扑排序和关键路径不作考试内容。 第 9 章 查找 1.线性表的查找 在顺序表上进行。 （1）顺序查找 （过程和算法） （2）二分查找 （过程和算法） （3）分块查找 (只需过程) 2. 树表的查找 二叉排序树 （1）定义 （2）查找（过程和算法） （3）插入和删除（过程） 3.哈希表查找 （1） 哈希函数（除留余数法 ） （2） 哈希冲突解决方法 （线性探查法 ） 第 10 章 内 排 序 各种排序方法的过程和算法设计。 外排序和文件部分不作要求