织梦做的网站在手机上显示,做网站推广logo,青岛网站建设首选营销吧系统,机械外发加工网题目要求#xff1a;
对于下面的这个无向网#xff0c;给出#xff1a;
1.“深度优先搜索序列”#xff08;从V1开始#xff09;
2.“广度优先序列”#xff08;从V1开始#xff09;
3.“用Prim算法求最小生成树” 代码实现#xff1a;
1.深度优先搜索#xff1a…题目要求
对于下面的这个无向网给出
1.“深度优先搜索序列”从V1开始
2.“广度优先序列”从V1开始
3.“用Prim算法求最小生成树” 代码实现
1.深度优先搜索
代码部分
#includestdio.h
#includemalloc.h
#define MAX 100typedef struct ArcNode{int adjvex;int weight;struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{char vertex[2];ArcNode *firstarc;
}VNode;
typedef VNode AdjList[MAX];
typedef struct ALGraph{AdjList adjlist;int vexnum,arcnum;
}ALGraph;int LocateVerTex(ALGraph *G,char *v)
{int k;for(k0;kG-vexnum;k)if(G-adjlist[k].vertex[0] v[0] G-adjlist[k].vertex[1] v[1])return k;return -1;
}void CreateALGraph(ALGraph *G)
{int i,adj1,adj2;int weight;char v1[2],v2[2];ArcNode *tmp NULL;printf(请输入顶点个数和边数:\n);scanf(%d %d,G-vexnum,G-arcnum);getchar();printf(请输入{%d}个顶点\n,G-vexnum);for(i0;iG-vexnum;i){scanf(%c%c,G-adjlist[i].vertex[0],G-adjlist[i].vertex[1]);G-adjlist[i].firstarc NULL;}getchar();printf(请输入{%d}条边,格式(v1 v2 权值).\n,G-arcnum);for(i0;iG-arcnum;i){scanf(%c%c %c%c %d,v1[0],v1[1],v2[0],v2[1],weight);getchar();adj1 LocateVerTex(G,v1);adj2 LocateVerTex(G,v2);if(adj1 -1 || adj2 -1){printf(失败.\n);i i - 1;continue;}else{tmp (ArcNode*)malloc(sizeof(ArcNode));tmp-adjvex adj2;tmp-weight weight;tmp-nextarc G-adjlist[adj1].firstarc;G-adjlist[adj1].firstarc tmp;tmp (ArcNode*)malloc(sizeof(ArcNode));tmp-adjvex adj1;tmp-weight weight;tmp-nextarc G-adjlist[adj2].firstarc;G-adjlist[adj2].firstarc tmp;printf(成功.\n);}}
}void DFS(ALGraph *G,int v,int *visit)
{ int w;ArcNode *tmp NULL;visit[v] 1;printf(访问顶点:{%c%c}.\n,G-adjlist[v].vertex[0],G-adjlist[v].vertex[1]);tmp G-adjlist[v].firstarc;while(tmp){w tmp-adjvex;if(visit[w] 0){DFS(G,w,visit);}tmp tmp-nextarc;}
}void DFSTraverse(ALGraph *G)
{int visit[G-vexnum];int v;for(v0;vG-vexnum;v){visit[v] 0;}for(v0;vG-vexnum;v){if(visit[v] 0){DFS(G,v,visit);}}
}int main()
{ALGraph G;CreateALGraph(G);DFSTraverse(G);return 0;
}
验证 2.广度优先搜索
代码部分
#includestdio.h
#define MAX 100
typedef struct MGraph{char vertex[MAX][2];int arcs[MAX][MAX];int vexnum,arcnum;
}Mgraph;
int LocateVerTex(MGraph *G,char *v)
{int k;for(k0;kG-vexnum;k){if(G-vertex[k][0] v[0] G-vertex[k][1] v[1])return k;}return -1;
}void CreateMGraph(MGraph *G)
{int i,j,adj1,adj2;int weight;char v1[2],v2[2];printf(请输入顶点个数和边数:\n);scanf(%d %d,G-vexnum,G-arcnum);getchar();printf(请输入{%d}个顶点\n,G-vexnum);for(i0;iG-vexnum;i){scanf(%c%c,G-vertex[i][0],G-vertex[i][1]);}getchar();for(i0;iG-vexnum;i)for(j0;jG-vexnum;j)G-arcs[i][j] 0;printf(请输入{%d}条边,格式(v1 v2 权值).\n,G-arcnum);for(i0;iG-arcnum;i){scanf(%c%c %c%c %d,v1[0],v1[1],v2[0],v2[1],weight);getchar();adj1 LocateVerTex(G,v1);adj2 LocateVerTex(G,v2);if(adj1 -1 || adj2 -1){printf(失败.\n);i i - 1;continue;}else{G-arcs[adj1][adj2] weight;G-arcs[adj2][adj1] weight;printf(成功.\n);}}
}void BFSTraverse(MGraph *G)
{int Q[G-vexnum1],visit[G-vexnum];int i,u,w;for(i0;iG-vexnum;i)visit[i] 0;int front 0,rear 0;for(i0;iG-vexnum;i){if(visit[i] 0){visit[i] 1;printf(输出顶点:{%c%c}\n,G-vertex[i][0],G-vertex[i][1]);Q[rear] i;rear (rear1) % (G-vexnum1);while(front ! rear){u Q[front];front (front1) % (G-vexnum1);for(w0;wG-vexnum;w){if(G-arcs[u][w] ! 0 visit[w] 0){visit[w] 1;printf(输出顶点:{%c%c}\n,G-vertex[w][0],G-vertex[w][1]);Q[rear] w;rear (rear1) % (G-vexnum1);}}}}}
}int main()
{MGraph G;CreateMGraph(G);BFSTraverse(G);return 0;
}
验证 3.用Prim算法求得最小生成树
代码部分
#includestdio.h
#define MAX 100
typedef struct MGraph{char vertex[MAX][2];int arcs[MAX][MAX];int vexnum,arcnum;
}Mgraph;
typedef struct closedge{char vertex[MAX][2];int lowcost[MAX];
}closedge;int LocateVerTex(MGraph *G,char *v)
{int k;for(k0;kG-vexnum;k){if(G-vertex[k][0] v[0] G-vertex[k][1] v[1])return k;}return -1;
}void CreateMGraph(MGraph *G)
{int i,j,adj1,adj2;int weight;char v1[2],v2[2];printf(请输入顶点个数和边数:\n);scanf(%d %d,G-vexnum,G-arcnum);getchar();printf(请输入{%d}个顶点\n,G-vexnum);for(i0;iG-vexnum;i){scanf(%c%c,G-vertex[i][0],G-vertex[i][1]);}getchar();for(i0;iG-vexnum;i)for(j0;jG-vexnum;j)G-arcs[i][j] 999;printf(请输入{%d}条边,格式(v1 v2 权值).\n,G-arcnum);for(i0;iG-arcnum;i){scanf(%c%c %c%c %d,v1[0],v1[1],v2[0],v2[1],weight);getchar();adj1 LocateVerTex(G,v1);adj2 LocateVerTex(G,v2);if(adj1 -1 || adj2 -1){printf(失败.\n);i i - 1;continue;}else{G-arcs[adj1][adj2] weight;G-arcs[adj2][adj1] weight;printf(成功.\n);}}
}int MiniMum(MGraph *G,closedge *cd)
{int j,p1,min999;for(j0;jG-vexnum;j){if(cd-lowcost[j] ! 0 cd-lowcost[j] min){min cd-lowcost[j];p j;}}return p;
}void MiniSpanTree_PRIM(MGraph *G,char *u)
{closedge cd;int i,j,k;k LocateVerTex(G,u);for(j0;jG-vexnum;j){if(j ! k){cd.vertex[j][0] u[0];cd.vertex[j][1] u[1];cd.lowcost[j] G-arcs[k][j];}}cd.lowcost[k] 0;printf(最小代价生成树的各条边为:\n);for(i1;iG-vexnum;i){k MiniMum(G,cd);printf(输出边%c%c-%c%c,权值为:{%d}\n,cd.vertex[k][0],cd.vertex[k][1],G-vertex[k][0],G-vertex[k][1],cd.lowcost[k]);cd.lowcost[k] 0;for(j0;jG-vexnum;j){if(G-arcs[k][j] cd.lowcost[j]){cd.vertex[j][0] G-vertex[k][0];cd.vertex[j][1] G-vertex[k][1];cd.lowcost[j] G-arcs[k][j];}}}
}int main()
{char original_vertex[2]{V,1};MGraph G;CreateMGraph(G);MiniSpanTree_PRIM(G,original_vertex);return 0;
}
验证
