算法与数据结构复习

(1)存储结构定义

顶点结构

vexdata firstin 表结点结构 (2) 算法设计

adjvex info firstarc int toposort (ALGraph G,int tpv[]){ //以逆邻接表为存储结构的有向图的拓扑排序

top=0;

for(i=0;i

findoutdegree(G,outdegree); // 对各顶点求出度

outdegree[p→adjvex]++; InitStack(&S); //初始化栈 for(i=0;i

if(outdegree[i]==0) Push(&S,i); //出度为零的顶点入栈 while(!Stack(S)){

Pop(&S,i);printf(G.adjlist[i].vextex); tpv[top++]=i;

for(p=G.adjlist[i].firstedge;p;p→next){

j=p→adjvex; outdegree[j]--; if(!outdegree[j]) Push(&S,j);

//出度为零的顶点入栈 }//for }//while

if(top

for(i=0;j=top-1;i< G.vexnum/2;i++,j--){//置逆输出 temp=tpv[i];tpv[i]=tpv[j];tpv[j]=temp;

}//for return 1;

}//else }//toposort

10. 设计算法，判断一个以邻接表为存储结构的无向图G是否连通有，若连通，则返回1，否则，返回0。int connect(ALGraph G){ //判断以邻接表为存储结构的无向图是否连通

flag=1;

for(i=0;i

if(visited[i]=0){ flag==0; breek; } return flag;

}// connect

void dfs(ALGraph G,int visited[],int v){ //采用深度优先遍历的算法思想 visited[v]=1;

p=G.ver[v].firstarc; while(p){

if(visited[p→adjvex]==0) dfs(G,visited,p→adjvex);

p=p→next; }//whike

}//dfs

17

18