2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号，给你一个数组 graph 表示这个图，其中，graph[i] 是一个列表，由所有与节点 i-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号，给你一个数组 graph 表示这个图，其中，graph[i] 是一个列表，由所有与节点 i。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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)
}

2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号，给你一个数组 graph 表示这个图，其中，graph[i] 是一个列表，由所有与节点 i

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;
}

2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号，给你一个数组 graph 表示这个图，其中，graph[i] 是一个列表，由所有与节点 i 文章来源地址https://www.toymoban.com/news/detail-441245.html

到了这里，关于2023-05-12：存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号，给你一个数组 graph 表示这个图，其中，graph[i] 是一个列表，由所有与节点 i的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！