发布时间 : 星期六 文章数据结构历年考研试题第7章图更新完毕开始阅读42800ff34693daef5ef73d2e
void enqueue (vertype Q[] ,v) //顶点v入队列Ｑ。 vertype delqueue (vertype Q[]) //出队操作。 int empty (Q) //判断队列是否为空的函数，若空返回１，否则返回０。
vertype firstadj(graph g ,vertype v)//图g中v的第一个邻接点。
vertype nextadj(graph g ,vertype v ,vertype w)//图g中顶点v的邻接点中在w后的邻接点
void bfs (graph g ,vertype v0)
//利用上面定义的图的抽象数据类型，从顶点v0出发广度优先遍历图g。 {visit(v0);
visited[v0]=1; //设顶点信息就是编号，visited是全局变量。 initqueue(Q); enqueue(Q,v0); //v0入队列。 while (!empty(Q))
{v=delqueue(Q); //队头元素出队列。
w=firstadj(g ,v); //求顶点v的第一邻接点 while (w!=0) //w!=0表示w存在。
{if (visited[w]==0) //若邻接点未访问。
{visit(w); visited[w]=1; enqueue(Q,w);}//if w=nextadj(g,v,w); //求下一个邻接点。 }//while }//while }//bfs
void Traver()
//对图g进行宽度优先遍历，图g是全局变量。 {for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++)
if (visited[i]==0) bfs(i); } //Traver
25.[题目分析] 本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用num记录访问顶点个数，当num等于图的顶点个数（题中的NODES(G)），输出所访问的顶点序列，顶点序列存在path中，path和visited数组，顶点计数器num，均是全局变量，都已初始化。 void SPathdfs(v0)
//判断无向图Ｇ中是否存在以v0为起点，包含图中全部顶点的简单路径。 {visited[v0]=1; path[++num]=v0;
if (num==nodes(G) //有一条简单路径，输出之。
{for (i=1;i<=num;i++) printf( \//if
p=g[v0].firstarc; while (p)
{if (visited[p->adjvex]==0) SPathdfs(p->adjvex); //深度优先遍历。 p=p->next; //下一个邻接点。 }//while
visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。 }//SPathdfs
26. 与上题类似，这里给出非递归算法，顶点信息仍是编号。
void AllSPdfs(AdjList g,vertype u,vertype v)
//求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v) { int top=0,s[];
s[++top]=u; visited[u]=1; while (top>0 || p)
{p=g[s[top]].firstarc; //第一个邻接点。
while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。
if (p==null) top--; //退栈。
else { i=p->adjvex; //取邻接点（编号）。
if (i==v) //找到从u到v的一条简单路径，输出。 {for (k=1;k<=top;k++) printf( \printf( \if
else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else }//while }// AllSPdfs
类似本题的另外叙述的第（2）题 ：u到v有三条简单路径：uabfv，ucdv，ucdefv。 27. （1）[题目分析]D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0)
// 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。
{ int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for (i=1,i<=n;i++) visited[i]=0; //图有n个顶点，visited数组为全局变量。 for (i=1,i<=n;i++) //对n个顶点的图g进行D_搜索。 if (visited[i]==0)
{s[++top]=i; visited[i]=1; printf( \ while (top>0)
{i=s[top--]; //退栈
p=g[i].firstarc; //取第一个邻接点
while (p!=null) //处理顶点的所有邻接点 {j=p->adjvex;
if (visited[j]==0) //未访问的邻接点访问并入栈。 {visited[j]=1; printf( \p=p->next;
1 } //下一个邻接点
}//while(top>0) 2 3 4 } //if 7 }//D_BFS
（2）D_搜索序列：1234675，生成树如图： 5
28，[题目分析] 本题的含义是对有向无环图(DAG)的顶点，以整数适当编号后，可使其邻接矩阵中对角线以下元素全部为零。根据这一要求，可以按各顶点出度大小排序，使出度最大的顶点编号为1，出度次大者编号为2，出度为零的顶点编号为n。这样编号后，可能出现