Graphs are a versatile data structure used to represent relationships between objects. They consist of vertices (nodes) and edges (connections between nodes). There are several ways to represent graphs, each with its advantages and use cases.
Adjacency Matrix: A 2D array where each cell (i, j) indicates the presence (and possibly the weight) of an edge between vertices i and j.
Adjacency List: An array or map where each index or key represents a vertex, and the corresponding value is a list of adjacent vertices (or edges with weights).
Edge List: A list of all edges, where each edge is represented by a tuple (or struct) containing the two vertices it connects (and possibly the weight).
Let's look at how to implement these representations and fundamental graph algorithms in Go.
gopackage main
import (
"fmt"
)
// Graph using adjacency matrix
type Graph struct {
matrix [][]int
}
func NewGraph(size int) *Graph {
matrix := make([][]int, size)
for i := range matrix {
matrix[i] = make([]int, size)
}
return &Graph{matrix: matrix}
}
func (g *Graph) AddEdge(v1, v2, weight int) {
g.matrix[v1][v2] = weight
g.matrix[v2][v1] = weight // For undirected graph
}
func (g *Graph) Print() {
for _, row := range g.matrix {
fmt.Println(row)
}
}
func main() {
graph := NewGraph(5)
graph.AddEdge(0, 1, 1)
graph.AddEdge(0, 4, 1)
graph.AddEdge(1, 2, 1)
graph.AddEdge(1, 3, 1)
graph.AddEdge(1, 4, 1)
graph.AddEdge(2, 3, 1)
graph.AddEdge(3, 4, 1)
graph.Print()
}
gopackage main
import (
"fmt"
)
// Graph using adjacency list
type Graph struct {
adjList map[int][]int
}
func NewGraph() *Graph {
return &Graph{adjList: make(map[int][]int)}
}
func (g *Graph) AddEdge(v1, v2 int) {
g.adjList[v1] = append(g.adjList[v1], v2)
g.adjList[v2] = append(g.adjList[v2], v1) // For undirected graph
}
func (g *Graph) Print() {
for vertex, edges := range g.adjList {
fmt.Printf("%d -> %v\n", vertex, edges)
}
}
func main() {
graph := NewGraph()
graph.AddEdge(0, 1)
graph.AddEdge(0, 4)
graph.AddEdge(1, 2)
graph.AddEdge(1, 3)
graph.AddEdge(1, 4)
graph.AddEdge(2, 3)
graph.AddEdge(3, 4)
graph.Print()
}
gopackage main
import (
"fmt"
)
// Edge represents an edge in the graph
type Edge struct {
src, dest, weight int
}
// Graph using edge list
type Graph struct {
edges []Edge
}
func (g *Graph) AddEdge(src, dest, weight int) {
g.edges = append(g.edges, Edge{src, dest, weight})
}
func (g *Graph) Print() {
for _, edge := range g.edges {
fmt.Printf("%d --%d--> %d\n", edge.src, edge.weight, edge.dest)
}
}
func main() {
graph := &Graph{}
graph.AddEdge(0, 1, 1)
graph.AddEdge(0, 4, 1)
graph.AddEdge(1, 2, 1)
graph.AddEdge(1, 3, 1)
graph.AddEdge(1, 4, 1)
graph.AddEdge(2, 3, 1)
graph.AddEdge(3, 4, 1)
graph.Print()
}
gopackage main
import "fmt"
type Graph struct {
adjList map[int][]int
}
func NewGraph() *Graph {
return &Graph{adjList: make(map[int][]int)}
}
func (g *Graph) AddEdge(v1, v2 int) {
g.adjList[v1] = append(g.adjList[v1], v2)
g.adjList[v2] = append(g.adjList[v2], v1) // For undirected graph
}
func (g *Graph) DFS(start int) {
visited := make(map[int]bool)
g.dfsHelper(start, visited)
}
func (g *Graph) dfsHelper(v int, visited map[int]bool) {
visited[v] = true
fmt.Printf("%d ", v)
for _, neighbor := range g.adjList[v] {
if !visited[neighbor] {
g.dfsHelper(neighbor, visited)
}
}
}
func main() {
graph := NewGraph()
graph.AddEdge(0, 1)
graph.AddEdge(0, 4)
graph.AddEdge(1, 2)
graph.AddEdge(1, 3)
graph.AddEdge(1, 4)
graph.AddEdge(2, 3)
graph.AddEdge(3, 4)
fmt.Print("DFS: ")
graph.DFS(0)
}
gopackage main
import (
"container/list"
"fmt"
)
type Graph struct {
adjList map[int][]int
}
func NewGraph() *Graph {
return &Graph{adjList: make(map[int][]int)}
}
func (g *Graph) AddEdge(v1, v2 int) {
g.adjList[v1] = append(g.adjList[v1], v2)
g.adjList[v2] = append(g.adjList[v2], v1) // For undirected graph
}
func (g *Graph) BFS(start int) {
visited := make(map[int]bool)
queue := list.New()
visited[start] = true
queue.PushBack(start)
for queue.Len() > 0 {
element := queue.Front()
v := element.Value.(int)
queue.Remove(element)
fmt.Printf("%d ", v)
for _, neighbor := range g.adjList[v] {
if !visited[neighbor] {
visited[neighbor] = true
queue.PushBack(neighbor)
}
}
}
}
func main() {
graph := NewGraph()
graph.AddEdge(0, 1)
graph.AddEdge(0, 4)
graph.AddEdge(1, 2)
graph.AddEdge(1, 3)
graph.AddEdge(1, 4)
graph.AddEdge(2, 3)
graph.AddEdge(3, 4)
fmt.Print("BFS: ")
graph.BFS(0)
}
gopackage main
import (
"container/heap"
"fmt"
"math"
)
// Edge represents an edge in the graph
type Edge struct {
dest, weight int
}
// Graph represents a graph using adjacency list representation
type Graph struct {
adjList map[int][]Edge
}
func NewGraph() *Graph {
return &Graph{adjList: make(map[int][]Edge)}
}
func (g *Graph) AddEdge(src, dest, weight int) {
g.adjList[src] = append(g.adjList[src], Edge{dest, weight})
g.adjList[dest] = append(g.adjList[dest], Edge{src, weight}) // For undirected graph
}
// Item represents a node in the priority queue
type Item struct {
vertex, distance int
index int
}
// PriorityQueue implements heap.Interface and holds Items
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].distance < pq[j].distance }
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil // avoid memory leak
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}
// Dijkstra's algorithm to find shortest paths from source to all vertices
func (g *Graph) Dijkstra(start int) map[int]int {
distances := make(map[int]int)
for vertex := range g.adjList {
distances[vertex] = math.MaxInt32
}
distances[start] = 0
pq := &PriorityQueue{}
heap.Init(pq)
heap.Push(pq, &Item{vertex: start, distance: 0})
for pq.Len() > 0 {
item := heap.Pop(pq).(*Item)
u := item.vertex
for _, edge := range g.adjList[u] {
v := edge.dest
weight := edge.weight
if distances[u]+weight < distances[v] {
distances[v] = distances[u] + weight
heap.Push(pq, &Item{vertex: v, distance: distances[v]})
}
}
}
return distances
}
func main() {
graph := NewGraph()
graph.AddEdge(0, 1, 4)
graph.AddEdge(0, 7, 8)
graph.AddEdge(1, 2, 8)
graph.AddEdge(1, 7, 11)
graph.AddEdge(2, 3, 7)
graph.AddEdge(2, 8, 2)
graph.AddEdge(2, 5, 4)
graph.AddEdge(3, 4, 9)
graph.AddEdge(3, 5, 14)
graph.AddEdge(4, 5, 10)
graph.AddEdge(5, 6, 2)
graph.AddEdge(6, 7, 1)
graph.AddEdge(6, 8, 6)
graph.AddEdge(7, 8, 7)
distances := graph.Dijkstra(0)
for vertex, distance := range distances {
fmt.Printf("Distance from 0 to %d is %d\n", vertex, distance)
}
}
Graphs are powerful data structures used to model relationships between entities. Understanding their different representations and implementing fundamental algorithms like DFS, BFS, and Dijkstra's shortest path in Go is essential for solving a wide range of problems. Each representation (adjacency matrix, adjacency list, edge list) has its own use cases and advantages. Using these implementations, you can efficiently manage and query graphs in your Go applications.