DFS
A simple implementation of DFS based on linked list representation of graphs
![DFS](/_next/image?url=%2Fstatic%2Fimages%2Fsnippets%2FGo-Logo.png&w=96&q=75)
package main
import (
"bufio"
"fmt"
"io"
"strconv"
"strings"
)
type NodeColor int
const (
White NodeColor = iota
Grey
Black
)
type Node struct {
color NodeColor
discoveryTime int
finishTime int
pi *Node
}
func (n *Node) Reset() {
n.color = White
n.discoveryTime = -1
n.finishTime = -1
n.pi = nil
}
type Graph struct {
nodes []*Node
links map[*Node][]*Node
time int
}
func (g *Graph) Reset() {
g.time = 0
for _, n := range g.nodes {
n.Reset()
}
}
func NewGraph(size int32) *Graph {
var nodes []*Node
var i int32
for i = 0; i < size; i++ {
nodes = append(nodes, &Node{})
}
return &Graph{
nodes: nodes,
links: make(map[*Node][]*Node),
}
}
func (g *Graph) AddLink(link []int32) {
g.links[g.nodes[link[0]-1]] = append(g.links[g.nodes[link[0]-1]], g.nodes[link[1]-1])
}
func (g *Graph) AddBatchLink(links [][]int32) {
for _, link := range links {
g.AddLink(link)
}
}
func (g *Graph) DFSVis(n *Node, parent *Node) {
g.time++
n.discoveryTime = g.time
n.color = Grey
n.pi = parent
for _, child := range g.links[n] {
if child.color == White {
g.DFSVis(child, n)
}
}
g.time++
n.finishTime = g.time
n.color = Black
}
func (g *Graph) DFS() {
g.Reset()
for _, n := range g.nodes {
if n.color == White {
g.DFSVis(n, nil)
}
}
}
func main() {
// first line contains the number of nodes N space seperated from the number of links M between nodes
// the M subsequent lines with the x y format each describe a link from node x to y
// the last line is the source from which we want to compute the BFS
input := `4 3
1 2
2 3
1 4
`
r := strings.NewReader(input)
reader := bufio.NewReaderSize(r, 1024*1024)
nm := strings.Split(readLine(reader), " ")
nTemp, err := strconv.ParseInt(nm[0], 10, 64)
if err != nil {
panic(err)
}
n := int32(nTemp)
mTemp, err := strconv.ParseInt(nm[1], 10, 64)
if err != nil {
panic(err)
}
m := int32(mTemp)
var links [][]int32
for linksRowItr := 0; linksRowItr < int(m); linksRowItr++ {
linksRowTemp := strings.Split(readLine(reader), " ")
var linksRow []int32
for _, linksRowItem := range linksRowTemp {
linksItemTemp, err := strconv.ParseInt(linksRowItem, 10, 64)
if err != nil {
panic(err)
}
linksItem := int32(linksItemTemp)
linksRow = append(linksRow, linksItem)
}
if len(linksRow) != int(2) {
panic("Bad input")
}
links = append(links, linksRow)
}
grph := NewGraph(n)
grph.AddBatchLink(links)
grph.DFS()
for indx, nd := range grph.nodes {
fmt.Printf("node %d: [%d %d]\n", indx, nd.discoveryTime, nd.finishTime)
}
}
func readLine(reader *bufio.Reader) string {
str, _, err := reader.ReadLine()
if err == io.EOF {
return ""
}
return strings.TrimRight(string(str), "\r\n")
}