Class: CodeCook::DFS

Inherits:
Object
  • Object
show all
Defined in:
手写代码必备手册(Ruby版).rb

Overview

graph = DFS::Graph.new(10) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 0) graph.add_edge(2, 4) graph.add_edge(2, 5) graph.add_edge(8, 9) dfs = DFS.new(graph, 0) dfs.path_to(1)

Defined Under Namespace

Classes: Graph

Instance Method Summary (collapse)

Constructor Details

- (DFS) initialize(graph, source)

Returns a new instance of DFS



505
506
507
508
509
510
511
 
# File '手写代码必备手册(Ruby版).rb', line 505

def initialize(graph, source)
    @graph = graph
    @source = source
    @edge_to = Array.new(graph.size, nil)
    @visited = Array.new(graph.size, false)
    search(source)
end

Instance Method Details

- (Object) path_to(v) 



513
514
515
516
517
518
519
520
521
522
523
524
525
 
# File '手写代码必备手册(Ruby版).rb', line 513

def path_to(v)
    return nil unless @visited[v]

    path = []
    w = v
    while w != @source
        path.push(w)
        w = @edge_to[w]
    end
    path.push(@source)

    path.reverse
end