数据结构小作业——判断顶点之间是否存在长度为k的路径_leetcode 无向图中是否有一条为k的路径

reference

link

概要

自选存储结构，编写一算法判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（即不含回路）

思路

1.

不含回路，即要求不能重复访问。这里用一个visited数组标记即可。
该图为无向图，那么需要判断，从其中任何一个顶点出发，能否到达另一个顶点。可以用dfs或者bfs，同时在遍历过程中记录路径长度。
但是这个长度k要怎么记录呢？怎么判断正好长度为k呢？如果传地址的话，每次直接修改这个k值也可以，但是这样因为每次递归调用，递归返回的话，这个k就是已经修改过的了。

2.

实在想不出来，看了别人的思路。即函数的递归出口是k=0，然后每次调用的时候传入k-1，即分治法。这样就可以啦

code

创建无向图

void CreateGraph(MGraph *G)
{
	int i, j;//图的顶点和边数 
	int s, e, w;//边的起始点，终点，权值 
	cout<<"请输入图的顶点数和边数"<<endl;
	cin>>G->vertexes>>G->edges;//输入顶点数和边数
	cout<<"请输入图的所有顶点"<<endl; 
	for(i = 0; i < G->vertexes; i++)
	{
		cin>>G->vexs[i];	
	}
	//邻接矩阵初始化
	for(i = 0; i < G->vertexes; i++)
	{
		for(j = 0; j < G->vertexes; j++)
		{
			G->arc[i][j] = 0;		
		}
	} 
	cout<<"请输入图的所有边"<<endl; 
	for(j = 0; j < G->edges; j++)
	{
		cin>>s>>e>>w;//输入边的起始点，终点，权值
		G->arc[s - 1][e - 1] = w; 
		G->arc[e - 1][s - 1] = w;//矩阵沿对角线对称 
	}
}
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

找以a为起点的顶点能否经过长为k的路径到达b顶点

也算是回溯法？

bool find(MGraph G, int a, int b, int k)
{
	int j;
	cout<<"k:"<<k<<"a:"<<a<<"b:"<<b<<endl;
	if(k == 0 && a == b)//如果找到了，则返回真 
	{
		return true;
	}
	else if(k > 0)
	{
		//找到与a相邻的顶点进一步递归
		for(j = 0; j < G.vertexes; j++)
		{
			if(G.arc[a - 1][j] != 0 && !visited[j])
			{
				visited[j] = true;
				if(find(G, j + 1, b, k - 1))//以j+1为顶点，找b 
				{
					return true;//要是找到了，那么以这个顶点为起点能找到，返回为真否则从下一个顶点为起点开始找 
				}
				visited[j] = false;//这步千万不能忘啊！！！ 
			}
		}
	}
	return false;	
}
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

总

体会

实在想不出来就去看一下别人的思路找找启发吧。要不然，这个时间会变成无效时间，还是啥也想不出来。