Back to Repositories

Testing Graph BFS Traversal Implementation in hello-algo

This test suite validates breadth-first search (BFS) implementation in a graph data structure, focusing on traversal operations and vertex handling in Go. The tests verify correct graph initialization and BFS traversal order through an adjacency list representation.

Test Coverage Overview

The test coverage encompasses graph initialization and BFS traversal verification.

Tests graph construction with 10 vertices (0-9) and 12 edges
Validates BFS traversal starting from vertex 0
Verifies correct vertex ordering during traversal
Ensures proper adjacency list representation

Implementation Analysis

The testing approach utilizes Go’s native testing framework with custom graph implementations.

Uses TestGraphBFS function as the main test entry point
Implements vertex conversion utilities for test data preparation
Leverages custom printing functions for verification
Incorporates direct graph manipulation through adjacency list

Technical Details

Testing Framework: Go testing package
Custom Utilities: ValsToVets, VetsToVals conversion functions
Graph Implementation: Adjacency list representation
Vertex Management: Custom Vertex type with value mapping

Best Practices Demonstrated

The test implementation showcases several testing best practices in Go.

Clear test case setup with explicit initialization
Proper separation of graph construction and traversal logic
Comprehensive vertex and edge relationship testing
Effective use of custom helper functions for test readability

krahets/hello-algo

codes/go/chapter_graph/graph_bfs_test.go

            
// File: graph_bfs_test.go
// Created Time: 2023-02-18
// Author: Reanon ([email protected])

package chapter_graph

import (
	"fmt"
	"testing"

	. "github.com/krahets/hello-algo/pkg"
)

func TestGraphBFS(t *testing.T) {
	/* 初始化无向图 */
	vets := ValsToVets([]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9})
	edges := [][]Vertex{
		{vets[0], vets[1]}, {vets[0], vets[3]}, {vets[1], vets[2]}, {vets[1], vets[4]},
		{vets[2], vets[5]}, {vets[3], vets[4]}, {vets[3], vets[6]}, {vets[4], vets[5]},
		{vets[4], vets[7]}, {vets[5], vets[8]}, {vets[6], vets[7]}, {vets[7], vets[8]}}
	graph := newGraphAdjList(edges)
	fmt.Println("初始化后，图为:")
	graph.print()

	/* 广度优先遍历 */
	res := graphBFS(graph, vets[0])
	fmt.Println("广度优先遍历（BFS）顶点序列为:")
	PrintSlice(VetsToVals(res))
}