实验要求
编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能：
- 建立如教材图7.所示的有向图G的邻接矩阵，并分别输出顶点表和邻接矩阵。
- 在图G的邻接矩阵存储表示基础上，实现深度优先遍历算法，输出从顶点V1开始的深度优先遍历序列。
- 实现广度优先遍历算法，输出从顶点V1开始的广度优先遍历序列。
- 建立如教材图7.16(a)所示的无向带权图G的邻接矩阵，实现普里姆算法，输出从顶点V1出发的最小生成树（按照求解出的边的顺序）
程序代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define VRtype int
#define Status int
#define VertexType int
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef struct ArcCell {
VRtype adj;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vex[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
int kind;
}MGraph;
bool visited[MAX_VERTEX_NUM + 5];
Status CreatUDN(MGraph &G)
{
printf("请输入图的顶点个数和边的个数\n");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf("%d %d\n",G.vexnum,G.arcnum);
for(int i = 1; i<=G.vexnum;++i) G.vex[i] = i;
for(int i = 1; i<=G.vexnum;++i){
for(int j = 1; j<=G.vexnum;++j){
G.arcs[i][j] = {INFINITY};
}
}
printf("请输入%d条边的信息，格式为起点，终点，权值\n",G.arcnum);
for(int i = 0; i<G.arcnum ;++i){
int v1,v2,w;
scanf("%d %d %d",&v1,&v2,&w);
G.arcs[v1][v2].adj = w;
G.arcs[v2][v1] = G.arcs[v1][v2];
}
return OK;
}
Status CreatGraph( MGraph &G)
{
printf("请输入图的种类 3代表无向网\n");
scanf("%d",&G.kind);
printf("%d\n",G.kind);
switch(G.kind){
//case DG: return CreateDG(G);
//case DN: return CreateDN(G);
// case UGD: return CreatUDG(G);
case UDN: return CreatUDN(G);
default : return ERROR;
}
}
void DFS(MGraph G, int v)
{
visited[v] = TRUE;
printf("%d ",v);
for(int i = 1; i <= G.vexnum;++i){
if(G.arcs[v][i].adj != INFINITY && !visited[i])
DFS(G,i);
}
}
void DFSTraverse(MGraph G)
{
for(int i = 1; i<=G.vexnum;++i) visited[i] = false;
for(int i = 1; i<=G.vexnum;++i)
if(!visited[i]) DFS(G,i);
printf("\n");
}
void BFSTraverse(MGraph G)
{
for(int i = 1; i<=G.vexnum;++i) visited[i] =FALSE;
int Queue[1000],fro = 0,rear = 0;
for(int i = 1; i<=G.vexnum ;++i){
if(!visited[i]){
visited[i] = TRUE;
printf("%d ",i);
}
Queue[rear++] = i;
while(fro != rear){
int temp = Queue[fro++];
for(int k = 1;k<=G.vexnum;++k){
if(G.arcs[temp][k].adj != INFINITY && !visited[k]){
visited[k] = TRUE;
// shuchu
printf("%d ",k);
Queue[rear++] = k;
}
}
}
}
printf("\n");
}
void MiniSpanTree_PRIM(MGraph G, VertexType u)
{
printf("最小生成树的边生成顺序为：\n");
struct {
VertexType adjvex;
VRtype lowcost;
}closedge[MAX_VERTEX_NUM];
int k = u;
for( int j = 1; j<=G.vexnum; ++j){
if(j != k){
closedge[j].adjvex = k;
closedge[j].lowcost = G.arcs[k][j].adj;
//printf("%d %d %d\n",closedge[j].adjvex,j,closedge[j].lowcost);
}
}
closedge[k].lowcost = 0;
for(int i = 2; i<=G.vexnum;++i){
//findmin
int id = 0,cost = INFINITY;
for(int l = 1; l<=G.vexnum;++l){
//printf("%d %d %d \n",l,closedge[l].lowcost,cost);
if(closedge[l].lowcost!= 0 &&closedge[l].lowcost < cost ){
id = l;
cost = closedge[l].lowcost;
}
}
//printf("id %d\n",id);
k = id;
printf("%d %d\n",closedge[k].adjvex, k);
closedge[k].lowcost = 0;
for(int j = 1; j<=G.vexnum ;++j){
if(G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost != 0 ){
closedge[j].adjvex = G.vex[k];
closedge[j].lowcost = G.arcs[k][j].adj;
}
}
}
}
void output(MGraph G)
{
printf("顶点表为\n");
for(int i =1; i<=G.vexnum;++i){
printf("%d %d\n",i,G.vexnum);
}
printf("邻接矩阵为\n");
for(int i = 1; i<=G.vexnum;++i){
for(int j = 1; j<=G.vexnum;++j){
if(G.arcs[i][j].adj != INFINITY){
printf("%d ",G.arcs[i][j].adj);
}else{
printf("# ");
}
}
printf("\n");
}
}
int main()
{
freopen("in.txt","r",stdin);
MGraph G;
CreatGraph(G);
output(G);
DFSTraverse(G);
BFSTraverse(G);
MiniSpanTree_PRIM(G,1);
return 0;
}运行结果
数据
3
6 10
1 2 6
1 4 5
1 3 1
2 3 5
3 4 5
2 5 3
5 3 6
6 4 2
3 6 4
5 6 6