图的操作
一、 实验目的
（1）掌握图的邻接矩阵和邻接表存储结构。
（2）熟练图的邻接表的基本运算。
（3）加深图的深度优先遍历算法和广度优先遍历算法的理解。
（4）领会最小生成树和最短路径问题的求解及相关算法设计。
二、 实验要求
有下图所示的带权有向图及其对应的邻接矩阵,编写一个程序,实现图的各种基本运算和下面main函数中的每一步功能。
（1）依据所给的邻接矩阵，创建上图的邻接表存储，并输出邻接表结构；
（2）输出从顶点0出发的一个深度优先遍历序列
（3）输出从顶点0出发的一个广度优先遍历序列
（4）采用克鲁斯卡尔算法求顶点0出发的一棵最小生成树
（5）采用克鲁斯卡尔算法求顶点0出发的一棵最小生成树
（6）采用迪杰斯特拉算法求顶点0出发到达其他各顶点的最短路径及最短路径长度
（7）销毁图的邻接表
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef char InfoType;
using namespace std;
typedef int ElemType;
using namespace std;
#define MAXY 5
#define INF 32767 // 无穷
#define MaxSize 1000
typedef struct {
int u; // 边的起始顶点
int v; // 边的终止顶点
int w; // 边的权值
} Edge;
typedef struct {
int n; // 图的顶点数
int e; // 图的边数
int edges[MAXY][MAXY]; // 邻接矩阵表示图的边
} MatGraph;
typedef struct ANode
{
int adjvex;//该边邻接点编号
struct ANode* nextarc;//指向下一条边的指针
int weight;//该边的相关信息，例如权值
}ArcNode;
typedef struct Vnode
{
InfoType data;//顶点其他信息
ArcNode* firstarc;//指向第一个边结点
}VNode;
typedef struct
{
VNode adjlist[MAXY];
int n, e;
}AdjGraph;
void CreateAdj(AdjGraph *&G, int A[MAXY][MAXY], int n, int e)//创建图的邻接表
{
int i, j; ArcNode* p;
G = (AdjGraph*)malloc(sizeof(AdjGraph));
for (i = 0; i < n; i++)
G->adjlist[i].firstarc = NULL;//所有头结点指针域置为空
for (i = 0; i < n; i++)//遍历邻接矩阵
{
for (j = n - 1; j >= 0; j--)
{
if (A[i][j] != 0 && A[i][j] != INF)//存在一条边<i,j>
{
p = (ArcNode*)malloc(sizeof(ArcNode));//创建一个结点p
p->adjvex = j;//存放邻接点
p->weight = A[i][j];//存放权
p->nextarc = G->adjlist[i].firstarc;//采用头插法插入结点p
G->adjlist[i].firstarc = p;
}
}
G->n = n; G->e = e;
}
}//创建图的邻接表
void DispAdj(AdjGraph* 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->weight);
p = p->nextarc;
}
printf("∧\n");
}
}//输出邻接表G
void DestroyAdj(AdjGraph*& G)
{
int i; ArcNode* pre, * p;
for (i = 0; i < G->n; i++)
{
pre = G->adjlist[i].firstarc;//p指向第i个单链表头结点
if (pre != NULL)
{
p = pre->nextarc;
while (p != NULL)
{
free(pre);
pre = p; p = p->nextarc;
}
free(pre);
}
}
free(G);//释放头结点数组
}//销毁图
int visited[MAXY] = { 0 };
void DFS(AdjGraph* G, int v)
{
ArcNode* p;
visited[v] = 1;//置已访问标记
printf("%d ", 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的下一个邻接点
}
}//深度优先遍历
typedef struct
{
ElemType data[MaxSize];
int front, rear;
}SqQueue;
//(1)初始化环形队列
void InitQueue(SqQueue*& q)
{
q = (SqQueue*)malloc(sizeof(SqQueue));
q->front = q->rear = 0;
}
//(2)依次进队元素
bool enQueue(SqQueue*& q, ElemType e)
{
if ((q->rear + 1) % MaxSize == q->front)
return false;
q->rear = (q->rear + 1) % MaxSize;
q->data[q->rear] = e;
return true;
}
//(3)判断环形队列q是否非空
bool QueueEmpty(SqQueue* q)
{
return(q->front == q->rear);
}
//(4)出队一个元素，输出该元素
bool deQueue(SqQueue*& q, ElemType& e)
{
if (q->front == q->rear)
return false;
q->front = (q->front + 1) % MaxSize;
e = q->data[q->front];
return true;
}
void BFS(AdjGraph* G,int u, int v)
{
int w, i; ArcNode* p;
SqQueue* qu;//定义环形队列指针
InitQueue(qu);//初始化队列
int visited[MAXY];//定义顶点访问标记数组
for (i = 0; i < G->n; i++)
visited[i] = 0;//访问标记数组初始化
printf("%2d", v);//输出访问顶点编号
visited[v] = 1;//设置已访问标记
enQueue(qu, v);
while (!QueueEmpty(qu))//队不空循环
{
deQueue(qu, w);//出队一个顶点w
p = G->adjlist[w].firstarc;//指向w的第一个邻接点
while (p != NULL)//查找w所有的邻接点
{
if (visited[p->adjvex == 0])//如果该邻接点未被访问
{
printf("%2d", p->adjvex);//访问该邻接点
visited[p->adjvex] = 1;//设置已访问标记
enQueue(qu, p->adjvex);//该顶点进队
}
p = p->nextarc;//找下一个邻接点
}
}
printf("\n");
}//广度优先遍历
void InsertSort(Edge arr[], int n) {
int i, j;
Edge key;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j].w > key.w) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void Kruskal(MatGraph g) {
int i, j, u1, v1, sn1, sn2, k;
int vset[MAXY];
Edge E[MaxSize]; // 存放图中的所有边
k = 0; // E数组下标从0开始
for (i = 0; i < g.n; i++) {
for (j = 0; j < g.n; j++) {
if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
E[k].u = i;
E[k].v = j;
E[k].w = g.edges[i][j];
k++;
}
}
}
InsertSort(E, g.e); // 采用直接插入排序法对E数组按权值递增排序
for (i = 0; i < g.n; i++) {
vset[i] = i; // 初始化辅助数组
}
k = 1; // k表示当前构造生成树的第几条边，初值为1
j = 0; // E中边的下标，初值为0
while (k < g.n) {
u1 = E[j].u;
v1 = E[j].v; // 取一条边的两个顶点
sn1 = vset[u1];
sn2 = vset[v1]; // 分别得到两个顶点所属的集合编号
if (sn1 != sn2) {
printf("(%d,%d):%d\n", u1, v1, E[j].w); // 输出最小生成树的一条边
k++; // 生成的边数加1
for (i = 0; i < g.n; i++) {
if (vset[i] == sn2) { // 两个集合统一编号
vset[i] = sn1;
}
}
}
j++; // 遍历下一条边
}
}
void Ppath(int path[], int i, int v)
{
int k;
k = path[i];
if (k == v)
return;
Ppath(path, k, v);
printf("%d,", k);
}
void Dispath(int dist[], int path[], int s[], int n, int v) {
for (int i = 0; i < n; i++) {
if (s[i] == 1) { // 顶点i在S中，输出路径长度和路径信息。
printf("从%d到%d的最短路径长度为:%d\t路径为:", v, i, dist[i]);
printf("%d,", v);
Ppath(path, i, v); // 打印从源点v到顶点i的路径。
printf("%d\n", i);
}
else { // 顶点i不在S中，输出不存在路径的信息。
printf("从%d到%d不存在路径\n", v, i);
}
}
}
void Dijkstra(MatGraph g, int v)
{
int dist[MAXY], path[MAXY];
int S[MAXY];//s[i]=1表示顶点i在S中，S[i]=0表示顶点i在U中
int mindist, i, j, u;
for (i = 0; i < g.n; i++)
{
dist[i] = g.edges[v][i];//距离初始化
S[i] = 0;//将S[]置空
if (g.edges[v][i] < INF)//路径初始化
path[i] = v;//顶点v到顶点i有边时，设置顶点i的前一个顶点为v
else
path[i] = -1;//顶点v到顶点i没边时，设置顶点i的前一个顶点为-1
}
S[v] = 1; path[v] = v;//源点编号v放入S中
for (i = 0; i < g.n - 1; i++)//循环，直到所有顶点的最短路径都求出
{
mindist = INF;//mindist置最大长度初值
for (j = 0; j < g.n; j++)//选取不在S中（既U中）且具有最小最短路径长度顶点u
if (S[j] == 0 && dist[j] < mindist)
{
u = j;
mindist = dist[j];
}
S[u] = 1;//顶点u加入S中
for (j = 0; j < g.n; j++)//修改不在S中（即U中）的顶点的最短路径
if (S[j] == 0)
{
if (g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j])
{
dist[j] = dist[u] + g.edges[u][j];
path[j] = u;
}
}
}
Dispath(dist, path, S, g.n, v);//输出最短路径
}
int main() {
MatGraph g;
g.n = 5; // 顶点数
g.e = 5; // 边数
int A[MAXY][MAXY] = {
{0, 1, 2, 6, INF},
{INF, 0, INF, 4, 5},
{INF, INF, 0, INF, 3},
{INF, INF, INF, 0, INF},
{INF, INF, INF, 7, 0}
};
memcpy(g.edges, A, sizeof(A));
AdjGraph* G;
CreateAdj(G, A, 5, 7);
printf("邻接表结构：\n");
DispAdj(G);
printf("深度优先遍历序列：\n");
int visited[MAXY] = { 0 };
DFS(G, 0);
printf("\n");
printf("广度优先遍历序列：\n");
BFS(G, 0, 0);
printf("克鲁斯卡尔算法最小生成树\n");
Kruskal(g);
Dijkstra(g, 0);
printf("销毁图");
DestroyAdj(G);
}
![[递归回溯枚举] 装载问题](https://img-blog.csdnimg.cn/direct/ac1933e8089c49428b54e88f11ae08f3.gif)