实验七：图的基本操作
实验七：图的基本操作
- 键盘输入数据，建立一个有向图的邻接表。
- 输出该邻接表。
- 在有向图的邻接表的基础上计算各顶点的度，并输出。
- 以有向图的邻接表为基础实现输出它的拓扑排序序列。
- 采用邻接表存储实现无向图的深度优先遍历。
- 采用邻接表存储实现无向图的广度优先遍历。
- 采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。
- 采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。
- 在主函数中设计一个简单的菜单，分别调试上述算法。
综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。
源码
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
#define max_vertex_num 20
#define INFINITY 1000000000
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef char vertexType;
typedef struct VNode
{
vertexType data;
ArcNode *firstarc;
int count;
} VNode, AdjList[max_vertex_num];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
int degree;
} ALGraph; //邻接表
typedef struct ArcCell
{
int adj;
} ArcCell, AdjMatrix[max_vertex_num][max_vertex_num];
typedef struct
{
char vex[max_vertex_num];
AdjMatrix
arc;
int vexnum, arcnum;
} MGraph; //邻接矩阵
ALGraph ALG, InsertALG, UALG;
MGraph G;
int visit[max_vertex_num];
struct edge
{
char adjvex;
int lowcost;
} closedge[max_vertex_num];
int P[max_vertex_num];
int D[max_vertex_num];
int finial[max_vertex_num];
void print()
{
printf("（1）键盘输入数据，建立一个有向图的邻接表\n");
printf("（2）输出该邻接表\n");
printf("（3）在有向图的邻接表的基础上计算各顶点的度，并输出\n");
printf("（4）以有向图的邻接表为基础实现输出它的拓扑排序序列\n");
printf("（5）采用邻接表存储实现无向图的深度优先遍历\n");
printf("（6）采用邻接表存储实现无向图的广度优先遍历\n");
printf("（7）采用邻接矩阵存储实现无向图的最小生成树的PRIM算法\n");
printf("（8）采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径\n");
printf("（0）退出程序\n");
}
int locatevex(MGraph G, char v)
{
//查找顶点在图中的位置
int i = 0;
while (i < G.vexnum)
{
if (v == G.vex[i])
break;
else
i++;
}
return i;
}
void CreateALGraph(ALGraph
&ALG, ALGraph
&InsertALG)
{
//创建有向邻接表及其逆邻接表并且其顶点用大写字母表示
int i, j, k;
ArcNode *s, *r;
printf("请输入有向邻接表的顶点数和边数：\n");
scanf("%d%d", &ALG.vexnum, &ALG.arcnum);
for (i = 0; i < ALG.vexnum; i++)
{
ALG.vertices[i].data = 'A' + i;
ALG.vertices[i].firstarc = NULL;
InsertALG.vertices[i].data = 'A' + i;
InsertALG.vertices[i].firstarc = NULL;
}
for (k = 0; k < ALG.arcnum; k++)
{
scanf("%d%d", &i, &j);
s = (ArcNode*)malloc(sizeof(ArcNode));
r = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = j;
s->nextarc = ALG.vertices[i].firstarc;
ALG.vertices[i].firstarc = s;
r->adjvex = i;
r->nextarc = InsertALG.vertices[j].firstarc;
InsertALG.vertices[j].firstarc = r;
}
}
void CeratUALGraph(ALGraph &UALG)
{
//用头插法建立无向邻接表
int i, j, k;
ArcNode *p;
printf("请输入无向邻接表的的顶点数和边数：\n");
scanf("%d%d", &UALG.vexnum, &UALG.arcnum);
for (i = 0; i < UALG.vexnum; i++)
{
UALG.vertices[i].data = 'A' + i;
UALG.vertices[i].firstarc = NULL;
}
for (k = 0; k < UALG.arcnum; k++)
{
scanf("%d%d", &i, &j);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = UALG.vertices[i].firstarc;
UALG.vertices[i].firstarc = p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = UALG.vertices[j].firstarc;
UALG.vertices[j].firstarc = p;
}
}
void CreateUDN(MGraph &G, int a)
{
//若a==1的时候创建无向邻接矩阵，否则创建有向邻接矩阵
int i, j, k, w;
char v1, v2;
printf("请输入邻接矩阵的顶点数和边数：\n");
scanf("%d%d", &G.vexnum, &G.arcnum);
getchar();
for (i = 0; i < G.vexnum; i++)
scanf("%c", &G.vex[i]);
for (i = 0; i < G.vexnum; i++)
for (j = 0; j < G.vexnum; j++)
G.arc[i][j].adj = INFINITY;
for (k = 0; k < G.arcnum; k++)
{
getchar();
scanf("%c %c
%d", &v1, &v2, &w);
i = locatevex(G, v1);
j = locatevex(G, v2);
G.arc[i][j].adj = w;
if (a == 1)
G.arc[j][i].adj = G.arc[i][j].adj;
}
}
void shuchu(ALGraph ALG)
{
//遍历邻接表并输出
int i;
ArcNode *p;
for (i = 0; i < ALG.vexnum; i++)
{
printf("%d %c ", i, ALG.vertices[i].data);
for (p = ALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
printf("%d ", p->adjvex);
printf("\n");
}
}
void Degree(ALGraph ALG, ALGraph InsertALG)
{
//计算邻接表的度=邻接表的出度+逆邻接表的的出度
int i;
ArcNode *p;
for (i = 0; i < ALG.vexnum; i++)
{
ALG.vertices[i].count = 0;
for (p = ALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
ALG.vertices[i].count++;
}
for (i = 0; i < ALG.vexnum; i++)
{
InsertALG.vertices[i].count = 0;
for (p = InsertALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
InsertALG.vertices[i].count++;
}
for (i = 0; i < ALG.vexnum; i++)
{
printf("%c的度为：%d\n", 'A' + i, ALG.vertices[i].count + InsertALG.vertices[i].count);
}
}
void dfs(ALGraph UALG, int v)
{
//深度优先遍历
ArcNode *p;
visit[v] = 1;
printf("%c\n", UALG.vertices[v].data);
p = UALG.vertices[v].firstarc;
while (p)
{
if (!visit[p->adjvex])
dfs(UALG, p->adjvex);
p = p->nextarc;
}
}
void DFSTraverse(ALGraph UALG)
{
for (int i = 0; i < UALG.vexnum; i++)
visit[i] = 0;
for (i = 0; i < UALG.vexnum; i++)
if (!visit[i])
dfs(UALG, i);
printf("\n");
}
void BFSTraverse(ALGraph UALG)
{
//广度优先遍历
ArcNode *p;
int v;
queue<int>q;
for (int i = 0; i < UALG.vexnum; i++)
visit[i] = 0;
for (i = 0; i < UALG.vexnum; i++)
if (!visit[i])
{
visit[i] = 1;
printf("%c\n", UALG.vertices[i].data);
q.push(i);
while (!q.empty())
{
v = q.front();
q.pop();
p = UALG.vertices[v].firstarc;
while (p)
{
if (!visit[p->adjvex])
{
visit[p->adjvex] = 1;
printf("%c\n", UALG.vertices[p->adjvex].data);
q.push(p->adjvex);
}
p = p->nextarc;
}
}
}
}
void prim(MGraph G, char v)
{
//用prim算法求最小生成树
int i, j, k, min, n;
k = locatevex(G, v);
for (i = 0; i < G.vexnum; i++)
{
if (i != k)
{
closedge[i].adjvex = v;
closedge[i].lowcost = G.arc[k][i].adj;
}
}
closedge[k].lowcost = 0;
for (i = 1; i < G.vexnum; i++)
{
min = INFINITY;
for (j = 0; j < G.vexnum; j++)
{
if (closedge[j].lowcost != 0 && closedge[j].lowcost < min)
{
n = j;
min = closedge[j].lowcost;
}
}
printf("%c %c\n", closedge[n].adjvex, G.vex[n]);
closedge[n].lowcost = 0;
for (j = 0; j < G.vexnum; j++)
if (G.arc[n][j].adj < closedge[j].lowcost && G.arc[n][j].adj != INFINITY)
{
closedge[j].adjvex = G.vex[n];
closedge[j].lowcost = G.arc[n][j].adj;
}
}
printf("\n");
}
int indegree[max_vertex_num];
int topsort(ALGraph ALG, ALGraph InsertALG)
{
//拓扑排序
ArcNode *p;
stack<int>s;
int i, k, count;
for (i = 0; i < ALG.vexnum; i++)
{
InsertALG.vertices[i].count = 0;
for (p = InsertALG.vertices[i].firstarc; p != NULL; p = p->nextarc)
InsertALG.vertices[i].count++;
}
for (i = 0; i < ALG.vexnum; i++)
{
indegree[i] = InsertALG.vertices[i].count;
printf("%d\n", indegree[i]);
}
for (i = 0; i < ALG.vexnum; i++)
if (indegree[i] == 0)
s.push(i);
count = 0;
while (!s.empty())
{
i = s.top();
s.pop();
printf("%c ", ALG.vertices[i].data);
count++;
for (p = ALG.vertices[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
indegree[k]--;
if (indegree[k] == 0)
s.push(k);
}
}
if (count < ALG.vexnum)
return -1;
else
return 1;
}
void short_dij(MGraph G, int v0, int *P, int *D)
{
//用dij球最短路径
int i, v, w, min;
for (i = 0; i < G.vexnum; i++)
{
finial[i] = 0;
D[i] = G.arc[v0][i].adj;
if (D[i] < INFINITY)
P[i] = v0;
}
D[v0] = 0;
finial[v0] = 1;
for (i = 1; i < G.vexnum; i++)
{
min = INFINITY;
for (w = 0; w < G.vexnum; w++)
{
if (finial[w] == 0)
if (D[w] < min)
{
v = w;
min = D[w];
}
}
if (min < INFINITY)
finial[v] = 1;
else
break;
for (w = 0; w < G.vexnum; w++)
{
if (finial[w] == 0 && min + G.arc[v][w].adj < D[w])
{
D[w] = min + G.arc[v][w].adj;
P[w] = v;
printf("%d ", P[w]);
}
}
printf("\n");
}
printf("路径长度为：\n");
for (i = 0; i < G.vexnum; i++)
{
if (D[i] == INFINITY)
printf("无法到达!!!\n");
else
printf("%d\n", D[i]);
}
}
int main()
{
int menu;
char V;
do
{
void print();
scanf("%d", &menu);
switch (menu)
{
case 1:
CreateALGraph(ALG, InsertALG);
break;
case 2:
shuchu(ALG);
break;
case 3:
CreateALGraph(ALG, InsertALG);
Degree( ALG,
InsertALG);
break;
case 4:
CreateALGraph(ALG, InsertALG);
topsort(
ALG, InsertALG);
break;
case 5:
CeratUALGraph(UALG);
DFSTraverse(UALG);
break;
case 6:
CeratUALGraph(UALG);
BFSTraverse(UALG);
break;
case 7:
CreateUDN(G, 1);
printf("请输入出发顶点：\n");
scanf("%c", &V);
prim(G, V);
break;
case 8:
CreateUDN(G, 0);
short_dij( G, 0, P, D);
break;
case 0:
return 0;
}
}
while (menu != 0);
return 0;
}