This function implements algorithm 4.2.1 of Gross and Yellen. The
input is a graph and a node to start from. It returns a
standard vertex labeling of graph. This is a vector with
elements corresponding to the nodes of graph and with values
that correspond to point in the depth first search the node is
visited.
Usage
DFS(object, node, checkConn=TRUE)
Arguments
object
An instance of the graph class.
node
A character indicating the starting node.
checkConn
A logical indicating whether the connectivity
of the graph should be checked.
Details
This function implements algorithm 4.2.1 of Gross and Yellen. Specific
details are given there.
It requires that the graph be connected. By default, this is checked,
but since the checking can be expensive it is optional.
A faster and mostly likely better implementation of depth first
searching is given by dfs in the RBGL
package.
Value
A vector with names given by the nodes of graph whose values
are 0 to one less than the number of nodes. These indices
indicate the point at which the node will be visited.
Author(s)
R. Gentleman
References
Graph Theory and its Applications, J. Gross and J. Yellen.
R version 3.3.1 (2016-06-21) -- "Bug in Your Hair"
Copyright (C) 2016 The R Foundation for Statistical Computing
Platform: x86_64-pc-linux-gnu (64-bit)
R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.
R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.
Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.
> library(graph)
Loading required package: BiocGenerics
Loading required package: parallel
Attaching package: 'BiocGenerics'
The following objects are masked from 'package:parallel':
clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
clusterExport, clusterMap, parApply, parCapply, parLapply,
parLapplyLB, parRapply, parSapply, parSapplyLB
The following objects are masked from 'package:stats':
IQR, mad, xtabs
The following objects are masked from 'package:base':
Filter, Find, Map, Position, Reduce, anyDuplicated, append,
as.data.frame, cbind, colnames, do.call, duplicated, eval, evalq,
get, grep, grepl, intersect, is.unsorted, lapply, lengths, mapply,
match, mget, order, paste, pmax, pmax.int, pmin, pmin.int, rank,
rbind, rownames, sapply, setdiff, sort, table, tapply, union,
unique, unsplit
> png(filename="/home/ddbj/snapshot/RGM3/R_BC/result/graph/DFS.Rd_%03d_medium.png", width=480, height=480)
> ### Name: DFS
> ### Title: Depth First Search
> ### Aliases: DFS DFS,graph,character-method
> ### Keywords: manip
>
> ### ** Examples
>
> RNGkind("Mersenne-Twister")
> set.seed(123)
> g1 <- randomGraph(letters[1:10], 1:4, p=.3)
> RNGkind()
[1] "Mersenne-Twister" "Inversion"
> DFS(g1, "a")
a b c d e f g h i j
0 1 6 2 3 4 8 5 9 7
>
>
>
>
>
> dev.off()
null device
1
>