给了以下点和路径,选取一点输出所有可能走过的点,走过的点不能重复
比如选取a,输出 [[a,b,c],[a,c,b,d,f],[a,b,d,e],…]**
class Point { name = ""; neighbor: string[] = []; } cosnt data: Point[] = [ { name: "a", neighbor: ["b", "c"] }, { name: "b", neighbor: ["a", "c", "d"] }, { name: "c", neighbor: ["a", "b"] }, { name: "d", neighbor: ["b", "e", "f", "g"] }, { name: "e", neighbor: ["d"] }, { name: "f", neighbor: ["d"] }, ]
每一个点用Point类表示,name代表点的名字,neighbor表示该点的邻居
一组走过的点使用string[]表示
实现一个方法,传入一个target,即点的name,返回所有可能走过的点的组合string[][]。(history参数下面会说到)
type getPath = (target: string, history?: string[]) => string[][];
比如我们从a开始,下一个点可能是b或者c,将会有两种分支。目前我们走的这组点为[‘a’],那么走下一步的时候我们要复制一下我们走过的点的组合,即复制成两个[‘a’]。多个分支复制成多个。那么[‘a’]就是下一次递归的history参数。
然后假设我们现在走过的是[‘a’, ‘b’],下一个点就不能有a了,也就是b点此时可选的邻居是[‘c’, ‘d’]。
实现一个方法,传入走过的点的组合,返回可选的下一个点
type getNext = (history: string[]) => string[];
如果下一步没路走了,也就代表我们找到一组可以走的点。
我们走了一步(target),得到当前走过的点(history),并且也知道下一步可以走哪(getNext),那么接下来就是用getPath进行递归。
export class Point { name = ""; neighbor: string[] = []; } export default class PathService { constructor(props: Point[]) { this.data = this.deepCopy(props); } data: Point[] = []; getData() { return this.deepCopy(this.data); } setData(pointList: Point[]) { this.data = this.deepCopy(pointList); this.resList = []; } resList: string[][] = []; getResList(): string[][] { const res: string[][] = []; for (const v of this.resList) { res.push([...v]); } return res; } /** * 深拷贝一个Point[] * @param pointList */ deepCopy(pointList: Point[]): Point[] { const result: Point[] = []; for (const v of pointList) { result.push({ name: v.name, neighbor: [...v.neighbor], }); } return result; } /** * 获取下一次可选路径 * @param historyArr 已走过的路径 */ getNext(historyArr: string[]): string[] { let nextData: string[] = []; // 获取刚走过的点 const target = this.data.find( (v) => v.name === historyArr[historyArr.length - 1] ); // console.log(target); if (target) { nextData = target.neighbor; } // 将走过的点过滤掉 nextData = nextData.filter((v) => historyArr.indexOf(v) === -1); // // console.log(nextData) return nextData; } /** * 输入其实目标,获取 * @param target * @param history */ getPath(target: string, history?: string[]): string[][] { // console.log(target); let nextHistory: string[] = []; if (history) { // console.log(history); nextHistory = [...history]; } // 先走一步 nextHistory.push(target); // console.log('nextHistory', nextHistory) // 下一步能走哪呢 const targetNavigation = this.getNextData(nextHistory || []); // console.log("targetNavigation", targetNavigation); // 没路走了 if (targetNavigation.length === 0) { this.resList.push(nextHistory); } // 还有路走,可走的分支进行递归 for (const v of targetNavigation) { this.getPath(v, nextHistory); } // 递归结束,全在this.resList里存好了 return this.getResList(); } }
const data: Point[] = [ { name: "a", neighbor: ["b", "c"] }, { name: "b", neighbor: ["a", "c", "d"] }, { name: "c", neighbor: ["a", "b"] }, { name: "d", neighbor: ["b", "e", "f", "g"] }, { name: "e", neighbor: ["d"] }, { name: "f", neighbor: ["d"] }, ]; let pathService = new PathService(data); let result = pathService.getPath("a"); console.log(result);