回溯法关于图

104 阅读 0 评论 69 点赞

我是靠谱客的博主活泼早晨，这篇文章主要介绍回溯法关于图，现在分享给大家，希望可以做个参考。

图的结构体定义

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的所有简单路径

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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<<path[i]<<" ";
	}
	++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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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<<path[i]<<" ";
	} 
	++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;
}