golang刷leetcode技巧之如何解决节点间通路问题
这篇文章将为大家详细讲解有关golang刷leetcode技巧之如何解决节点间通路问题，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
示例1:
输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出：true
示例2:
输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
输出 true
提示：
节点数量n在[0, 1e5]范围内。
节点编号大于等于 0 小于 n。
图中可能存在自环和平行边。
解题思路
1，图相关的问题，一般广度优先遍历或者深度优先遍历即可解决
2，广度优先遍历借助对接，深度优先遍历借助栈，或者递归
3，针对寻找联通路径，广度优先遍历比较简单
4，为了表示方便，可以先把图转成邻接矩阵
代码实现
func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {adj:=make([][]int,n)for i:=0;i<len(graph);i++{adj[graph[i][0]]=append(adj[graph[i][0]],graph[i][1])}var q queueq.push(start)// fmt.Println(adj,q.isEmpty())for !q.isEmpty(){y:=q.pop()for _,x:=range adj[y]{//fmt.Println(q,x,y)if x==target{return true}q.push(x)}}return false}type queue struct{data []int}func (q *queue)push(x int){q.data=append(q.data,x)}func(q* queue)pop()int{x:=q.data[0]q.data=q.data[1:]return x}func(q *queue)isEmpty()bool{return len(q.data)==0}
关于“golang刷leetcode技巧之如何解决节点间通路问题”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。