Back to Repositories

Testing Graph DFS Traversal Implementation in hello-algo

This test suite validates the implementation of Depth-First Search (DFS) traversal in a graph data structure. It verifies the correct construction of an undirected graph and tests the DFS algorithm’s ability to traverse vertices in the expected order.

Test Coverage Overview

The test coverage focuses on verifying the graph DFS implementation with a specific undirected graph structure.

Tests graph initialization with predefined vertices and edges
Validates DFS traversal starting from a specific vertex
Ensures correct vertex ordering in the traversal result
Covers basic graph connectivity scenarios

Implementation Analysis

The testing approach utilizes Go’s testing framework to validate graph operations and traversal algorithms.

Uses helper functions ValsToVets and VetsToVals for vertex conversion
Implements graph construction using adjacency list representation
Employs fmt package for visual verification of graph structure
Demonstrates modular test organization with clear setup and execution phases

Technical Details

Testing Framework: Go testing package (testing.T)
Custom Graph Package: github.com/krahets/hello-algo/pkg
Visualization: fmt package for graph structure printing
Helper Functions: PrintSlice for result verification
Data Structures: Vertex type and adjacency list representation

Best Practices Demonstrated

The test implementation showcases several testing best practices for graph algorithms.

Clear test case setup with documented graph initialization
Visual feedback for graph structure verification
Separation of graph construction and traversal logic
Use of helper functions for data conversion and output formatting
Proper package organization and import management

krahets/hello-algo

codes/go/chapter_graph/graph_dfs_test.go

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

package chapter_graph

import (
	"fmt"
	"testing"

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

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

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