图的深度优先和广度优先搜索的算法和最小生成树的程序？

Question

如题所述

Answer 1

最小生成树：
#include<iostream>
using namespace std;
#define inf 99999;

template<class Type>
Type Prim(int n,Type **c){
Type lowcost[n],sum=0;
// int closest[n];
bool s[n];
s[1]=true;
for(int i=2;i<=n;i++){
lowcost[i]=c[1][i];
// closest[i]=1;
s[i]=false;
}
for(int i=1;i<n;i++){
Type min=inf;
int j=1;
for(int k=2;k<=n;k++)
if((lowcost[k]<min)&&(!s[k])){
min=lowcost[k];
j=k;
}
// cout<<j<<' '<<closest[j]<<endl;
sum+=lowcost[j];
s[j]=true;
for(int k=2;k<=n;k++){
if((c[j][k]<lowcost[k])&&(!s[k])){
lowcost[k]=c[j][k];
// closest[k]=j;
}
}
}
return sum;
}
int main(){
int T,n,m,**c;
cin>>T;
while(T--){
cin>>n>>m;
c=new int*[n+1];
for(int i=1;i<=n;i++){
c[i]=new int[n+1];
for(int j=1;j<=n;j++)
c[i][j]=inf;
}
while(m--){
int x,y,w;
cin>>x>>y>>w;
c[x][y]=w;
}
cout<<Prim(n,c)<<endl;
}
// system("pause");
return 0;
}

Answer 2

分太少了。。。

Answer 3

node* creategraph()//建立邻接表，完成无向图的输入
{
int l,m,n;
bool g;
cout<<"请输入节点数: ";
cin>>n;
node *adjacencylist=new node[n+1];//动态分配节点数组内存
adjacencylist[0].data=n;//0地址存放的为节点数
adjacencylist[0].next=NULL;
for(int i=1;i<=n;i++)//给各顶点域赋初值
{
adjacencylist[i].data=0;
adjacencylist[i].next=NULL;
adjacencylist[i].sign=f;//表示未遍历
}
cout<<"请依次输入各条边的始点和尾点:（以0表示结束）"<<endl;
cin>>l;
if(l!=0)//判断输入边是否结束
g=t;
while(g==t)
{
cin>>m;
if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判断输入顶点是否正确
{
node *p,*q,*top;
p=(node *)new(node);//分配边的一个顶点内存
p->data=m;
p->next=NULL;
if(adjacencylist[l].next==NULL)//为每个节点创建邻接链表
adjacencylist[l].next=p;
else
{
top=adjacencylist[l].next;
while(top->next!=NULL)
top=top->next;
top->next=p;
}
adjacencylist[l].data++;//统计邻接点的个数
q=(node *)new(node);//分配边的另一个顶点内存
q->data=l;
q->next=NULL;
if(adjacencylist[m].next==NULL)//构建邻接表
adjacencylist[m].next=q;
else
{
top=adjacencylist[m].next;
while(top->next!=NULL)
top=top->next;
top->next=q;
}
adjacencylist[m].data++;//统计邻接点的个数
}
else
cout<<"边"<<l<<"--"<<m<<"输入错误！"<<endl;//错误输入标识
cin>>l;
if(l==0)//边的输入结束
g=f;
}
return adjacencylist;//返回邻接表
};