解：本题的算法思想是：利用深度优先搜索遍历,设栈(stack)保存遍历路径上的顶点，并以d记下当前的路径长度。从V=Vi出发，找V的邻接顶点W，若W已访问过，则找下一个邻接顶点；W=Vj，且d=L-1,则路径即为所求；若W<>j，且d<L-1,则从W出发继续遍历，否则找下一个邻接顶点，若找不到下一个邻接顶点(设W=0),则退栈，找前一顶点的下一个邻接顶点，若栈空，则说明没有这样的路径。
因此，实现本题功能的函数如下：
#define MAXVEX 100
void path(adj,i,j,L)
int I,j,L
{
int v,w,top=0,d=0,head;
int stack[MAXVEX],visited[MAXVEX];
struct vexnode *p;
v=Vi;
visited[Vi]=1; head=1;
do
{
if (head) p=adj[v]->link;
else {
head=0;
p=p->next;
}
if (p= =Null) w=0;
else w=p->adjvex;
if (w!=0)
if (visited[w]= =0)
if (w= = Vi && d==L-1)
{
d++;
top++;
stack[top]=v;
}
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}
}while ((top!=0)| | w==0)&&(d!=1))
if (top>0)
for(I=1;I<top;I++)
printf(“%d”,stack[i]);
else printf(‘没有这样的路径!’);
}
11 个解决方案
#1
程序有错误，没有head=0的赋值。虽然条件语句里有，但head永远不会＝0。除此之外之外，思路很清晰。不知你哪里有疑问？
#2
确实head没有赋0，我也看了半天。但书上确实是这么写的，我想不出在哪里赋head为0。
从V=Vi出发，找V的邻接顶点W，若W已访问过，则找下一个邻接顶点；
这里找下一个顶点是怎么实现的。谢谢!
从V=Vi出发，找V的邻接顶点W，若W已访问过，则找下一个邻接顶点；
这里找下一个顶点是怎么实现的。谢谢!
#3
head＝0的赋值大概在
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=0; /*不是＝1 */
top--;
d--;
}
此时p=null,所以出栈，置head=0，表明取邻接表的下一个顶点。
此程序是深度优先遍历。先从vi开始遍历每个连表的表头的adj[v]->link顶点,如果为空,出栈取前一个顶点的下一个邻接顶点p->next.如果你把邻接表的结构搞清楚了就明白了.邻接表的结构是这样的.
adj[0]->link(指向v1)--v1->next(指向v2)--v2->next--null
adj[1]->link--v3->next--v4->next--null
adj[2]->link=null
....
adj[4]-link=null.
如果还又疑问,请指明.
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=0; /*不是＝1 */
top--;
d--;
}
此时p=null,所以出栈，置head=0，表明取邻接表的下一个顶点。
此程序是深度优先遍历。先从vi开始遍历每个连表的表头的adj[v]->link顶点,如果为空,出栈取前一个顶点的下一个邻接顶点p->next.如果你把邻接表的结构搞清楚了就明白了.邻接表的结构是这样的.
adj[0]->link(指向v1)--v1->next(指向v2)--v2->next--null
adj[1]->link--v3->next--v4->next--null
adj[2]->link=null
....
adj[4]-link=null.
如果还又疑问,请指明.
#4
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
这个地方不管W是不是访问过或为0都进栈？
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
这个地方不管W是不是访问过或为0都进栈？
#5
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}而且这里退栈的时候，返回去p=p->next应该不会是下一个邻接顶点。
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}而且这里退栈的时候，返回去p=p->next应该不会是下一个邻接顶点。
#6
w不管是不是访问都近栈，w=0因该不近栈，如果近栈，当w出栈时哪里有p->next。程序可能有错误。我觉得应该这样：
if (w!=0)
{ /*加大括号*/
if (visited[w]= =0)
if (w= = Vi && d==L-1)
{
d++;
top++;
stack[top]=v;
}
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
} /* 对应前面的大括号*/
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}
}while ((top!=0)| | w==0)&&(d!=1))
if (w!=0)
{ /*加大括号*/
if (visited[w]= =0)
if (w= = Vi && d==L-1)
{
d++;
top++;
stack[top]=v;
}
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
} /* 对应前面的大括号*/
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}
}while ((top!=0)| | w==0)&&(d!=1))
#7
退栈的时候是不是应该加上p=adj[v]->link;
#8
能否告知这是那里的题目?
#9
清华的一本数据结构习题。
#10
修正一下，加上大括号后，w应该没有访问过进栈，如果访问了也进栈，就形成回路了。另外w=0应该也进栈，否则不用退栈，只取栈顶元素。当访问到邻接表连尾的时候，必须有退栈过程。大括号加错了
退栈的时候不应该加上p=adj[v]->link，因为退栈后转到前面
if (head) p=adj[v]->link;
else {
p=p->next;
}
这里给p赋值。
此题的毛病在于对什么时候退栈的判断错误。
此题如用递归，可简单些，再和回溯配合，可以找出所有长度为L的路径。
退栈的时候不应该加上p=adj[v]->link，因为退栈后转到前面
if (head) p=adj[v]->link;
else {
p=p->next;
}
这里给p赋值。
此题的毛病在于对什么时候退栈的判断错误。
此题如用递归，可简单些，再和回溯配合，可以找出所有长度为L的路径。
#11
OK，谢谢！
#1
程序有错误，没有head=0的赋值。虽然条件语句里有，但head永远不会＝0。除此之外之外，思路很清晰。不知你哪里有疑问？
#2
确实head没有赋0，我也看了半天。但书上确实是这么写的，我想不出在哪里赋head为0。
从V=Vi出发，找V的邻接顶点W，若W已访问过，则找下一个邻接顶点；
这里找下一个顶点是怎么实现的。谢谢!
从V=Vi出发，找V的邻接顶点W，若W已访问过，则找下一个邻接顶点；
这里找下一个顶点是怎么实现的。谢谢!
#3
head＝0的赋值大概在
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=0; /*不是＝1 */
top--;
d--;
}
此时p=null,所以出栈，置head=0，表明取邻接表的下一个顶点。
此程序是深度优先遍历。先从vi开始遍历每个连表的表头的adj[v]->link顶点,如果为空,出栈取前一个顶点的下一个邻接顶点p->next.如果你把邻接表的结构搞清楚了就明白了.邻接表的结构是这样的.
adj[0]->link(指向v1)--v1->next(指向v2)--v2->next--null
adj[1]->link--v3->next--v4->next--null
adj[2]->link=null
....
adj[4]-link=null.
如果还又疑问,请指明.
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=0; /*不是＝1 */
top--;
d--;
}
此时p=null,所以出栈，置head=0，表明取邻接表的下一个顶点。
此程序是深度优先遍历。先从vi开始遍历每个连表的表头的adj[v]->link顶点,如果为空,出栈取前一个顶点的下一个邻接顶点p->next.如果你把邻接表的结构搞清楚了就明白了.邻接表的结构是这样的.
adj[0]->link(指向v1)--v1->next(指向v2)--v2->next--null
adj[1]->link--v3->next--v4->next--null
adj[2]->link=null
....
adj[4]-link=null.
如果还又疑问,请指明.
#4
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
这个地方不管W是不是访问过或为0都进栈？
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
这个地方不管W是不是访问过或为0都进栈？
#5
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}而且这里退栈的时候，返回去p=p->next应该不会是下一个邻接顶点。
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}而且这里退栈的时候，返回去p=p->next应该不会是下一个邻接顶点。
#6
w不管是不是访问都近栈，w=0因该不近栈，如果近栈，当w出栈时哪里有p->next。程序可能有错误。我觉得应该这样：
if (w!=0)
{ /*加大括号*/
if (visited[w]= =0)
if (w= = Vi && d==L-1)
{
d++;
top++;
stack[top]=v;
}
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
} /* 对应前面的大括号*/
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}
}while ((top!=0)| | w==0)&&(d!=1))
if (w!=0)
{ /*加大括号*/
if (visited[w]= =0)
if (w= = Vi && d==L-1)
{
d++;
top++;
stack[top]=v;
}
if (w!=Vj&&d<L-1)
{
d++;
top++;
stackp[top]=v;
visited[w]=1;
v=w;
head=1;
}
} /* 对应前面的大括号*/
else if (top>0)
{
visited[v]=0;
v=stack[top];
head=1;
top--;
d--;
}
}while ((top!=0)| | w==0)&&(d!=1))
#7
退栈的时候是不是应该加上p=adj[v]->link;
#8
能否告知这是那里的题目?
#9
清华的一本数据结构习题。
#10
修正一下，加上大括号后，w应该没有访问过进栈，如果访问了也进栈，就形成回路了。另外w=0应该也进栈，否则不用退栈，只取栈顶元素。当访问到邻接表连尾的时候，必须有退栈过程。大括号加错了
退栈的时候不应该加上p=adj[v]->link，因为退栈后转到前面
if (head) p=adj[v]->link;
else {
p=p->next;
}
这里给p赋值。
此题的毛病在于对什么时候退栈的判断错误。
此题如用递归，可简单些，再和回溯配合，可以找出所有长度为L的路径。
退栈的时候不应该加上p=adj[v]->link，因为退栈后转到前面
if (head) p=adj[v]->link;
else {
p=p->next;
}
这里给p赋值。
此题的毛病在于对什么时候退栈的判断错误。
此题如用递归，可简单些，再和回溯配合，可以找出所有长度为L的路径。
#11
OK，谢谢！