Representing a Graph

graph.go

package main

import (
	"fmt"
	"log"
)

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
See See Cormen, et al, 3rd ed. page 592

For my implementation, a Graph consists of an array,
  s.t. the array indices correspond to a unique vertex ID.
  At each index is a pointer to a list of adjacent vertices.
  Each node of the list indicates both the adjacent vertex's
  ID and the weight of the connecting edge.

If the graph is unweighted, then the weights are all 0.
Graphs are treated as directed graphs.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

type Adjacency struct {
	id     int        // numerical id corresponding to the vertex's "name"
	weight int        // the weight of the edge b/w the parent and the adjacent node
	next   *Adjacency // the next node adjacent to the parent
}

type Graph struct {
	Adj []*Adjacency // list of adjacencies
	V   int          // number of vertices
	E   int          // number of edges
}

func initGraph(num_vertices int) *Graph {
	return &Graph{make([]*Adjacency, num_vertices), num_vertices, 0}
}

// adds a directed connection from vertex u to v
func (G *Graph) addEdge(u int, v int, weight int) {
	if v >= G.V || u >= G.V {
		log.Print("You're trying to create an edge to non-extant vertices!")
		return
	}
	new_adj := &Adjacency{v, weight, nil}
	new_adj.next = G.Adj[u]
	G.Adj[u] = new_adj
	G.E += 1
}

func (G *Graph) addVertex() {
	G.Adj = append(G.Adj, nil)
	G.V += 1
}

func (G *Graph) printGraph() {
	fmt.Printf("\nV: %v\tE: %v\n", G.V, G.E)

	for i := 0; i < G.V; i += 1 {
		fmt.Printf("[%v]", i)

		for e := G.Adj[i]; e != nil; e = e.next {
			fmt.Printf(" -> %v [%v]", e.weight, e.id)
		}
		fmt.Printf("\n")
	}
	fmt.Printf("\n")
}

main.go

package main

import (
	"container/list"
	"fmt"
	//"reflect"
)

func bfs(G *Graph, s int) {

	explored := make([]bool, G.V, G.V) // track if a vertex is already explored or not
	Q := list.New()                    // a FIFO queue which tracks newly explored adjacencies
	Q.PushBack(s)

	for Q.Len() != 0 { // when Q is empty, that means we have no new unexplored nodes to visit
		v := Q.Remove(Q.Front()).(int) // type assertion: https://golang.org/ref/spec#Type_assertions
		for w := G.Adj[v]; w != nil; w = w.next {
			if !explored[w.id] {
				explored[w.id] = true
				Q.PushBack(w.id)
			}
		}
	}
	fmt.Println(explored)
}

/*func dfs() {

}

func dijkstra() {

}*/

func main() {
	G := initGraph(5)
	G.addEdge(0, 1, 0)
	G.addEdge(0, 3, 0)
	G.addEdge(1, 2, 0)
	G.addEdge(2, 3, 0)
	G.addEdge(2, 4, 0)
	//G.addEdge(3, 0, 0)
	G.addEdge(4, 1, 0)
	G.printGraph()

	bfs(G, 4)    // explores all nodes except node 0, since we cannot get from node 0 to 4

	/*for w := G.Adj[0]; w != nil; w = w.next {
	  fmt.Println(w.id)
	}*/

}