数据结构-图的课后习题（2）

题目要求：

对于下面的这个无向网，给出：

1.“深度优先搜索序列”（从V1开始）

2.“广度优先序列”（从V1开始）

3.“用Prim算法求最小生成树”

代码实现：

1.深度优先搜索：

代码部分：

#include<stdio.h>
#include<malloc.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(k=0;k<G->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(i=0;i<G->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(i=0;i<G->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(v=0;v<G->vexnum;v++){visit[v] = 0;}for(v=0;v<G->vexnum;v++){if(visit[v] == 0){DFS(G,v,visit);}}
}int main()
{ALGraph G;CreateALGraph(&G);DFSTraverse(&G);return 0;
}

验证：

2.广度优先搜索：

代码部分：

#include<stdio.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(k=0;k<G->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(i=0;i<G->vexnum;i++){scanf("%c%c",&G->vertex[i][0],&G->vertex[i][1]);}getchar();for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j] = 0;printf("请输入{%d}条边,格式(v1 v2 权值).\n",G->arcnum);for(i=0;i<G->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->vexnum+1],visit[G->vexnum];int i,u,w;for(i=0;i<G->vexnum;i++)visit[i] = 0;int front = 0,rear = 0;for(i=0;i<G->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 = (rear+1) % (G->vexnum+1);while(front != rear){u = Q[front];front = (front+1) % (G->vexnum+1);for(w=0;w<G->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 = (rear+1) % (G->vexnum+1);}}}}}
}int main()
{MGraph G;CreateMGraph(&G);BFSTraverse(&G);return 0;
}

验证：

3.用Prim算法求得最小生成树：

代码部分：

#include<stdio.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(k=0;k<G->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(i=0;i<G->vexnum;i++){scanf("%c%c",&G->vertex[i][0],&G->vertex[i][1]);}getchar();for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j] = 999;printf("请输入{%d}条边,格式(v1 v2 权值).\n",G->arcnum);for(i=0;i<G->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,p=1,min=999;for(j=0;j<G->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(j=0;j<G->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(i=1;i<G->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(j=0;j<G->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;
}

验证：