Golang DSA Chapter 9 Part 1: Graphs and Network Representation

Chapter 9 of “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi shifts gears into graphs and network structures. If you’ve been following along, we spent the last few chapters on searching, sorting, and hashing. Now we’re getting into something that models the real world more directly: connections between things.

This is Part 1, where we cover graphs as a concept, social network representation, map layouts, and knowledge graphs. Part 2 will handle sparse matrices and their uses.

What Is a Graph, Anyway?

A graph is just a collection of points (called vertices or nodes) connected by links (called edges). That’s it. Think of a social network where people are the points and friendships are the links. Or a map where cities are points and roads are links.

There are a few flavors of graphs worth knowing:

• Directed graph - links go one way (like following someone on Twitter)
• Non-directed graph - links go both ways (like a Facebook friendship)
• Connected graph - you can reach any node from any other node
• Non-connected graph - some nodes are isolated
• Simple graph - no duplicate links, no loops
• Multi-graph - allows multiple links between the same pair of nodes

To store a graph in code, you typically use one of these:

• Adjacency list - for each vertex, keep a list of its neighbors
• Adjacency matrix - a 2D grid where rows and columns are vertices, and the cells say whether a link exists
• Incidence matrix - rows are vertices, columns are edges, and the cells are booleans

The book starts with adjacency lists because they’re the most practical for most use cases.

A Basic Graph in Go

The first example builds a simple SocialGraph using slices. The struct holds a size and a 2D slice of links:

type SocialGraph struct {
    Size  int
    Links [][]Link
}

type Link struct {
    Vertex1    int
    Vertex2    int
    LinkWeight int
}

Each Link connects two vertices and carries a weight. You create the graph by making a slice of the right size:

func NewSocialGraph(num int) *SocialGraph {
    return &SocialGraph{
        Size:  num,
        Links: make([][]Link, num),
    }
}

Adding a link just appends to the right slot in the slice:

func (socialGraph *SocialGraph) AddLink(vertex1 int, vertex2 int, weight int) {
    socialGraph.Links[vertex1] = append(socialGraph.Links[vertex1],
        Link{Vertex1: vertex1, Vertex2: vertex2, LinkWeight: weight})
}

And printing walks through the adjacency list:

func (socialGraph *SocialGraph) PrintLinks() {
    var vertex int
    vertex = 0

    fmt.Printf("Printing all links from %d\n", vertex)
    var link Link
    for _, link = range socialGraph.Links[vertex] {
        fmt.Printf("Link: %d -> %d (%d)\n", link.Vertex1, link.Vertex2, link.LinkWeight)
    }

    fmt.Println("Printing all links in graph.")
    var adjacent []Link
    for _, adjacent = range socialGraph.Links {
        for _, link = range adjacent {
            fmt.Printf("Link: %d -> %d (%d)\n", link.Vertex1, link.Vertex2, link.LinkWeight)
        }
    }
}

Wire it up in main:

func main() {
    var socialGraph *SocialGraph
    socialGraph = NewSocialGraph(4)

    socialGraph.AddLink(0, 1, 1)
    socialGraph.AddLink(0, 2, 1)
    socialGraph.AddLink(1, 3, 1)
    socialGraph.AddLink(2, 4, 1)

    socialGraph.PrintLinks()
}

This gives you links from vertex 0 to 1 and 2, from 1 to 3, and from 2 to 4. Simple directed graph with uniform weights. Nothing complicated, but it shows the pattern: create the graph, add links, traverse them.

Social Network Representation

The basic integer-based graph is fine for learning, but it’s not very useful in the real world. Nobody wants to remember that vertex 7 is “John Smith.” The book builds a better version using Go maps and a custom Name type.

type Name string

type SocialGraph struct {
    GraphNodes map[Name]struct{}
    Links      map[Name]map[Name]struct{}
}

This is a pretty common Go pattern. The map[Name]struct{} acts like a set, since empty structs take zero bytes of memory. The Links field is a map of maps, so you can look up connections by name.

Creating the graph initializes both maps:

func NewSocialGraph() *SocialGraph {
    return &SocialGraph{
        GraphNodes: make(map[Name]struct{}),
        Links:      make(map[Name]map[Name]struct{}),
    }
}

Adding an entity checks if it already exists first:

func (socialGraph *SocialGraph) AddEntity(name Name) bool {
    var exists bool
    if _, exists = socialGraph.GraphNodes[name]; exists {
        return true
    }
    socialGraph.GraphNodes[name] = struct{}{}
    return true
}

And the AddLink method creates entities on the fly if they don’t exist yet:

func (socialGraph *SocialGraph) AddLink(name1 Name, name2 Name) {
    var exists bool
    if _, exists = socialGraph.GraphNodes[name1]; !exists {
        socialGraph.AddEntity(name1)
    }
    if _, exists = socialGraph.GraphNodes[name2]; !exists {
        socialGraph.AddEntity(name2)
    }
    if _, exists = socialGraph.Links[name1]; !exists {
        socialGraph.Links[name1] = make(map[Name]struct{})
    }
    socialGraph.Links[name1][name2] = struct{}{}
}

The main method creates a social network with a root node connected to three people, and some of those people connected to others:

func main() {
    var socialGraph *SocialGraph
    socialGraph = NewSocialGraph()

    var root Name = Name("Root")
    var john Name = Name("John Smith")
    var per Name = Name("Per Jambeck")
    var cynthia Name = Name("Cynthia Gibas")

    socialGraph.AddEntity(root)
    socialGraph.AddEntity(john)
    socialGraph.AddEntity(per)
    socialGraph.AddEntity(cynthia)

    socialGraph.AddLink(root, john)
    socialGraph.AddLink(root, per)
    socialGraph.AddLink(root, cynthia)

    var mayo Name = Name("Mayo Smith")
    var lorrie Name = Name("Lorrie Jambeck")
    var ellie Name = Name("Ellie Vlocksen")

    socialGraph.AddLink(john, mayo)
    socialGraph.AddLink(john, lorrie)
    socialGraph.AddLink(per, ellie)

    socialGraph.PrintLinks()
}

This is basically a two-level friend graph. Root knows John, Per, and Cynthia. John knows Mayo and Lorrie. Per knows Ellie. You could keep going and build out a full social network from here.

The key idea: by using maps instead of integer arrays, you get human-readable names and flexible sizing. You don’t need to know the total number of people upfront.

Map Layouts

The next example takes the same graph pattern and applies it to geography. Instead of people, the nodes are places with coordinates.

type Place struct {
    Name      string
    Latitude  float64
    Longitude float64
}

type MapLayout struct {
    GraphNodes map[Place]struct{}
    Links      map[Place]map[Place]struct{}
}

The methods follow the exact same pattern as the social graph. NewMapLayout initializes the maps, AddPlace adds a node, AddLink connects two places.

func NewMapLayout() *MapLayout {
    return &MapLayout{
        GraphNodes: make(map[Place]struct{}),
        Links:      make(map[Place]map[Place]struct{}),
    }
}

func (mapLayout *MapLayout) AddPlace(place Place) bool {
    var exists bool
    if _, exists = mapLayout.GraphNodes[place]; exists {
        return true
    }
    mapLayout.GraphNodes[place] = struct{}{}
    return true
}

func (mapLayout *MapLayout) AddLink(place1 Place, place2 Place) {
    var exists bool
    if _, exists = mapLayout.GraphNodes[place1]; !exists {
        mapLayout.AddPlace(place1)
    }
    if _, exists = mapLayout.GraphNodes[place2]; !exists {
        mapLayout.AddPlace(place2)
    }
    if _, exists = mapLayout.Links[place1]; !exists {
        mapLayout.Links[place1] = make(map[Place]struct{})
    }
    mapLayout.Links[place1][place2] = struct{}{}
}

The main method creates places with real-ish coordinates and links them:

func main() {
    var mapLayout *MapLayout
    mapLayout = NewMapLayout()

    var root Place = Place{"Algeria", 3, 28}
    var netherlands Place = Place{"Netherlands", 5.75, 52.5}
    var korea Place = Place{"Korea", 124.1, -8.36}
    var tunisia Place = Place{"Tunisia", 9, 34}

    mapLayout.AddPlace(root)
    mapLayout.AddPlace(netherlands)
    mapLayout.AddPlace(korea)
    mapLayout.AddPlace(tunisia)

    mapLayout.AddLink(root, netherlands)
    mapLayout.AddLink(root, korea)
    mapLayout.AddLink(root, tunisia)

    var singapore Place = Place{"Singapore", 103.8, 1.36}
    var uae Place = Place{"UAE", 54, 24}
    var japan Place = Place{"Japan", 139.75, 35.68}

    mapLayout.AddLink(korea, singapore)
    mapLayout.AddLink(korea, japan)
    mapLayout.AddLink(netherlands, uae)

    mapLayout.PrintLinks()
}

If you squint, this is the same concept as the social graph. The only difference is the node type. Go’s type system makes it easy to swap out what a “node” means while keeping the graph logic identical.

This pattern shows up everywhere in real applications: route planning, logistics, network topology. Any time you have locations connected by paths, this is the shape of the data.

Knowledge Graphs

The last graph example in this half of the chapter models a knowledge graph. This is a way to represent relationships between concepts or objects. The book uses a car and its parts as the example.

type Class struct {
    Name string
}

type KnowledgeGraph struct {
    GraphNodes map[Class]struct{}
    Links      map[Class]map[Class]struct{}
}

Again, same pattern. NewKnowledgeGraph, AddClass, AddLink all work the same way as the social graph and map layout versions.

The interesting part is the data model:

func main() {
    var knowledgeGraph *KnowledgeGraph
    knowledgeGraph = NewKnowledgeGraph()

    var car = Class{"Car"}
    var tyre = Class{"Tyre"}
    var door = Class{"Door"}
    var hood = Class{"Hood"}

    knowledgeGraph.AddClass(car)
    knowledgeGraph.AddClass(tyre)
    knowledgeGraph.AddClass(door)
    knowledgeGraph.AddClass(hood)

    knowledgeGraph.AddLink(car, tyre)
    knowledgeGraph.AddLink(car, door)
    knowledgeGraph.AddLink(car, hood)

    var tube = Class{"Tube"}
    var axle = Class{"Axle"}
    var handle = Class{"Handle"}
    var windowGlass = Class{"Window Glass"}

    knowledgeGraph.AddClass(tube)
    knowledgeGraph.AddClass(axle)
    knowledgeGraph.AddClass(handle)
    knowledgeGraph.AddClass(windowGlass)

    knowledgeGraph.AddLink(tyre, tube)
    knowledgeGraph.AddLink(tyre, axle)
    knowledgeGraph.AddLink(door, handle)
    knowledgeGraph.AddLink(door, windowGlass)

    knowledgeGraph.PrintLinks()
}

A car has tyres, doors, and a hood. A tyre has a tube and an axle. A door has a handle and window glass. This is basically a bill of materials, a tree of “is made of” relationships stored as a graph.

Knowledge graphs are used all over the place. Search engines use them to understand how concepts relate. Recommendation systems use them to figure out what you might like based on what you already bought. The book mentions ontologies here, which is the fancy word for a structured vocabulary of concepts and relationships.

The Pattern Worth Noticing

If you look at all three examples, the code is almost identical. Social graph, map layout, knowledge graph, they all have the same structure:

1. A map of nodes (using struct{} as a zero-cost set)
2. A map of maps for links (adjacency list stored as nested maps)
3. Methods for adding nodes, adding links, and printing

The only thing that changes is the node type: Name, Place, or Class. This is a great example of how Go’s simplicity works in your favor. You don’t need complex inheritance hierarchies. You just swap the type and the logic stays the same.

In a modern Go codebase, you might reach for generics to avoid repeating this pattern three times. But the book was written before generics landed in Go, so the repetition is understandable.

Wrapping Up

Chapter 9 Part 1 gives you a solid foundation for working with graphs in Go. The main takeaways:

• Graphs model connections between things, and adjacency lists are the go-to way to store them
• Go maps with empty struct values make great sets for tracking nodes
• Nested maps (map[T]map[T]struct{}) give you flexible adjacency lists
• The same graph pattern works for people, places, or abstract concepts

In Part 2, we’ll look at sparse matrices and how list-of-lists representation works for large, mostly empty datasets. That’s where things get a bit more math-heavy.

This post is part of a series retelling “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). All code examples are adapted from the book.