© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_16

16. Graph Structures

Richard Wiener1  
(1)
Colorado Springs, CO, USA
 

In the previous chapter, we presented dynamic programming and three applications.

In this chapter, we introduce graph structures and some applications. We show several examples of how to represent a graph, and we examine some basic algorithms associated with graph traversal.

In the next section, we examine how graphs can be represented.

16.1 Representing Graphs

Graph data structures provide one of the most useful and powerful frameworks for algorithm design. A graph (not to be confused with a pictorial representation of a mathematical function) can represent a huge number of systems from communication networks, transportation, electrical grid, online interactions, games, and pattern matching, to name a few.

A graph consists of a set of nodes and edges between them: Graph = (N, E), where N is the collection of nodes and E the collection of edges.

In a directed graph, each edge has a specified direction.

Nodes are adjacent if there is an edge connecting them. Nodes that are adjacent to a given node are neighbors.

The degree of a node is the number of nodes incident to it.

A path in a graph is a subgraph (subset of N and E) where the edges connect a series of nodes in a sequence without visiting any node more than once.

A weighted graph has a weight associated with each edge. The length of a path is the sum of its edge weights.

Consider the weighted directed graph shown in Figure 16-1.

An illustration of a weighted graph with nodes and edges, and paths with numerical values. Nodes are represented by alphabets. The values are depicted in the format: node to node, numerical number. A to B, 2. A to C, 5. A to D, 9. B to D, 3. C to D, 7. C to F, 9. D to E, 4. E to G, 7. G to F, 3. E to F, 6.

Figure 16-1

A weighted graph

In the next section, we discuss two methods for traversing this graph or any graph. We allow the node to be of generic type OrderedStringer. Here, the generic type is String.

16.2 Traversing Graphs

We look at two important traversal algorithms:
  1. 1.

    Depth-first search (DFS)

     
  2. 2.

    Breadth-first search (BFS)

     

The method DFS uses recursion and moves in a sequence outward from the starting node and continues to visit nodes in a sequence as far as possible from the starting node without revisiting a node and getting progressively closer to the starting node.

The method BFS uses iteration and an internal queue to traverse the graph incrementally from the starting node. Nodes are visited at distances progressively further from the starting vertex toward the furthest vertex from the starting vertex.

The edge values are stored in a global map variable as edges are defined.

In the next section, we discuss and implement a depth-first traversal and a breadth-first traversal of a graph with generic vertex values.

16.3 Depth- and Breadth-First Search

We start by defining important data types.
type OrderedStringer interface {
    comparable
    String() string
}
type Vertex[T OrderedStringer] struct {
    Key T
    Neighbors map[T]*Vertex[T]
}
type Graph[T OrderedStringer] struct {
    Vertices map[T]*Vertex[T]
}
var visitation []string

Our generic type is OrderedStringer. Entities of this type must be comparable and have a string representation using the String() function.

A generic Vertex contains a Key (type T) and a map, Neighbors, mapping keys (type T) to pointers to other vertices.

A generic Graph contains a map, Vertices, mapping keys (type T) to pointers to vertices.

A global visitation variable is defined. This variable is a slice of string representing the traversal keys.

Several important functions and methods are shown as follows:
func NewVertex[T OrderedStringer](key T) *Vertex[T] {
    return &Vertex[T]{
        Key: key,
        Neighbors: map[T]*Vertex[T]{},
    }
}
func NewGraph[T OrderedStringer]() *Graph[T] {
    return &Graph[T]{Vertices: map[T]*Vertex[T]{}}
}
func (g *Graph[T]) AddVertex(key T) {
    vertex := NewVertex(key)
    g.Vertices[key] = vertex
}
func (g *Graph[T]) AddEdge(key1, key2 T, edgeValue int) {
    vertex1 := g.Vertices[key1]
    vertex2 := g.Vertices[key2]
    if vertex1 == nil || vertex2 == nil {
        return
    }
    vertex1.Neighbors[vertex2.Key] = vertex2
    g.Vertices[vertex1.Key] = vertex1
    g.Vertices[vertex2.Key] = vertex2
}

The function NewVertex takes a key (of type T) and returns a pointer to a Vertex with an empty map, Neighbors.

The function NewGraph returns an empty graph with an empty map of Vertices.

The method AddVertex creates a new vertex and assigns Vertices[key] to the new vertex.

The method AddEdge takes the two keys, assigns these to the Vertices field of graph, and assigns the Neighbors field of vertex1 to vertex2.

Depth-First Search

The first traversal method we examine is depth-first search. This method moves outward from the starting vertex and moves directly to the furthest vertex not yet visited.

It is implemented as follows:
func (g *Graph[T]) DepthFirstSearch(start *Vertex[T],
           visited map[T]bool) {
    if start == nil {
        return
    }
    visited[start.Key] = true
    visitation = append(visitation, start.Key.String())
    // for each of the adjacent vertices, call the
    // function recursively if it hasn't yet been
    // visited
    for _, v := range start.Neighbors {
        // The sequence of v may change from run to run
        if visited[v.Key] {
            continue
        }
        g.DepthFirstSearch(v, visited)
    }
}

The parameter, visited, passed in must be initialized to an empty map before invoking the method.

The sequence of recursive calls causes the traversal to move away from the starting vertex until it is furthest away before backtracking and finding other vertices far away from the starting vertex.

Breadth-First Search

The second traversal method we examine is breadth-first search. This method visits vertices close to the starting vertex slowly moving outward and away from the starting vertex. There is no recursion used here. A queue is used to store vertices that neighbor visited vertices. These neighboring vertices are traversed first. So as the name of this method implies, this traversal moves to adjacent vertices slowly getting further from the starting vertex. It is implemented as follows:
type Queue[T any] struct {
    items []T
}
// Methods
func (queue *Queue[T]) Insert(item T) {
    // item is added to the right-most position in the
    // slice
    queue.items = append(queue.items, item)
}
func (queue *Queue[T]) Remove() T {
    returnValue := queue.items[0]
    queue.items = queue.items[1:]
    return returnValue
}
func (g *Graph[T]) BreadthFirstSearch(start *Vertex[T],
           visited map[T]bool) {
    if start == nil {
        return
    }
    queue := Queue[*Vertex[T]]{} // Queue hold pointers
                                 // to Vertex
    current := start
    for {
        if !visited[current.Key] {
            visitation = append(visitation,
                            current.Key.String())
        }
        visited[current.Key] = true
        // Insert each neighboring vertex not visited
        // onto the queue
        for _, v := range current.Neighbors {
            if !visited[v.Key] {
                queue.Insert(v)
            }
        }
        // Grab first vertex in the queue and remove it
        if len(queue.items) > 0 {
            current = queue.Remove()
        } else {
            break
        }
    }
}

The queue plays a central role in the implementation of this method. It forces all nearby vertices to be visited early in contrast to depth-first search. Like the latter method, this method requires the parameter visited to be initialized to an empty map before invoking the method.

Listing 16-1 presents all the details of defining and traversing a graph. The graph shown in Section 16.1 is constructed in the main driver program.
package main
import (
    "fmt"
)
type OrderedStringer interface {
    comparable
    String() string
}
type Graph[T OrderedStringer] struct {
    Vertices map[T]*Vertex[T]
}
type Vertex[T OrderedStringer] struct {
    Key T
    Neighbors map[T]*Vertex[T]
}
var visitation []string
func NewVertex[T OrderedStringer](key T) *Vertex[T] {
    return &Vertex[T]{
        Key: key,
        Neighbors: map[T]*Vertex[T]{},
    }
}
func NewGraph[T OrderedStringer]() *Graph[T] {
    return &Graph[T]{Vertices: map[T]*Vertex[T]{}}
}
func (g *Graph[T]) AddVertex(key T) {
    vertex := NewVertex(key)
    g.Vertices[key] = vertex
}
func (g *Graph[T]) AddEdge(key1, key2 T,
        edgeValue int) {
    vertex1 := g.Vertices[key1]
    vertex2 := g.Vertices[key2]
    if vertex1 == nil || vertex2 == nil {
        return
    }
    vertex1.Neighbors[vertex2.Key] = vertex2
    g.Vertices[vertex1.Key] = vertex1
    g.Vertices[vertex2.Key] = vertex2
}
func (g *Graph[T]) DepthFirstSearch(start *Vertex[T],
          visited map[T]bool) {
    if start == nil {
        return
    }
    visited[start.Key] = true
    visitation = append(visitation, start.Key.String())
    for _, v := range start.Neighbors {
        // The sequence of v may change from run to run
        if visited[v.Key] {
            continue
        }
        g.DepthFirstSearch(v, visited)
    }
}
type Queue[T any] struct {
    items []T
}
// Methods
func (queue *Queue[T]) Insert(item T) {
    queue.items = append(queue.items, item)
}
func (queue *Queue[T]) Remove() T {
    returnValue := queue.items[0]
    queue.items = queue.items[1:]
    return returnValue
}
func (g *Graph[T]) BreadthFirstSearch(start *Vertex[T],
            visited map[T]bool) {
    if start == nil {
        return
    }
    queue := Queue[*Vertex[T]]{}
    current := start
    for {
        if !visited[current.Key] {
            visitation = append(visitation,
                             current.Key.String())
        }
        visited[current.Key] = true
        for _, v := range current.Neighbors {
            if !visited[v.Key] {
                queue.Insert(v)
            }
        }
        // Grab first vertex in the queue and remove it
        if len(queue.items) > 0 {
            current = queue.Remove()
        } else {
            break
        }
    }
}
func (g *Graph[T]) String() string {
    result := ""
    for i := 0; i < len(visitation); i++ {
        result += " " + visitation[i]
    }
    return result
}
// Make String implement Stringer
type String string
func (str String) String() string {
    return string(str)
}
func main() {
    g := NewGraph[String]()
    g.AddVertex("A")
    start := g.Vertices["A"]
    g.AddVertex("B")
    g.AddVertex("C")
    g.AddVertex("D")
    g.AddVertex("E")
    g.AddVertex("F")
    g.AddVertex("G")
    g.AddEdge("A", "B", 2)
    g.AddEdge("A", "C", 5)
    g.AddEdge("A", "D", 9)
    g.AddEdge("B", "D", 3)
    g.AddEdge("C", "F", 9)
    g.AddEdge("D", "E", 4)
    g.AddEdge("E", "D", 4)
    g.AddEdge("F", "E", 6)
    g.AddEdge("E", "G", 7)
    g.AddEdge("F", "G", 3)
    visited := make(map[String]bool)
    visitation = []string{}
    g.DepthFirstSearch(start, visited)
    fmt.Println("Depth First Search:", g.String())
    visited = make(map[String]bool)
    visitation = []string{}
    g.BreadthFirstSearch(start, visited)
    fmt.Println("Breadth First Search:", g.String())
}
/* Output
Depth First Search:  A B D E G C F
Breadth First Search:  A C D B F E G
*/
Listing 16-1

Defining and traversing a graph

The two output traversal sequences confirm our assertions about the sequence of visited nodes for depth- vs. breadth-first search.

In the next section, we present and implement a solution to a classic graph problem. We show how to find the shortest path from a source node to every other node in a graph.

16.4 Single-Source Shortest Path in Graph

Given a graph and a source node in the graph. Find the shortest paths from the source node to all the nodes in the graph.

The celebrated Dijkstra algorithm is presented. It was conceived by computer scientist Edsger W.​ Dijkstra in 1956 and published three years later.

Consider the graph with source node “A” shown in Figure 16-2.

An illustration of a graph, for Dijkstra&#x2019;s single-source shortest path. A is considered the source node. The distance is depicted in the format: path, number. A B, 4. A H, 1. B H, 11. B C, 1. C I, 2. H I, 7. H G, 1. I G, 1. C D, 7. C F, 1. G F, 2. D E, 1. D F, 8. D E, 1. F E, 10.

Figure 16-2

Graph for single-source shortest path

The Dijkstra algorithm returns the shortest distance from source node “A” to all the other nodes in the graph.

Implementation

Listing 16-2 presents an implementation of the Dijkstra algorithm.
package main
import (
    "fmt"
    "github.com/jiaxwu/container/heap"
)
// PriorityQueue Priority queue
type PriorityQueue[T any] struct {
    h *heap.Heap[T]
}
func New[T any](less func(e1 T, e2 T) bool)
                *PriorityQueue[T] {
    return &PriorityQueue[T]{
        h: heap.New(less),
    }
}
func (p *PriorityQueue[T]) Add(elem T) {
    p.h.Push(elem)
}
func (p *PriorityQueue[T]) Remove() T {
    return p.h.Pop()
}
func (p *PriorityQueue[T]) Len() int {
    return p.h.Len()
}
func (p *PriorityQueue[T]) Empty() bool {
    return p.Len() == 0
}
func Less(a, b tuple) bool {
    return a.weight < b.weight
}
// end priority queue
type edges = map[rune]int
type Graph map[rune]edges
type tuple struct {
    node   rune
    weight int
}
func convert(r rune) int {
    return int(r) - 65
}
func Dijkastra(graph Graph) []tuple {
    distances := make([]tuple, len(graph))
    for i := 0; i < len(graph); i++ {
        distances[i] = tuple{'A', 32767}
    }
    distances[0] = tuple{'A', 0}
    heapQueue := New[tuple](Less)
    t := tuple{'A', 0}
    heapQueue.Add(t)
    for {
        if heapQueue.Len() == 0 {
            break
        }
        t = heapQueue.Remove()
        currentNode := t.node
        currentDistance := t.weight
        if currentDistance >
                          distances[convert(currentNode)].weight {
            continue
        }
        for t, w := range graph[currentNode] {
            neighbor := t
            weight := w
            distance := currentDistance + weight
            /*
               Only consider this new path if it's
               better than any path we've already
               found
            */
            if distance <
                       distances[convert(neighbor)].weight {
                distances[convert(neighbor)] =
                           tuple{neighbor, distance}
                heapQueue.Add(tuple{neighbor,
                          distance})
            }
        }
    }
    return distances
}
func main() {
    graph := make(map[rune]edges)
    graph['A'] = edges{'B': 4, 'H': 1}
    graph['B'] = edges{'A': 4, 'C': 1, 'H': 11}
    graph['C'] = edges{'B': 1, 'I': 2, 'F': 1, 'D': 7}
    graph['D'] = edges{'C': 7, 'F': 8, 'E': 1}
    graph['E'] = edges{'D': 1, 'F': 10}
    graph['F'] = edges{'G': 2, 'C': 1, 'D': 8, 'E': 10}
    graph['G'] = edges{'F': 2, 'I': 1, 'H': 1}
    graph['H'] = edges{'G': 1, 'I': 7, 'B': 11, 'A': 1}
    graph['I'] = edges{'C': 2, 'H': 7, 'G': 1}
    solution := Dijkastra(graph)
    for node, weight := range solution {
        fmt.Printf("%s %d ", string(node + 65), weight)
    }
}
/* Output
A {65 0} B {66 4} C {67 5} D {68 12} E {69 13} F {70 4} G {71 2} H {72 1} I {73 3}
*/
Listing 16-2

Dijkstra algorithm

Explanation of Solution

Each node in the graph is represented by a tuple defined as
type tuple struct {
    node rune
    weight int
}
type edges = map[rune]int
A Graph is defined as:
type Graph map[rune]edges

In a graph, each node, with key of type rune, such as “A”, is mapped to another map, edges, from rune to int. This layering of abstractions is needed to represent a structure as complicated as a graph.

A priority queue plays a central role in implementing a solution to the problem. Here, we implement PriorityQueue with generic type T by importing package “github.com/jiaxwu/container/heap”.

We define a Less function that compares the int field of the tuples to order them from smallest to largest.

We initialize the queue using
heapQueue := New[tuple](Less)

Here, we see another example whereby having a generic structure, PriorityQueue, makes it easy to create an instance with base-type tuple, useful in this application.

We define a slice, distances, as containing tuples of node (type rune) and an int that represents the best distance so far. We initialize distances to have very large initial value.

We set distances[0] to tuple{‘A’, 0}.

We push this tuple onto the heap queue. This heap queue is set up to ensure that the tuple with the smallest distance is at the head of the line, the first tuple that can be removed.

In a loop that terminates when the queue becomes empty, we remove the head of the queue and assign current distance to its weight field. If this value is greater than the second field of the tuple removed from the queue, we discard it by continuing the loop.

In a second inner loop in which we range over the connections from the current node, we compare the sum of the current distance and the weight of each graph connection to the best distance so far for the given connection. If this best distance so far is less than the value in the distances slice, we push the tuple onto the queue and update the distances slice.

In main, we define the graph shown earlier. The output displays the shortest distances from source node “A” to each of the other nodes.

In the next section, we present another classic graph problem and its solution – minimum spanning tree.

16.5 Minimum Spanning Tree

A minimum spanning tree for a weighted undirected connected graph is a collection of edges that touch all nodes of the graph without any cycles and with minimum weight. The weight of the spanning tree is defined as the sum of the weights of the edges that comprise the tree.

Although several people have laid claim to creating an algorithm for creating a minimum spanning tree from a weighted graph, the two most famous algorithms for doing this are by Prim and Kruskal.

We shall present the Kruskal algorithm and its implementation. This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50, in 1956 and was written by Joseph Kruskal.

The approach that is taken is to incrementally build the tree one edge at a time by choosing the cheapest edge among those still available. This strategy is a classic greedy strategy in which a local optimization leads to a global optimum solution.

Kruskal Algorithm

  1. 1.

    Sort the edges in ascending order of their weights.

     
  2. 2.

    Select the edge having minimum weight and add it to the spanning tree providing that a cycle does not occur.

     
  3. 3.

    Repeat steps 1 and 2 until all nodes have been covered.

     

To see how the algorithm works, we shall walk through an example.

Consider the tree shown in Figure 16-3.

An illustration of a graph, for Kruskal&#x2019;s spanning tree, with a step-by-step example. The edges and weights are as follows: A B, 1. A C, 1. C G, 1. B C, 4. C D, 20. G D, 6. D E, 2. D F, 5. E F, 3.

Figure 16-3

Graph for Kruskal algorithm

The first edge that we insert into our spanning tree has the smallest weight. There are three such edges, “AB”, “AC”, and “CG”, each with weight equal to 1. We insert all three into the spanning tree since no cycles are produced. Next, we insert “DE” and “EF”, with weights 2 and 3, since these produce no cycles.

The next smallest edge is “BC”, with a weight of 4. If we were to add this edge to the spanning tree, we would get a cycle among the nodes, “A”, “B”, and “C”. So we reject this edge. Likewise, we reject the next smallest available edge, “DF”, since its inclusion would produce a cycle among the nodes, “D”, “E”, and “F”.

The next smallest node, “GD”, with weight 6, is added next. The remaining available node, “CD”, is rejected since its inclusion would create a cycle among the nodes, “C”, “G”, and “D”.

A minimum spanning tree for this graph is therefore

{1 A B} {1 A C} {1 C G} {2 D E} {3 E F} {6 G D} with a total weight of 14.

In the next section, we implement the Kruskal algorithm. The main driver program uses the graph shown previously.

16.6 Implementation of Kruskal Algorithm

Our implementation of the Kruskal algorithm is relatively short. The details are presented in Listing 16-3 and carefully explained after the listing.
package main
import (
    "fmt"
    "sort"
)
type Edge struct {
    weight int
    node1 Node
    node2 Node
}
type Node = string
type EdgeSlice []Edge
// Infrastructure to allow []Edges to be sorted
func (edges EdgeSlice) Len() int {
    return len(edges)
}
func (edges EdgeSlice) Swap(i, j int) {
    edges[i], edges[j] = edges[j], edges[i]
}
func (edges EdgeSlice) Less(i, j int) bool {
    return edges[i].weight < edges[j].weight
}
var connection map[Node]Node
/*
    The initial level of each Node is 0.
    If the node is node2 of an Edge,
    increase its level by 1.
*/
var end map[Node]int
func Initialize(node Node) {
    connection[node] = node
    end[node]  = 0
}
func Find(node Node) Node {
    // Stops a cycle
    if connection[node] != node {
        connection[node] = Find(connection[node])
    }
    return connection[node]
}
func Connect(node1, node2 Node) {
    n1 := Find(node1)
    n2 := Find(node2)
    fmt.Printf(" Find(%s) = %s", node1, n1)
    fmt.Printf(" Find(%s) = %s", node2, n2)
    if n1 != n2 {
        fmt.Printf(" end[%s] = %d", n1, end[n1])
        fmt.Printf(" end[%s] = %d", n2, end[n2])
        if end[n1] > end[n2] {
            connection[n2] = n1
            fmt.Printf(" connection[%s] = %s", n2,
                       n1)
        } else {
            connection[n1] = n2
            fmt.Printf(" connection[%s] = %s", n1,
                       n2)
            if end[n1] == end[n2] {
                end[n2] += 1
                fmt.Printf(" end[%s] = 1", n2)
            }
        }
    }
}
func Kruskal(nodes []Node, edges EdgeSlice) []Edge {
    for _, node := range nodes {
        Initialize(node)
    }
    spanningTree := []Edge{}
    sort.Sort(edges)
    for _, edge := range edges {
        node1 := edge.node1
        node2 := edge.node2
        n1 := Find(node1)
        n2 := Find(node2)
        fmt.Printf(" Find(%s) = %s", node1, n1)
        fmt.Printf(" Find(%s) = %s", node2, n2)
        if n1 != n2 {
            Connect(node1, node2)
            fmt.Printf(" Connect(%s, %s)", node1,
                       node2)
            spanningTree = append(spanningTree, edge)
        } else {
            fmt.Printf(" Reject edge %s and %s",
                       node1, node2)
        }
    }
    return spanningTree
}
func main() {
    connection = make(map[Node]Node)
    end = make(map[Node]int)
    // Define the graph by its nodes and edges
    nodes := []Node{"A", "B", "C", "D", "E", "F", "G"}
    edges := []Edge{ {1, "A", "B"}, {1, "A", "C"},
                     {4, "B", "C"}, {20, "C", "D"},
                     {2, "D", "E"}, {3, "E", "F"},
                     {6, "G", "D"}, {1, "C", "G"},
                     {5, "D", "F"} }
    spanningTree := Kruskal(nodes, edges)
    fmt.Println(" ", spanningTree)
}
/* Output
Find(A) = A
Find(B) = B
Find(A) = A
Find(B) = B
end[A] = 0
end[B] = 0
connection[A] = B
end[B] = 1
Connect(A, B)
Find(A) = B
Find(C) = C
Find(A) = B
Find(C) = C
end[B] = 1
end[C] = 0
connection[C] = B
Connect(A, C)
Find(C) = B
Find(G) = G
Find(C) = B
Find(G) = G
end[B] = 1
end[G] = 0
connection[G] = B
Connect(C, G)
Find(D) = D
Find(E) = E
Find(D) = D
Find(E) = E
end[D] = 0
end[E] = 0
connection[D] = E
end[E] = 1
Connect(D, E)
Find(E) = E
Find(F) = F
Find(E) = E
Find(F) = F
end[E] = 1
end[F] = 0
connection[F] = E
Connect(E, F)
Find(B) = B
Find(C) = B
Reject edge B and C
Find(D) = E
Find(F) = E
Reject edge D and F
Find(G) = B
Find(D) = E
Find(G) = B
Find(D) = E
end[B] = 1
end[E] = 1
connection[B] = E
end[E] = 1
Connect(G, D)
Find(C) = E
Find(D) = E
Reject edge C and D
 [{1 A B} {1 A C} {1 C G} {2 D E} {3 E F} {6 G D}]*/
Listing 16-3

Kruskal algorithm

Explanation of Kruskal Implementation

We walk through the example given in the main driver to uncover the details of this implementation.

We initialize the connection and end maps.

We define the input, the slice of Node values, and the slice of Edge values in main.

We pass these slices to the Kruskal function.

In function Kruskal, we initialize all the nodes by setting the connection of the node to itself and the end value to 0.

We define spanningTree as an empty slice of edges. We sort the edges by their weight, having created the infrastructure for ensuring that an edge slice can be sorted (functions Len, Swap, and Less).

In a loop over the edges, for each edge, we define node1 and node2 as the beginning and ending nodes of the edge.

The code has been instrumented with many fmt.Printf outputs that chronicle the algorithm in detail showing, in particular, the rejection of edges that cause cycles.

Let’s take a look.

The first edge that needs to be rejected is the link from “B” to “C”. Let’s zoom in on the details following the connection from “E” to “F”. The next link to be inserted is the link from “C” to “B”.

Since Find(“B”) equals Find(“C”), this link is not appended to the spanning tree.

The output lines shown in boldface lead to the rejections of the links shown. The link from “D” to “F” is rejected for the same reason.

16.7 Summary

In this chapter, we introduced graph structures and some applications. We showed several examples of how to represent a graph, and we examined some basic algorithms associated with graph traversal.

The next chapter introduces the famed Travelling Salesperson Problem (TSP). All known exact solutions to this problem are computationally intractable. We introduce one such solution and test it on a smaller-sized problem. We also show how to plot a tour associated with a TSP solution.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.17.162.26