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

template class MGraph {

public:

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

MGraph(T a[],int n,int e,int h); void DFS(int v); void BFS(int v); void Prim(MGraph G);

void Kruskal(VEdge E[],int n,int e); int vNum,arcNum;

int arcs[MAXSIZE][MAXSIZE];//用于储存权值的数组 int arc[MAXSIZE][MAXSIZE]; private:

T vertex[MAXSIZE]; };

template //构造带权值的有向图 MGraph::MGraph(T a[],int n,int e,int h) {

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

for(k=0;k

for(j=0;j

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<

//普利姆算法

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;//初始化U={vo} for(int i=1;i

int k=mininum(G,lowcost);//求下一个边权值最小的邻接点 cout<<'V'<

for(int j=0;j

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

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

//克鲁斯卡尔算法 template

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

int k=0,i,j;

for(i=0;i

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