数据结构实验八 图及其应用
实验内容
1．编写一个程序，完成如下功能：
(1) 建立如下有向图G1的邻接矩阵输出，并由邻接矩阵产生邻接表输出之；
(2) 输出图G1从顶点0开始的深度优先遍历序列；
(3) 输出图G1从顶点0开始的广度优先遍历序列；
(4) 用普里姆算法输出从顶点0出发的最小生成树；
参考自：https://blog.csdn.net/chj65/article/details/103935951
#include <stdio.h>
#include <iostream>
using namespace std;
typedef int InfoType;
#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示∞
//以下定义邻接矩阵类型
typedef struct
{
int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{
int edges[MAXV][MAXV]; //邻接矩阵
int n, e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode //边的节点结构类型
{
int adjvex; //该边的终点位置
struct ANode* nextarc; //指向下一条边的指针
InfoType info; //该边的相关信息,这里用于存放权值
} ArcNode;
typedef int Vertex;
typedef struct Vnode //邻接表头节点的类型
{
Vertex data; //顶点信息
ArcNode* firstarc; //指向第一条边
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n, e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
void MatToList1(MGraph g, ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{
int i, j;
ArcNode* p; //表结点结构类型
G = new ALGraph;
for (i = 0; i < g.n; i++) //给邻接表中所有头节点的指针域置初值
G->adjlist[i].firstarc = NULL;
for (i = 0; i < g.n; i++) //检查邻接矩阵中每个元素
for (j = g.n - 1; j >= 0; j--)
if (g.edges[i][j] != 0 && g.edges[i][j] != INF) //存在一条边
{
p = new ArcNode;
p->adjvex = j; //终点信息
p->info = g.edges[i][j]; //权值信息
p->nextarc = G->adjlist[i].firstarc; //将*p链到链表后
G->adjlist[i].firstarc = p;
}
G->n = g.n; G->e = g.e;
}
void DispMat1(MGraph g)
//输出邻接矩阵g
{
int i, j;
for (i = 0; i < g.n; i++)
{
for (j = 0; j < g.n; j++)
if (g.edges[i][j] == INF)
printf("%3s", "∞");
else
printf("%3d", g.edges[i][j]);
cout << endl;
}
}
void DispAdj1(ALGraph* G)
//输出邻接表G
{
int i;
ArcNode* p;
for (i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
printf("%3d: ", i);
while (p != NULL)
{
printf("%3d(%d)", p->adjvex, p->info);
p = p->nextarc;
}
cout << endl;
}
}
int visited[MAXV] = { 0 }; //全局数组
void DFS(ALGraph* G, int v) //深度优先递归算法
{
ArcNode* p;
visited[v] = 1; //置已访问标记
printf("%3d", v); //输出被访问顶点的编号
p = G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点
while (p != NULL)
{
if (visited[p->adjvex] == 0) //若p->adjvex顶点未访问,递归访问它
DFS(G, p->adjvex);
p = p->nextarc; //p指向顶点v的下一条弧的弧头结点
}
}
void BFS(ALGraph* G, int v) //广度优先遍历
{
ArcNode* p;
int queue[MAXV], front = 0, rear = 0; //定义循环队列并初始化
int visited[MAXV]; //定义存放结点的访问标志的数组
int w, i;
for (i = 0; i < G->n; i++) visited[i] = 0; //访问标志数组初始化
printf("%3d", v); //输出被访问顶点的编号
visited[v] = 1; //置已访问标记
rear = (rear + 1) % MAXV;
queue[rear] = v; //v进队
while (front != rear) //若队列不空时循环
{
front = (front + 1) % MAXV;
w = queue[front]; //出队并赋给w
p = G->adjlist[w].firstarc; //找与顶点w邻接的第一个顶点
while (p != NULL)
{
if (visited[p->adjvex] == 0) //若当前邻接顶点未被访问
{
printf("%3d", p->adjvex); //访问相邻顶点
visited[p->adjvex] = 1; //置该顶点已被访问的标志
rear = (rear + 1) % MAXV; //该顶点进队
queue[rear] = p->adjvex;
}
p = p->nextarc; //找下一个邻接顶点
}
}
cout << endl;
}
void Prim(MGraph g, int v) //prim 算法求最小生成树
{
int lowcost[MAXV], min, n = g.n;
int closest[MAXV], i, j, k;
for (i = 0; i < g.n; i++)//赋初值，即将closest数组都赋为第一个结点v，lowcost数组赋为第一个结点v到各结点的权重
{
closest[i] = v;
lowcost[i] = g.edges[v][i];//g.edges[v][i]的值指的是结点v到i节点的权重
}
for (i = 1; i < g.n; i++)//接下来找剩下的n-1个结点（g.n是图的节点个数）
{
min = INF;//INF表示正无穷（每查找一个结点，min都会重新更新为INF，以便获取当前最小权重的结点）
for (j = 0; j < g.n; j++)//遍历所有结点
{
if (lowcost[j] != 0 && lowcost[j] < min)//若该结点还未被选且权值小于之前遍历所得到的最小值
{
min = lowcost[j];//更新min的值
k = j;//记录当前最小权重的结点的编号
}
}
printf("边(%d,%d)权为:%d\n", closest[k], k, min);
lowcost[k] = 0;//表明k结点已被选了(作标记)
//选中一个结点完成连接之后，作数组相应的调整
for (j = 0; j < g.n; j++)//遍历所有结点
{
if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j])
{
//更新lowcost数组，closest数组
lowcost[j] = g.edges[k][j];//更新权重，使其当前最小
closest[j] = k;//进入到该if语句里，说明刚选的结点k与当前结点j有更小的权重，则closest[j]的被连接结点需作修改为k
}
}
}
}
int main()
{
ALGraph* G;
MGraph g;
int path[MAXV], i, j, v = 0;
g.n = 6; g.e = 10;
int A[MAXV][6] = {
{ 0, 5, INF, 7, INF, INF },
{ INF, 0, 4, INF, INF, INF },
{ 8, INF, 0, INF, INF, 9 },
{ INF, INF, 5, 0, INF, 6 },
{ INF, INF, INF, 5, 0, INF },
{ 3, INF, INF, INF, 1, 0 } };
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
g.edges[i][j] = A[i][j];
cout << "有向图G的邻接矩阵:" << endl;
DispMat1(g);
G = new ALGraph;
MatToList1(g, G);
cout << "图G的邻接表:" << endl;
DispAdj1(G); //输出邻接表
cout << "从顶点0开始的DFS(递归算法):" << endl;
DFS(G, 0);
cout << endl;
cout << "从顶点0开始的BFS(非递归算法):" << endl;
BFS(G, 0);
cout << endl;
cout << "普里姆算法求解结果:" << endl;
Prim(g, 0);
return 0;
}
2.基于Dijkstra算法的最短路径求解：
问题描述：
一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。
输入要求：
多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路径。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。
输出要求：
每组数据输出两行。第一行为一个整数，为从起点到终点之间最短路径的长度。第二行为一串字符串，代表该路径。每两个字符之间用空格隔开。
输入样例
3 3
A B C
A B 1
B C 1
C A 3
A C
6 8
A B C D E F
A F 100
A E 30
A C 10
B C 5
C D 50
D E 20
E F 60
D F 10
A F
0 0
输出样例
2
A B C
60
A E D F
#include<iostream>
using namespace std;
#define maxn 200
#define inf 1e9
int n;
char v[maxn];
int Hash[maxn];
int e[maxn][maxn];
int dis[maxn];
int path[maxn];
int visit[maxn];
void Dijkstra(int x)
{
int k, min;
for (int i = 1; i <= n; i++)
{
dis[i] = e[x][i];
visit[i] = 0;
if (e[x][i] < inf)
path[i] = x;
else
path[i] = -1;
}
dis[x] = 0;
visit[x] = 1;
for (int t = 0; t < n - 1; t++)
{
min = inf;
for (int i = 1; i <= n; i++)
{
if (!visit[i] && dis[i] < min)
{
k = i;
min = dis[i];
}
}
visit[k] = 1;
for (int i = 1; i <= n; i++)
{
if (!visit[i] && dis[i] > dis[k] + e[k][i])
{
dis[i] = dis[k] + e[k][i];
path[i] = k;
}
}
}
}
void printpath(int x)
{
if (x != -1)
{
printpath(path[x]);
cout << v[x] << " ";
}
}
int main()
{
int m, d;
char x, y;
while (1)
{
cin >> n >> m;
if (!n && !m)break;
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxn; j++)
e[i][j] = inf;
for (int i = 1; i <= n; i++)
{
cin >> v[i];
Hash[v[i]] = i;
}
while (m--)
{
cin >> x >> y >> d;
e[Hash[x]][Hash[y]] = e[Hash[y]][Hash[x]] = d;
}
cin >> x >> y;
Dijkstra(Hash[x]);
cout << dis[Hash[y]] << endl;
printpath(path[Hash[y]]);
cout << v[Hash[y]] << endl;
}
return 0;
}