2023-05-12:存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号

2023-05-12:存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号,
给你一个数组 graph 表示这个图,
其中,graph[i] 是一个列表,由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。
你可以在任一节点开始和停止,也可以多次重访节点,并且可以重用边。
输入:graph = [[1,2,3],[0],[0],[0]]。
输出:4。

答案2023-05-12:

大体步骤如下:

1.首先,在 main 函数中调用 shortestPathLength 函数,并将图的邻接表 graph 作为参数传入。

2.在 shortestPathLength 函数中,获取图中节点的个数 n,使用 Floyd 算法计算所有节点之间的最短路径距离,并将结果保存到 distance 二维数组中,同时初始化一个 ans 变量为整型最大值。

3.接下来,初始化一个 dp 数组,其中 dp[i][j] 表示当前状态为 i(二进制表示),当前在节点 j 的情况下,能形成的最短路径长度。同时,对于 dp 数组进行初始化,将所有元素的值设为 -1。

4.循环遍历每个节点 i,从 i 节点出发,通过 process 函数求出访问所有节点的最短路径长度,并更新 ans 的值。

5.在 process 函数中,首先判断当前状态是否已经访问了所有节点,如果是,返回 0 表示已经完成访问。如果 dp 数组中已有对应状态和当前节点的最短路径长度,则直接返回该值,避免重复计算。

6 如果上述条件都不满足,则遍历所有未访问过的且与当前节点 cur 相邻的节点 next,对于这些节点,递归调用 process 函数,并记录访问当前节点 cur 和下一个节点 next 所需的距离 distance[cur][next],然后将其加上递归得到的 nextAns 值,更新 ans 的值。

7.最后,将计算出的最短路径长度 ans 保存到 dp 数组中,并返回该值。在主函数中输出 ans 的值即为能够访问所有节点的最短路径的长度。

时间复杂度:本算法中使用了 Floyd 算法计算所有节点之间的最短路径,其时间复杂度为 O(n^3);同时,使用动态规划求解当前状态下访问所有节点的最短路径长度,需要遍历状态空间和邻接表,时间复杂度为 O(2^n * n^2)。因此,总的时间复杂度为 O(n^3 + 2^n * n^2)。

空间复杂度:本算法中使用了一个距离矩阵 distance 数组来存储节点之间的最短路径距离,其空间复杂度为 O(n^2);同时,使用了一个 dp 数组来记录状态和节点的最短路径长度,其空间复杂度也是 O(2^n * n)。因此,总的空间复杂度为 O(n^2 + 2^n * n)。

go语言完整代码如下:

package main

import (
    "fmt"
    "math"
)

func shortestPathLength(graph [][]int) int {
    n := len(graph)
    distance := floyd(n, graph)
    ans := math.MaxInt32
    dp := make([][]int, 1<<n)
    for i := 0; i < (1 << n); i++ {
        dp[i] = make([]int, n)
        for j := 0; j < n; j++ {
            dp[i][j] = -1
        }
    }
    for i := 0; i < n; i++ {
        ans = min(ans, process(1<<i, i, n, distance, dp))
    }
    return ans
}

func floyd(n int, graph [][]int) [][]int {
    distance := make([][]int, n)
    for i := 0; i < n; i++ {
        distance[i] = make([]int, n)
        for j := 0; j < n; j++ {
            distance[i][j] = math.MaxInt32
        }
    }
    for i := 0; i < n; i++ {
        distance[i][i] = 0
    }
    for cur := 0; cur < n; cur++ {
        for _, next := range graph[cur] {
            distance[cur][next] = 1
            distance[next][cur] = 1
        }
    }
    for jump := 0; jump < n; jump++ {
        for from := 0; from < n; from++ {
            for to := 0; to < n; to++ {
                if distance[from][jump] != math.MaxInt32 && distance[jump][to] != math.MaxInt32 &&
                    distance[from][to] > distance[from][jump]+distance[jump][to] {
                    distance[from][to] = distance[from][jump] + distance[jump][to]
                }
            }
        }
    }
    return distance
}

func process(status, cur, n int, distance, dp [][]int) int {
    if status == (1<<n)-1 {
        return 0
    }
    if dp[status][cur] != -1 {
        return dp[status][cur]
    }
    ans := math.MaxInt32
    for next := 0; next < n; next++ {
        if status&(1<<next) == 0 && distance[cur][next] != math.MaxInt32 {
            nextAns := process(status|(1<<next), next, n, distance, dp)
            if nextAns != math.MaxInt32 {
                ans = min(ans, distance[cur][next]+nextAns)
            }
        }
    }
    dp[status][cur] = ans
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    graph := [][]int{{1, 2, 3}, {0}, {0}, {0}}
    ans := shortestPathLength(graph)
    fmt.Println(ans)
}

在这里插入图片描述

rust语言完整代码如下:

fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 {
    let n = graph.len();
    let distance = floyd(n, &graph);
    let mut ans = std::i32::MAX;
    let mut dp = vec![vec![-1; n]; 1 << n];
    for i in 0..(1 << n) {
        for j in 0..n {
            dp[i][j] = -1;
        }
    }
    for i in 0..n {
        ans = ans.min(process(1 << i, i, n, &distance, &mut dp));
    }
    return ans;
}

fn floyd(n: usize, graph: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut distance = vec![vec![std::i32::MAX; n]; n];
    // 初始化认为都没路
    for i in 0..n {
        for j in 0..n {
            distance[i][j] = std::i32::MAX;
        }
    }
    // 自己到自己的距离为0
    for i in 0..n {
        distance[i][i] = 0;
    }
    // 支持任意有向图,把直接边先填入
    for cur in 0..n {
        for &next in graph[cur].iter() {
            distance[cur][next as usize] = 1;
            distance[next as usize][cur] = 1;
        }
    }
    // O(N^3)的过程
    // 枚举每个跳板
    // 注意! 跳板要最先枚举,然后是from和to
    for jump in 0..n {
        for from in 0..n {
            for to in 0..n {
                if distance[from][jump] != std::i32::MAX
                    && distance[jump][to] != std::i32::MAX
                    && distance[from][to] > distance[from][jump] + distance[jump][to]
                {
                    distance[from][to] = distance[from][jump] + distance[jump][to];
                }
            }
        }
    }
    return distance;
}

// status : 所有已经走过点的状态
// 0 1 2 3 4 5
// int
//        5 4 3 2 1 0
//        0 0 1 1 0 1
// cur : 当前所在哪个城市!
// n : 一共有几座城
// 返回值 : 从此时开始,逛掉所有的城市,至少还要走的路,返回!
fn process(
    status: i32,
    cur: usize,
    n: usize,
    distance: &Vec<Vec<i32>>,
    dp: &mut Vec<Vec<i32>>,
) -> i32 {
    // 5 4 3 2 1 0
    // 1 1 1 1 1 1
    // 1 << 6 - 1
    if status == (1 << n) - 1 {
        return 0;
    }
    if dp[status as usize][cur] != -1 {
        return dp[status as usize][cur];
    }
    let mut ans = std::i32::MAX;
    // status:
    // 5 4 3 2 1 0
    // 0 0 1 0 1 1
    // cur : 0
    // next : 2 4 5
    for next in 0..n {
        if (status & (1 << next)) == 0 && distance[cur][next] != std::i32::MAX {
            let next_ans = process(status | (1 << next), next, n, distance, dp);
            if next_ans != std::i32::MAX {
                ans = ans.min(distance[cur][next] + next_ans);
            }
        }
    }
    dp[status as usize][cur] = ans;
    return ans;
}

fn main() {
    let graph = vec![vec![1, 2, 3], vec![0], vec![0], vec![0]];
    let ans = shortest_path_length(graph);
    println!("{}", ans);
}

在这里插入图片描述

c语言完整代码如下:


#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15, INF = 0x3f3f3f3f;

int n;
int dist[N][N], dp[1 << N][N];

int floyd(vector<vector<int>>& graph)
{
    n = graph.size();
    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < n; i++)
        for (auto j : graph[i])
            dist[i][j] = 1;

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    return 0;
}

int dfs(int status, int cur)
{
    if (status == (1 << n) - 1)
        return 0;

    if (dp[status][cur] != -1)
        return dp[status][cur];

    int ans = INF;

    for (int next = 0; next < n; next++)
        if ((status & (1 << next)) == 0 && dist[cur][next] != INF)
        {
            int nextAns = dfs(status | (1 << next), next);
            if (nextAns != INF)
                ans = min(ans, dist[cur][next] + nextAns);
        }

    return dp[status][cur] = ans;
}

int shortestPathLength(vector<vector<int>>& graph) {
    memset(dp, -1, sizeof dp);
    floyd(graph);

    int ans = INF;
    for (int i = 0; i < n; i++)
        ans = min(ans, dfs(1 << i, i));
    return ans;
}

int main()
{
    vector<vector<int>> graph = { {1,2,3},{0},{0},{0} };
    cout << shortestPathLength(graph) << endl;

    return 0;
}

在这里插入图片描述

c++语言完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 15
#define INF 0x3f3f3f3f

int n;
int dist[N][N], dp[1 << N][N];

void floyd(int** graph, int graphSize, int* graphColSize)
{
    n = graphSize;
    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < graphColSize[i]; j++)
            dist[i][graph[i][j]] = 1;

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = dist[i][j] < dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];
}

int dfs(int status, int cur)
{
    if (status == (1 << n) - 1)
        return 0;

    if (dp[status][cur] != -1)
        return dp[status][cur];

    int ans = INF;

    for (int next = 0; next < n; next++)
        if ((status & (1 << next)) == 0 && dist[cur][next] != INF)
        {
            int nextAns = dfs(status | (1 << next), next);
            if (nextAns != INF)
                ans = ans < dist[cur][next] + nextAns ? ans : dist[cur][next] + nextAns;
        }

    return dp[status][cur] = ans;
}

int shortestPathLength(int** graph, int graphSize, int* graphColSize) {
    memset(dp, -1, sizeof dp);
    floyd(graph, graphSize, graphColSize);

    int ans = INF;
    for (int i = 0; i < n; i++)
        ans = ans < dfs(1 << i, i) ? ans : dfs(1 << i, i);
    return ans;
}

int main()
{
    int graphSize = 4;
    int graphColSize[] = { 3, 1, 1, 1 };
    int** graph = (int**)malloc(sizeof(int*) * graphSize);
    for (int i = 0; i < graphSize; i++)
    {
        graph[i] = (int*)malloc(sizeof(int) * graphColSize[i]);
        memcpy(graph[i], (int[]) { 0 }, sizeof(int)* graphColSize[i]);
    }
    graph[0][0] = 1;
    graph[0][1] = 2;
    graph[0][2] = 3;

    printf("%d\n", shortestPathLength(graph, graphSize, graphColSize));

    for (int i = 0; i < graphSize; i++)
        free(graph[i]);
    free(graph);

    return 0;
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商