写一个算法 确定有n个顶点的无向图是否包含回路。此算法的时间代价应该是O（n)。

正确答案：(1)数据结构 采用9．1．3节中无向图的邻接表表示法。 (2)思路 由图论的知识可知对于一个有n个顶点的无向图如果它的边数m大于等于n那么此图必然包含回路。 算法犬体分两步：①先顺序搜索一遍边表统计边的个数一旦发现n条边直接返回“是”即可。②算法执行到此说明边数m一定小于顶点数n。执行is_loop算法类似的算法来判断此无向图中是否包含回路。 对于任意一个有n个顶点m条边的无向图当m≥n时算法只执行第1步时间代价为O(n)；当m＜n时算法执行第1步的时间代价为O(m)执行第i步的时间代价为O(m+n)总的时间代价为O(m+n)。注意到m＜n因此时间代价仍为O(n)。综上所述该算法的时间代价为O(n)。 (3)算法 int is_loop_2(GraphList*pgraph){ ／*判断一个无向图是否包含回路。是返回1；否则返回0*／ EdgeList p； int m=0ijknodeno=0top=-l； int degree[MAXVEX]； int flag[MAXVEX]； ／*用来记录每个顶点是否入过栈。flag[i]等于1表示第i个顶点入过栈等于0表示该顶点未入过栈*／ for(i=0；i＜pgraph-＞n；i++){ ／*统计边的个数一旦发现n条边返回1*／ p=pgraph-＞vexs[i]．edgelist； while(p!=NULL){ m++； if(m＞=2*pgraph-＞n) return 1； if(p!=NULL){ p=p-＞nextedge； } } } for(i=0；i＜pgraph-＞n；i++){ degree[i]=0； flag[i]=O； } for(i=0；i＜pgraph-＞n；i++){ ／*计算图中所有顶点的度结果放入数组degree中*／ p=pgraph-＞vexs[i]．edgelist； while(p!=NULL){ degree[p-＞endvex]++； p=p-＞nextedge； } } for(i=0；i＜pgraph-＞n；i++) ／*将度为01的顶点入栈*／ if(degree[i]＜=1){ degree[i]=top； flag[i]=1； top=i； } while(top!=-1){ j=top； ／*取出栈顶元素*／ top=degree[top]； ／*出栈*／ nodeno++； p=pgraph-＞vexs[j]．edgelist； while(p!=NULL){ ／*删除以该顶点为端点的边*／ k=p-＞endvex； if(flag[k]!=1){ ／*若第k个顶点未入过栈*／ degree[k]--； if(degree[k]==1){ ／*将新的度为1的顶点入栈*／ degree[k]=top； flag[k]=1； top=k； } } p=p-＞nextedge； } } if(nodeno＜pgraph-＞n) return 1； ／*存在回路*／ return 0； } (4)代价分析 该算法的时间复杂度为O(n)。
(1)数据结构采用9．1．3节中无向图的邻接表表示法。(2)思路由图论的知识可知,对于一个有n个顶点的无向图,如果它的边数m大于等于n,那么此图必然包含回路。算法犬体分两步：①先顺序搜索一遍边表,统计边的个数,一旦发现n条边,直接返回“是”即可。②算法执行到此,说明边数m一定小于顶点数n。执行,is_loop算法类似的算法来判断此无向图中是否包含回路。对于任意一个有n个顶点m条边的无向图,当m≥n时,算法只执行第1步,时间代价为O(n)；当m＜n时,算法执行第1步的时间代价为O(m),执行第i步的时间代价为O(m+n),总的时间代价为O(m+n)。注意到m＜n,因此时间代价仍为O(n)。综上所述,该算法的时间代价为O(n)。(3)算法intis_loop_2(GraphList*pgraph){／*判断一个无向图是否包含回路。是,返回1；否则,返回0*／EdgeListp；intm=0,i,j,k,nodeno=0,top=-l；intdegree[MAXVEX]；intflag[MAXVEX]；／*用来记录每个顶点是否入过栈。flag[i]等于1表示第i个顶点入过栈,等于0表示该顶点未入过栈*／for(i=0；i＜pgraph-＞n；i++){／*统计边的个数,一旦发现n条边,返回1*／p=pgraph-＞vexs[i]．edgelist；while(p!=NULL){m++；if(m＞=2*pgraph-＞n)return1；if(p!=NULL){p=p-＞nextedge；}}}for(i=0；i＜pgraph-＞n；i++){degree[i]=0；flag[i]=O；}for(i=0；i＜pgraph-＞n；i++){／*计算图中所有顶点的度,结果放入数组degree中*／p=pgraph-＞vexs[i]．edgelist；while(p!=NULL){degree[p-＞endvex]++；p=p-＞nextedge；}}for(i=0；i＜pgraph-＞n；i++)／*将度为0,1的顶点入栈*／if(degree[i]＜=1){degree[i]=top；flag[i]=1；top=i；}while(top!=-1){j=top；／*取出栈顶元素*／top=degree[top]；／*出栈*／nodeno++；p=pgraph-＞vexs[j]．edgelist；while(p!=NULL){／*删除以该顶点为端点的边*／k=p-＞endvex；if(flag[k]!=1){／*若第k个顶点未入过栈*／degree[k]--；if(degree[k]==1){／*将新的度为1的顶点入栈*／degree[k]=top；flag[k]=1；top=k；}}p=p-＞nextedge；}}if(nodeno＜pgraph-＞n)return1；／*存在回路*／return0；}(4)代价分析该算法的时间复杂度为O(n)。