#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#define INFINITY 2147483647
#define MAX 20
#define OK 1
#define ERROR 0
//结构类型定义部分
typedef char VertexType;
typedef int Status;
typedef int VRType;
typedef enum { DG, DN, UDG, UDN }GrapghKind;
typedef struct {
VertexType vexs[MAX];
VRType arcs[MAX][MAX];
int vexnum;
int arcnum;
GrapghKind kind;
}MGraph;
typedef struct {
VertexType adivex;
VRType lowcost;
}edge;
MGraph G[4];
int visited[MAX];
Status(*VisiFunc)(MGraph G, int v);
edge closedge[MAX];
int LocateVex(MGraph G, VertexType v);
Status CreateDG(MGraph &G);
Status CreateUDG(MGraph &G);
Status CreateDN(MGraph &G);
Status CreateUDN(MGraph &G);
Status PrintVex(MGraph G, int v);
int FirstAdjVex(MGraph G, int v, int w);
int NextADjvex(MGraph G, int v, int w);
void DFS(MGraph G, int v);
void DFSTraverse(MGraph G, Status(*Visit) (MGraph G, int v));
void BFSTraverse(MGraph G, Status(*Visit) (MGraph G, int v));
Status ShortestPath_DIJ(MGraph G, int V0, int P[][MAX], int *D);
//2
Status PrintShortestPath(MGraph G, int V0, int P[][MAX], int *D);
int mininum(edge *closedge, int v);
Status MiniSpanTree_PRIM(MGraph G, int v0);
//函数定义部分
int LocateVex(MGraph G, VertexType v) {
int i = 0;
while ((v != G.vexs[i]) && (i < G.vexnum)) i++;
return i;
}
Status CreateDG(MGraph&G) {
int i = 0, j = 0, k = 0; VertexType v1, v2;
printf("%d", &G.vexnum);
printf("请输入弧总数:");
scanf("%d", &G.arcnum);
printf("请输入%d个顶点值:", G.vexnum);
getchar();
for (; i < G.vexnum; i++)
scanf("%c", &G.vexs[i]);
for (i = 0; i < G.vexnum; i++)
for (j = 0; j < G.vexnum; j++)G.arcs[i][j] = 0;
for (; k < G.arcnum; k++) {
printf("请输入第%d对作为弧尾,弧头的元素:", k + 1);
getchar();
scanf("%c%c",&v1,&v2);
i = LocateVex(G, v1); j = LocateVex(G, v2);
if ((i == G.vexnum) || (j == G.vexnum)) {
printf("弧端元素输入错误\n");
return ERROR;
}
G.arcs[i][j] = 1;
}
printf("成功创建有向图\n");
return OK;
}
//END
//无向图
Status CreateUDG(MGraph &G) {
int i = 0, j = 0, k = 0; VertexType v1, v2;
pri
#include<stdio.h>
#include<stdlib.h>
#define INFINITY 2147483647
#define MAX 20
#define OK 1
#define ERROR 0
//结构类型定义部分
typedef char VertexType;
typedef int Status;
typedef int VRType;
typedef enum { DG, DN, UDG, UDN }GrapghKind;
typedef struct {
VertexType vexs[MAX];
VRType arcs[MAX][MAX];
int vexnum;
int arcnum;
GrapghKind kind;
}MGraph;
typedef struct {
VertexType adivex;
VRType lowcost;
}edge;
MGraph G[4];
int visited[MAX];
Status(*VisiFunc)(MGraph G, int v);
edge closedge[MAX];
int LocateVex(MGraph G, VertexType v);
Status CreateDG(MGraph &G);
Status CreateUDG(MGraph &G);
Status CreateDN(MGraph &G);
Status CreateUDN(MGraph &G);
Status PrintVex(MGraph G, int v);
int FirstAdjVex(MGraph G, int v, int w);
int NextADjvex(MGraph G, int v, int w);
void DFS(MGraph G, int v);
void DFSTraverse(MGraph G, Status(*Visit) (MGraph G, int v));
void BFSTraverse(MGraph G, Status(*Visit) (MGraph G, int v));
Status ShortestPath_DIJ(MGraph G, int V0, int P[][MAX], int *D);
//2
Status PrintShortestPath(MGraph G, int V0, int P[][MAX], int *D);
int mininum(edge *closedge, int v);
Status MiniSpanTree_PRIM(MGraph G, int v0);
//函数定义部分
int LocateVex(MGraph G, VertexType v) {
int i = 0;
while ((v != G.vexs[i]) && (i < G.vexnum)) i++;
return i;
}
Status CreateDG(MGraph&G) {
int i = 0, j = 0, k = 0; VertexType v1, v2;
printf("%d", &G.vexnum);
printf("请输入弧总数:");
scanf("%d", &G.arcnum);
printf("请输入%d个顶点值:", G.vexnum);
getchar();
for (; i < G.vexnum; i++)
scanf("%c", &G.vexs[i]);
for (i = 0; i < G.vexnum; i++)
for (j = 0; j < G.vexnum; j++)G.arcs[i][j] = 0;
for (; k < G.arcnum; k++) {
printf("请输入第%d对作为弧尾,弧头的元素:", k + 1);
getchar();
scanf("%c%c",&v1,&v2);
i = LocateVex(G, v1); j = LocateVex(G, v2);
if ((i == G.vexnum) || (j == G.vexnum)) {
printf("弧端元素输入错误\n");
return ERROR;
}
G.arcs[i][j] = 1;
}
printf("成功创建有向图\n");
return OK;
}
//END
//无向图
Status CreateUDG(MGraph &G) {
int i = 0, j = 0, k = 0; VertexType v1, v2;
pri