本文共 1224 字，大约阅读时间需要 4 分钟。

图的结构体定义

typedef struct {	int adjvex;	EdgeNode *next;}EdgeNode;typedef struct{	int data;	EdgeNode *firstEdge;}Vertex;typedef struct {	Vertex adjList[maxsize];	int n,e;}AGraph;

1.假设图G采用邻接表存储，设设计一个算法，输出此图G从顶点vi到vj长度为L的所有简单路径

int visited[maxsize];int path[maxsize];void printAllPath(AGraph *g,int vi,int vj,int d,int L){	EdgeNode *p;int i;	if(vi==vj&&d==L)	{		cout<<"one path:";		for(i=0;i<=d;i++)			cout<
   
    <<" ";	}	++d;	path[d]=vi;	visited[vi]=1;	p=g->adjList[vi].firstedge;	while(p!=NULL)	{		if(visited[p->adjvex]==0)			printAllPath(g,p->adjvex,vj,d,L);		p=p->next;	} 	visited[vi]=0;	--d;}
   

2.藏宝图，设计一个算法，要求从入口到出口，必须经过v1,v6,不得经过v4

int visited[maxsize];int path[maxsize];int d=-1;int cond(int v1,int v4,int v6){	int flag1=0,flag2=0,flag3=1,i;	for(i=0;i<=d;i++)	{		if(path[i]==v1) 			flag1=1;		else if(path[i]==v4)			flag3=0;		else if(path[i]==v6)			flag2=1;	}	return flag1&&flag2&&flag3;} void printPath(AGraph *g,int vi,int vj,int v1,int v4,int v6){	EdgeNode *p;int i;	if(vi===vj&&cond(v1,v4,v6))	{		for(i=0;i<=d;i++)			cout<
   
    <<" ";	} 	++d;path[d]=vi;	visited[vi]=1;	p=g->adjList[vi]->firstedge;	while(p!=NULL)	{		if(visited[p->adjvex]==0)			printPath(g,p->adjvex,vj,v1,v4,v6);		p=p->next;	}	visited[vi]=0;	--d;}
   

转载地址：http://tzzdf.baihongyu.com/