图论

图论是计算机科学中的一个重要领域，它在算法设计中占有举足轻重的地位。解决图论问题的通用思路通常包括以下几个步骤：

理解图的表示：图可以通过邻接矩阵或邻接表来表示。邻接矩阵适合表示稠密图，而邻接表适合表示稀疏图。
确定图的类型：图可以是无向或有向，加权或非加权。这将决定你选择哪种算法。
选择合适的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的图遍历算法。DFS 适合用于寻找组件或检查环，而 BFS 适合于寻找最短路径。
考虑可能的优化：对于特定问题，可能需要使用特定的算法，如 Dijkstra 算法用于在加权图中找到最短路径，Bellman-Ford 算法可以处理负权重边，Floyd-Warshall 算法用于计算所有对最短路径，以及 Prim 或 Kruskal 算法用于找到最小生成树。
实现并优化：在实现算法时，考虑数据结构的选择以优化时间和空间复杂度。

下面是使用 Go 语言实现的一些图论算法的代码示例。

邻接表表示法：

type Graph struct {
    vertices []*Vertex
}

type Vertex struct {
    key      int
    adjacent []*Vertex
}

func (g *Graph) AddVertex(k int) {
    if contains(g.vertices, k) {
        err := fmt.Errorf("Vertex %v not added because it is an existing key", k)
        fmt.Println(err.Error())
    } else {
        g.vertices = append(g.vertices, &Vertex{key: k})
    }
}

func (g *Graph) AddEdge(from, to int) {
    // get vertex
    fromVertex := g.getVertex(from)
    toVertex := g.getVertex(to)
    // check error
    if fromVertex == nil || toVertex == nil {
        err := fmt.Errorf("Invalid edge (%v->%v)", from, to)
        fmt.Println(err.Error())
    } else if contains(fromVertex.adjacent, to) {
        err := fmt.Errorf("Existing edge (%v->%v)", from, to)
        fmt.Println(err.Error())
    } else {
        // add edge
        fromVertex.adjacent = append(fromVertex.adjacent, toVertex)
    }
}

func (g *Graph) getVertex(k int) *Vertex {
    for i, v := range g.vertices {
        if v.key == k {
            return g.vertices[i]
        }
    }
    return nil
}

func contains(s []*Vertex, k int) bool {
    for _, v := range s {
        if k == v.key {
            return true
        }
    }
    return false
}

深度优先搜索（DFS）：

func (g *Graph) DFS(startingKey int) {
    visited := make(map[int]bool)
    g.dfsHelper(startingKey, visited)
}

func (g *Graph) dfsHelper(startingKey int, visited map[int]bool) {
    visited[startingKey] = true
    vertex := g.getVertex(startingKey)
    fmt.Println(vertex.key)

    for _, v := range vertex.adjacent {
        if !visited[v.key] {
            g.dfsHelper(v.key, visited)
        }
    }
}

广度优先搜索（BFS）：

func (g *Graph) BFS(startingKey int) {
    visited := make(map[int]bool)
    queue := []*Vertex{g.getVertex(startingKey)}

    for len(queue) > 0 {
        vertex := queue[0]
        queue = queue[1:]

        if !visited[vertex.key] {
            visited[vertex.key] = true
            fmt.Println(vertex.key)

            for _, v := range vertex.adjacent {
                if !visited[v.key] {
                    queue = append(queue, v)
                }
            }
        }
    }
}

在实际应用中，你需要根据具体问题调整这些代码。例如，如果你需要处理加权图，你可能需要在你的Vertex结构中添加一个表示权重的字段，并在添加边时考虑这个权重。同样，如果你在处理有向图，添加边的方式也会有所不同。

hot-100

图论