グラフの幅優先探索と深さ優先探索を実装するためのgo言語によるプログラミングを学ぶ

// matrix implementation of the graph
typedef struct MGRAPH{
    nodes int[]; //nodes
    edges int[][]; //edges
}mGraph;

package main
import "fmt"
type Node struct{
	value int; //node is of type int
};
type Graph struct{
	nodes []*Node
	edges map[Node][]*Node // undirected graph of adjacency representation
}

//add nodes
// can be interpreted as a member function of Graph
func (g *Graph) AddNode(n *Node) {
	g.nodes = append(g.nodes, n)
}
//add edges
func (g *Graph) AddEdge(u, v *Node) {
	g.edges[*u] = append(g.edges[*u],v) //u->v edges
	g.edges[*v] = append(g.edges[*v],u) //u->v edges
}
//print graph
func (g *Graph) Print(){
	//range traverses g.nodes, returning index and value
	for _,iNode:=range g.nodes{
		fmt.Printf("%v:",iNode.value)
		for _,next:=range g.edges[*iNode]{
			fmt.Printf("%v->",next.value)
		}
		fmt.Printf("\n")
	}
}
func initGraph() Graph{
	g := Graph{}
	for i:=1;i<=5;i++{
		g.AddNode(&Node{i,false})
	}
	//generate edges
	A := [...] int{1,1,2,2,2,3,4}
	B := [...] int{2,5,3,4,5,4,5}
	g.edges = make(map[Node][]*Node)//initialize edges
	for i:=0;i<7;i++{
		g.AddEdge(g.nodes[A[i]-1], g.nodes[B[i]-1])
	}
	return g
}
func main(){
	g := initGraph()
	g.Print()
}

PS E:\Code> go run . \goGraph.go
1:2->5->
2:1->3->4->5->
3:2->4->
4:2->3->5->
5:1->2->4->

type Node struct{
	value int;
	searched bool;
}
/*func initGraph() Graph{
    g := Graph{}
*/
    //Change the node generation function accordingly
    for i:=1;i<=5;i++{
		g.AddNode(&Node{i,false})
	}
/*
...
*/

type Graph struct{
	nodes []*Node
	edges map[*Node][]*Node // undirected graph of adjacency representation
}
//add edges
func (g *Graph) AddEdge(u, v *Node) {
	g.edges[u] = append(g.edges[u],v) //u->v edges
	g.edges[v] = append(g.edges[v],u) //u->v edges
}
//print graph
func (g *Graph) Print(){
	//range iterates over g.nodes, returning index and value
	for _,iNode:=range g.nodes{
		fmt.Printf("%v:",iNode.value)
		for _,next:=range g.edges[iNode]{
			fmt.Printf("%v->",next.value)
		}
		fmt.Printf("\n")
	}
}
func initGraph() Graph{
	g := Graph{}
	for i:=1;i<=9;i++{
		g.AddNode(&Node{i,false})
	}
	//generate edges
	A := [...] int{1,1,2,2,2,3,4,5,5,6,1}
	B := [...] int{2,5,3,4,5,4,5,5,6,7,8,9}
	g.edges = make(map[*Node][]*Node)//initialize edges
	for i:=0;i<11;i++{
		g.AddEdge(g.nodes[A[i]-1], g.nodes[B[i]-1])
	}
	return g
}
func (g *Graph) BFS(n *Node){
	var adNodes[] *Node // store the nodes to be searched
	n.searched = true
	fmt.Printf("%d:",n.value)
	for _,iNode:=range g.edges[n]{
		if !iNode.searched {
			adNodes = append(adNodes,iNode)
			iNode.searched=true
			fmt.Printf("%v ",iNode.value)
		}
	}
	fmt.Printf("\n")
	for _,iNode:=range adNodes{
		g.BFS(iNode)
	}
}
func main(){
	g := initGraph()
	g.Print()
	g.BFS(g.nodes[0])
}

PS E:\Code\goStudy> go run . \goGraph.go
1:2->5->9->
2:1->3->4->5->
3:2->4->
4:2->3->5->
5:1->2->4->6->7->
6:5->8->
7:5->
8:6->
9:1->
// The following are the BFS results
1:2 5 9
2:3 4
3:
4:
5:6 7
6:8
8:
7:
9:

func (g *Graph) visitNode(n *Node){
	for _,iNode:= range g.edges[n]{
		if !iNode.searched{
			iNode.searched = true
			fmt.Printf("%v->",iNode.value)
			g.visitNode(iNode)
			return
		}
	}
}
func main(){
	g := initGraph()
	g.nodes[0].searched = true
	fmt.Printf("%v->",g.nodes[0].value)
	g.visitNode(g.nodes[0])
}

PS E:\Code> go run . \goGraph.go
1->2->3->4->5->6->8->

func (g *Graph) DFS(){
	for _,iNode:=range g.nodes{
		if !iNode.searched{
			iNode.searched = true
			fmt.Printf("%v->",iNode.value)
			g.visitNode(iNode)
			fmt.Printf("\n")
			g.DFS()
		}
	}
}
func main(){
	g := initGraph()
	g.nodes[0].searched = true
	fmt.Printf("%v->",g.nodes[0].value)
	g.visitNode(g.nodes[0])
}

PS E:\Code> go run . \goGraph.go
1->2->3->4->5->6->8->
7->
9->