第四次上机实验程序

1、第四次上机实验一、 上机实习题目建立一个 n=30 的无向图，用临接表表示结点关系，从图的每个结点进行深度优先遍历二、相关知识或技术熟悉图的结构以及图的邻接表表示，同时对于深度优先遍历的方法需要了解并加以使用。三、算法及数据结构设计（算法设计）1.从顶点 v 出发图的深度优先遍历算法（1）（2）首先图中某个顶点找出与定点v 邻接的第一个未被顶点重复操作的w，对该顶点进行，再以w 为（3）当某个顶点的所有邻接顶点都未被放过时，就从这个点返回未被点，直到某邻接顶点中有未被过的顶点，执行（2）的顶2. 算法时间复杂度分析图用邻接表表示，假定有 n 个顶点，e 条边，对于邻接表的为各节点至多一次，无向

2、图时，有 2e 个链表结点和n 个表头结点，时间复杂度 O（n+2e）=O(n+e),又确定某结点所用时间复杂度O（n），故完成搜索所需时间复杂度 O(n2)四、上机环境和使用语言（计算机程序实现）上机环境：VC 6.0使用语言： C程序设计：#define maxnode 40#define null 0 #include #include typedef struct st_arcadjvex; weight;struct st_arc *nextarc;ode;typedef structvertex; struct st_arc *vernode;arc;typedef vernode

3、 adjlistmaxnode;void trave(adjlist g,n,k)i,j,visitedmaxnode;void dfs(adjlist g, for(i=0;in;i+)visitedi=0; for(j=k;jn;j+)for(i=j;in;i+) if(visitedi=0)k,visited);dfs(g,i,visited); for(i=0;iadjvex; if(visitedw=0)dfs(g,w,visited); p=p-nextarc;void main()i,j,n,k,v; ode *p,*q;adjlist g;prf(请输入结点数：);scanf(

4、%d,&n); for(k=0;kadjvex=j;q-nextarc=gi.arc;gi. p=(arc=q; ode*)malloc(sizeof(ode);p-adjvex=i;p-nextarc=gj.arc;gj.arc=p;prf(dfs:);for(v=0;v16-7-2-8-6-11-22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-dfs:2-8-7-1-16-6-11-22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4

5、-dfs:3-4-9-13-18-23-28-29-30-25-20-19-15-14-24-22-21-26-27-17-12-11-6-1-16-7-2-8-5-10-dfs:4-3-9-13-18-23-28-29-30-25-20-19-15-14-24-22-21-26-27-17-12-11-6-1-16-7-2-8-5-10-dfs:5-10-9-13-18-23-28-29-30-25-20-19-15-14-24-22-21-26-27-17-12-11-6-1-16-7-2-8-3-4-dfs:6-11-22-21-26-27-17-12-18-23-28-29-30-25

6、-20-19-15-14-24-13-9-5-10-3-4-1-16-7-2-8-dfs:7-2-8-1-16-6-11-22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-dfs:8-2-7-1-16-6-11-22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-dfs:9-13-18-23-28-29-30-25-20-19-15-14-24-22-21-26-27-17-12-11-6-1-16-7-2-8-5-10-3-4-dfs:

7、10-5-9-13-18-23-28-29-30-25-20-19-15-14-24-22-21-26-27-17-12-11-6-1-16-7-2-8-3-4-dfs:11-22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-6-1-16-7-2-8-dfs:12-17-27-26-21-22-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-11-6-1-16-7-2-8-dfs:13-18-23-28-29-30-25-20-19-15-14-24-22-21-26-

8、27-17-12-9-5-10-3-4-11-6-1-16-7-2-8-dfs:14-15-19-20-25-30-29-28-23-18-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-24-dfs:15-19-20-25-30-29-28-23-18-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-24-14-dfs:16-1-7-2-8-6-11-22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-dfs:17-27

9、-26-21-22-18-23-28-29-30-25-20-19-15-14-24-13-9-12-5-10-3-4-11-6-1-16-7-2-8-dfs:18-23-28-29-30-25-20-19-15-14-24-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-dfs:19-20-25-30-29-28-23-18-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-15-14-24-dfs:20-25-30-29-28-23-18-22-21-26-27-17-12-9-13-5-10-3

10、-4-11-6-1-16-7-2-8-15-19-14-24-dfs:21-22-18-23-28-29-30-25-20-19-15-14-24-13-9-12-17-27-26-5-10-3-4-11-6-1-16-7-2-8-dfs:22-21-26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-13-9-5-10-3-4-11-6-1-16-7-2-8-dfs:23-28-29-30-25-20-19-15-18-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-14-24-dfs:24-29-30-2

11、5-20-19-15-18-23-28-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-14-dfs:25-30-29-28-23-18-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-15-19-20-14-24-dfs:26-27-17-12-18-23-28-29-30-25-20-19-15-14-24-22-21-11-6-1-16-7-2-8-13-9-5-10-3-4-dfs:27-26-21-22-18-23-28-29-30-25-20-19-15-14-24-13-9-12-17-5-10-3-4-11-6-1-16-7-2-8-dfs:28-29-30-25-20-19-15-18-23-22-21-26-27-17-12-9-13-5-10-3-4-11-6-1-16-7-2-8-14-24-dfs:29-30-25-20