核心：贪心思想 只能用于无向图 prim和dijkstra异同
在这里插入prim代码： #include<iostream> #include<cstring> #include<algorithm> #define NIL -1 #define INF 0x3f3f3f3f using namespace std; const int white=0,gray=1,black=2,maxn=1e3+10; int n,color[maxn],dis[maxn],parent[maxn],graph[maxn][maxn]; int prim() { for(int i=0;i<n;i++){color[i]=white;dis[i]=INF;parent[i]=NIL;} dis[0]=0,color[0]=gray; while(1){ int minv=INF,u=-1; for(int i=0;i<n;i++){ if(color[i]!=black&&dis[i]<minv){ minv=dis[i]; u=i; } } color[u]=black; if(u==-1)break; for(int v=0;v<n;v++){ if(color[v]!=black&&graph[u][v]!=NIL){ if(graph[u][v]<dis[v]){ dis[v]=graph[u][v]; color[v]=gray; parent[v]=u; } } } } int sum=0; for(int i=0;i<n;i++){ if(parent[i]!=NIL)sum+=graph[i][parent[i]]; } return sum; } int main() { memset(graph,INF,sizeof(graph)); cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>graph[i][j]; } } cout<<prim()<<endl; return 0; } 代码片