Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 图
- class Graph {
- constructor(count, adj_list) {
- this.count = count // 记录顶点的个数
- this.adj = new Array(count) // 邻接表
- // 初始化邻接表
- for (let i = 0; i < count; i++) {
- this.adj[i] = new Array()
- }
- for (let j = 0, len = adj_list.length; j < len; j++) {
- let vw = adj_list[j]
- this.adj[vw[0]].push(vw[1])
- }
- }
- showGraph() {
- let str = ''
- for (let i = 0; i < this.count; i++) {
- str += (i + " -> ")
- for (let j = 0, len = this.adj[i].length; j < len; j++) {
- if (this.adj[i][j] != undefined) {
- str += (this.adj[i][j] + ' ')
- }
- }
- str += "\n"
- }
- console.log(str)
- }
- build_path(edgeTo, end, start) {
- const path = []
- for (let i = end; i != start; i = edgeTo[i]) {
- path.push(i)
- }
- path.push(start)
- return path.reverse()
- }
- find_path(start, end) {
- const que = [], edgeTo = [], visited = []
- visited[start] = true
- que.push(start)
- while (que.length > 0) {
- let v = que.shift()
- for (let w of this.adj[v]) {
- if (!visited[w]) {
- visited[w] = true
- edgeTo[w] = v
- que.push(w)
- if (w == end) {
- return this.build_path(edgeTo, end, start)
- }
- }
- }
- }
- }
- }
- const count = 4
- const g = new Graph(count, [[0,1], [0,2], [1,0], [1,2], [1,3], [2,0], [2,1], [3,0], [3,1]])
- g.showGraph()
- for (let i = 0; i < count; i++) {
- for (let j = 0; j < count; j++) {
- if (i != j) {
- console.log(i + '->' + j, g.find_path(i, j))
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement