北邮数据结构实验第二次实验图

vNum=n; arcNum=e;

for(k=0;k

for(j=0;j

for(int i=0;i

for(int j=0;j

}

cout<<\ 请输入连通的两顶点下标 ( 弧头 - 弧尾）及弧的权值 (<1000) ：for(int i=0;i

arcs[i][i]=0;

}

for(k=0;k

cin>>i>>j>>l; arcs[i][j]=l; arc[i][j]=1;

}

}

template // 带权值的无向图

MGraph::MGraph(T a[],int n,int e)

{

int i,j,k,l; vNum=n; arcNum=e;

for(k=0;k

for(j=0;j

cout<<\

请输入连通的两顶点下标及边的权值

(<1000)

： \

for(k=0;k

{

cin>>i>>j>>l; arcs[i][j]=l; arcs[j][i]=arcs[i][j];

arc[i][j]=1;

arc[j][i]=arc[i][j];

}

\

}

// 深度广度遍历

int visited[MAXSIZE]={false}; template

void MGraph::DFS(int v) {

cout<

for(int j=0;j

if(arc[v][j]==1&&!visited[j])

DFS(j);

}

int visit[MAXSIZE]={false}; template

void MGraph::BFS(int v) {

int queue[MAXSIZE]; int f=0,r=0;

cout<

v=queue[++f];

for(int j=0;j

if(arc[v][j]==1&&!visit[j]) {

cout<

queue[++r]=j; }

}

}

}

// 普利姆算法 int adjvex[MAXSIZE]; int lowcost[MAXSIZE]; int MAX=10000; template

int mininum(MGraph G,int a[]) {

int min=MAX; int k=0;

for(int i=0;i

if(a[i]!=0&&a[i]

min=a[i]; k=i;

}

}

return k;

}

template

void MGraph:: Prim(MGraph G) {

for(int i=0;i

adjvex[i]=0;

lowcost[i]=G.arcs[0][i];

}

lowcost[0]=0;// {

int k=mininum(G,lowcost);// lowcost[k]=0;

for(int j=0;j

if(lowcost[j]!=0&&G.arcs[k][j]

lowcost[j]=G.arcs[k][j]; adjvex[j]=k;

}

}

} }

求下一个边权值最小的邻接点

寻找 U-{V-U} 中边权值最小的顶点

初始化 U={vo}

for(int i=1;i

cout<<'V'<

// 克鲁斯卡尔算法 template

void GenSortEdge(MGraph G,VEdge E[])// {

int k=0,i,j;

获取 EdgeList

for(i=0;i

边赋值

for(j=i;j

if(G.arcs[i][j]!=MAX) {

E[k].fromV=i; E[k].endV=j;

E[k].weight=G.arcs[i][j]; k++;

}

for(i=0;i

{

for(j=i+1;jE[j].weight)

{

VEdge t=E[i]; E[i]=E[j]; E[j]=t;

}

}

}

const int MAX_VERTEXT=20; template

void MGraph:: Kruskal(VEdge E[],int n,int e) {

int vset[MAX_VERTEXT]; for(int i=0;i

int k=0,j=0; while(k

int m=E[j].fromV,n=E[j].endV;

int sn1=vset[m];//m

所属的集合 int sn2=vset[n];//n 所属的集合

if(sn1!=sn2) {

cout<<'V'<

for(int i=0;i

if(vset[i]==sn2)//

集合编号为 sn2 的全部改为vset[i]=sn1;

}

} j++;

sn1