递归算法的内部运行问题
/* Note:Your choice is C IDE */#include "stdio.h"
#define MAX 100
#include<stdlib.h>
/*以下定义邻接矩阵类型*/
typedef struct node
{
int info;
int value;
}vtype;
typedef struct
{
int vexnum,arcnum;
vtype vexs[MAX];
int edges[MAX][MAX];
}adjmatrix;
/*一下定义邻接表类型*/
typedef struct qnode
{
int adjvex;
int value;
struct qnode *next;
}arcnode;
typedef struct
{
char data;
arcnode *firsthead;
}headone;
typedef struct
{
int n,e;
headone adjlist[MAX];
}graphlist;
int visited[MAX];
void pathall(graphlist *g,int u,int v,int path[],int i)
{
arcnode *p;
int j,n;
p=g->adjlist[u].firsthead;
while(p)
{
n=p->adjvex;
if(n==v)
{
path[i+1]=v;
for(j=0;j<=i+1;j++)
printf("%3d",path[j]);printf("\n");
}
else if(visited[n]==0)
{
path[i+1]=n;
pathall(g,n,v,path,i+1);
}
p=p->next;
}
visited[u]=0;
}
void pathall2(graphlist *g,int u,int v,int l,int path[],int d)
{
int m,i;
arcnode *p;
visited[u]=1;
d++;
path[d]=u;
if(u==v&&d==l)
{
for(i=0;i<=d;i++)
printf("%3d",path[i]);
printf("\n");
}
p=g->adjlist[u].firsthead;
while(p)
{
m=p->adjvex;
if(visited[m]==0)
pathall2(g,m,v,l,path,d);
p=p->next;
}
visited[u]=0;
d--;
}
int shortpath(graphlist *g,int u,int v,int path[])
{
struct
{
int vno;
int level;
int parent;
}qu[MAX];
int front=-1,rear=-1,k,lev,i,j;
arcnode *p;
visited[u]=1;
rear++;
qu[rear].vno=u;
qu[rear].level=0;
qu[rear].parent=-1;
while(front<rear)
{
front++;
k=qu[front].vno;
lev=qu[front].level;
if(k==v)
{
i=0;
j=front;
while(j!=-1)
{
path[lev-i]=qu[j].vno;
j=qu[j].parent;
i++;
}
return lev;
}
p=g->adjlist[k].firsthead;
while(p)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
rear++;
qu[rear].vno=p->adjvex;
qu[rear].level=lev+1;
qu[rear].parent=front;
}
p=p->next;
}
}
return 0;
}
void mattolist(graphlist *G,adjmatrix *g)
{
int i,j,n=g->vexnum;
arcnode *p;
for(i=0;i<n;i++)
G->adjlist[i].firsthead=NULL;
for(i=0;i<n;i++)
for(j=n-1;j>=0;j--)
if(g->edges[i][j])
{
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=j;p->value=g->edges[i][j];
p->next=G->adjlist[i].firsthead;
G->adjlist[i].firsthead=p;
}
G->n=n;G->e=g->arcnum;
}
void displaylist(graphlist *G)
{
arcnode *p;
int i;
for(i=0;i<G->n;i++)
{
printf("头顶点为[%d]=>",i);
p=G->adjlist[i].firsthead;
while(p)
{
printf("(%d,%d)->",p->adjvex,p->value);
p=p->next;
}printf("\n");
}
}
void main()
{
int i,j;
int u=5,v=2,d=3;
int path[MAX];
adjmatrix g;
graphlist *G;
int a[MAX][6]={{0,1,0,1,0,0},
{0,0,1,0,0,0},
{1,0,0,0,0,1},
{0,0,1,0,0,1},
{0,0,0,1,0,0},
{1,1,0,1,1,0}};
g.vexnum=6;g.arcnum=10;
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
g.edges[i][j]=a[i][j];
G=(graphlist *)malloc(sizeof(graphlist));
mattolist(G,&g);
printf("图G的邻接矩阵:\n");
displaylist(G);printf("\n");
for(i=0;i<g.vexnum;i++)
visited[i]=0;
printf("从%d到%d的所有路径:\n",u,v);
path[0]=u;visited[u]=1;
pathall(G,u,v,path,0);printf("\n");
printf("从%d到%d的所有长度为%d路径:\n",u,v,d);
pathall2(G,u,v,d,path,-1);printf("\n");
for(i=0;i<g.vexnum;i++)
visited[i]=0;
printf("从%d到%d最短路径:\n",u,v);
for(i=0;i<g.vexnum;i++)
visited[i]=0;
j=shortpath(G,u,v,path);
for(i=0;i<=j;i++)
printf("%3d",path[i]);
printf("\n\n");
}
我想问一下pathall这个函数里面的visited[u]=0;从新开始使用u顶点时，系统怎么知道以前那个输入过。如，5 0 1 2
第二路径:5 0 3 2 ，系统怎么判定5 0 1 2 访问过，递归的时候到底开辟了多少个栈，能解释一下栈的运行情况吗？
