2023-05-12：存在一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的無向連通圖，圖中的節(jié)點(diǎn)按從 0 到 n - 1 編號
2023-05-12：存在一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的無向連通圖，圖中的節(jié)點(diǎn)按從 0 到 n - 1 編號， 給你一個(gè)數(shù)組 graph 表示這個(gè)圖， 其中，graph[i] 是一個(gè)列表，由所有與節(jié)點(diǎn) i 直接相連的節(jié)點(diǎn)組成。 返回能夠訪問所有節(jié)點(diǎn)的最短路徑的長度。 你可以在任一節(jié)點(diǎn)開始和停止，也可以多次重訪節(jié)點(diǎn)，并且可以重用邊。 輸入：graph = [[1,2,3],[0],[0],[0]]。 輸出：4。
答案2023-05-12：
大體步驟如下：
1.首先，在 main 函數(shù)中調(diào)用 shortestPathLength 函數(shù)，并將圖的鄰接表 graph 作為參數(shù)傳入。
2.在 shortestPathLength 函數(shù)中，獲取圖中節(jié)點(diǎn)的個(gè)數(shù) n，使用 Floyd 算法計(jì)算所有節(jié)點(diǎn)之間的最短路徑距離，并將結(jié)果保存到 distance 二維數(shù)組中，同時(shí)初始化一個(gè) ans 變量為整型最大值。
3.接下來，初始化一個(gè) dp 數(shù)組，其中 dp[i][j] 表示當(dāng)前狀態(tài)為 i（二進(jìn)制表示），當(dāng)前在節(jié)點(diǎn) j 的情況下，能形成的最短路徑長度。同時(shí)，對于 dp 數(shù)組進(jìn)行初始化，將所有元素的值設(shè)為 -1。
4.循環(huán)遍歷每個(gè)節(jié)點(diǎn) i，從 i 節(jié)點(diǎn)出發(fā)，通過 process 函數(shù)求出訪問所有節(jié)點(diǎn)的最短路徑長度，并更新 ans 的值。
5.在 process 函數(shù)中，首先判斷當(dāng)前狀態(tài)是否已經(jīng)訪問了所有節(jié)點(diǎn)，如果是，返回 0 表示已經(jīng)完成訪問。如果 dp 數(shù)組中已有對應(yīng)狀態(tài)和當(dāng)前節(jié)點(diǎn)的最短路徑長度，則直接返回該值，避免重復(fù)計(jì)算。
6 如果上述條件都不滿足，則遍歷所有未訪問過的且與當(dāng)前節(jié)點(diǎn) cur 相鄰的節(jié)點(diǎn) next，對于這些節(jié)點(diǎn)，遞歸調(diào)用 process 函數(shù)，并記錄訪問當(dāng)前節(jié)點(diǎn) cur 和下一個(gè)節(jié)點(diǎn) next 所需的距離 distance[cur][next]，然后將其加上遞歸得到的 nextAns 值，更新 ans 的值。
7.最后，將計(jì)算出的最短路徑長度 ans 保存到 dp 數(shù)組中，并返回該值。在主函數(shù)中輸出 ans 的值即為能夠訪問所有節(jié)點(diǎn)的最短路徑的長度。
時(shí)間復(fù)雜度：本算法中使用了 Floyd 算法計(jì)算所有節(jié)點(diǎn)之間的最短路徑，其時(shí)間復(fù)雜度為 O(n^3)；同時(shí)，使用動(dòng)態(tài)規(guī)劃求解當(dāng)前狀態(tài)下訪問所有節(jié)點(diǎn)的最短路徑長度，需要遍歷狀態(tài)空間和鄰接表，時(shí)間復(fù)雜度為 O(2^n * n^2)。因此，總的時(shí)間復(fù)雜度為 O(n^3 + 2^n * n^2)。
空間復(fù)雜度：本算法中使用了一個(gè)距離矩陣 distance 數(shù)組來存儲(chǔ)節(jié)點(diǎn)之間的最短路徑距離，其空間復(fù)雜度為 O(n^2)；同時(shí)，使用了一個(gè) dp 數(shù)組來記錄狀態(tài)和節(jié)點(diǎn)的最短路徑長度，其空間復(fù)雜度也是 O(2^n * n)。因此，總的空間復(fù)雜度為 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];
????//?初始化認(rè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)的過程
????//?枚舉每個(gè)跳板
????//?注意!?跳板要最先枚舉，然后是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?:?所有已經(jīng)走過點(diǎn)的狀態(tài)
//?0?1?2?3?4?5
//?int
//????????5?4?3?2?1?0
//????????0?0?1?1?0?1
//?cur?:?當(dāng)前所在哪個(gè)城市！
//?n?:?一共有幾座城
//?返回值?:?從此時(shí)開始，逛掉所有的城市，至少還要走的路，返回！
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;
}
福大大架構(gòu)師每日一題
java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號
