溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關golang刷leetcode技巧之如何解決節(jié)點間通路問題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
節(jié)點間通路。給定有向圖，設計一個算法，找出兩個節(jié)點之間是否存在一條路徑。
示例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
提示：
節(jié)點數(shù)量n在[0, 1e5]范圍內。
節(jié)點編號大于等于 0 小于 n。
圖中可能存在自環(huán)和平行邊。
解題思路
1，圖相關的問題，一般廣度優(yōu)先遍歷或者深度優(yōu)先遍歷即可解決
2，廣度優(yōu)先遍歷借助對接，深度優(yōu)先遍歷借助棧，或者遞歸
3，針對尋找聯(lián)通路徑，廣度優(yōu)先遍歷比較簡單
4，為了表示方便，可以先把圖轉成鄰接矩陣
代碼實現(xiàn)
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技巧之如何解決節(jié)點間通路問題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
