内容发布更新时间 : 2024/6/4 1:33:59星期一 下面是文章的全部内容请认真阅读。

性能分析：在建立邻接表函数create_AdjListGraph()中，在输入房间的个数后，对各个房间的信息进行初始化的时间性能为O(n)，输入门的信息后，对开门的方向存入各个结点中，其时间性能为O(e)，最后又将表头结点中一维数组的值一一赋给了定义的一个邻接表类型的变量alg中的一维数组vextices[i]，其时间性能为O(n)，故总的时间性能为O(2n+e)。

在深度优先搜索遍历函数中，采用了递归的方法，而每一个房间都要调用n次深度优先搜索遍历函数，故n个房间在深度优先搜索中的时间性能为O(n2)。

用户使用说明

1. 房间数目最多为100个，所以在输入房间数目时应输入少于100的整数。

2. 输入开门的方向时，如果门是从001号房间开向012号房间，则输入001 012，两

个房间之间用空格分开，不能用逗号或其他符号，并且房间也要输入整数，前面0可以写也可以不写。

3. 当输入结束后，均以回车键结束。

参考文献

[1] 王昆仑，红. 数据结构与算法. ：中国铁道，2011.

附录（完整源程序）

#include #include

#define MAX_VERTEX_NUM 100 int flag=1; int num;

int visited[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //visited二维数组用于

判断每个房间是否都被访问过

typedef struct Arcnode{ //邻接表中结点结构类型的定义 int adjvex; Arcnode *nextarc; }Arcnode;

typedef struct{ //邻接表表头结点结构类型的定义 int vexdata; Arcnode *firstarc; //指向第一个邻接点 }Vexnode;

typedef struct{ //邻接表类型的定义 Vexnode vextices[MAX_VERTEX_NUM];

int vexnum,arcnum; //vexnum记录房间的个数，arcnum记录门的个数 }ALGraph;

ALGraph create_AdjListGraph(){ //建立邻接表函数，将房间和门存入邻接表中 int i,j,k,n,e; Arcnode *p; Vexnode al[MAX_VERTEX_NUM]; printf(\请输入房间的数目：\ scanf(\ for(i=1;i<=n;i++){ //初始化表头结点数组 al[i].vexdata=i; al[i].firstarc=NULL; }

}

void DFS(ALGraph alg,int i){ //深度优先搜索遍历函数 visited[num][i]=1; Arcnode *p=alg.vextices[i].firstarc; while(p!=NULL){ if(visited[num][p->adjvex]==0) DFS(alg,p->adjvex); p=p->nextarc; } }

void DFS_trave(ALGraph alg){ int i,j; for(i=1;i<=alg.vexnum;i++) for(j=1;j<=alg.vexnum;j++) visited[i][j]=0; //初始化访问数组，即让每一个结点都未被访问过 for(num=1;num<=alg.vexnum;num++) DFS(alg,num); for(i=1;i<=alg.vexnum;i++) for(j=1;j<=alg.vexnum;j++) if(visited[i][j]==0){ flag=0; break; } if(flag==1)

printf(\请输入门的数目：\

scanf(\

printf(\请再输入开门的方向(比如门从号房间开向号房间，那么就输入010)：\\n\for(i=0;iadjvex=k; p->nextarc=al[j].firstarc; al[j].firstarc=p; }

ALGraph alg; for(i=1;i<=n;i++) alg.vextices[i]=al[i]; //将al数组中的房间号依次存储在邻接表表头

结点 的一维数组vextices中

alg.vexnum=n; alg.arcnum=e; return alg;

printf(\任意两个房间都可以互相相通！\ else printf(\任意两个房间都不可以相通！\}

void main(){ //主函数 ALGraph Alg; Alg=create_AdjListGraph(); DFS_trave(Alg); }