求解答
设图结点的元素类型为ElemType(可以为char或int)，通过文件读取方式，建立一个不少于10个顶点的带权无向图G，实现以下图的各种基本操作的程序：
① 用邻接矩阵作为储结构存储图G并输出该邻接矩阵；
② 用邻接链表作为储结构存储图G并输出该邻接链表；
③ 按DFS算法输出图G中顶点的遍历序列；
④ 按BFS算法输出图G中顶点的遍历序列；
⑤ 按Prime算法从某个指定的顶点出发输出图G的最小生成树；
⑥ 求从有向图的某个节点出发到其余各顶点的最短路径和最短路径值；（带权有向图）；
⑦ 主函数通过函数调用实现以上各项操作。
#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
#define Maxsize 100
#define INF 65535 //表示无穷大
#define MaxVer 100 //最大顶点
#define MaxVerSize 100
//队列
typedef int QDataType;
typedef struct {
QDataType queue[maxsize];
int rear;
int front;
int count;
} SeqQueue;
//初始化
void QueueInit(SeqQueue* Q) {
Q->count = 0;
Q->front = 0;
Q->rear = 0;
}
//判断非空否
int QueueNotEmpty(SeqQueue Q) {
if (Q.count != 0) return 1;
else return 0;
}
//入队列
int QueueAppend(SeqQueue* Q, QDataType x) {
if (Q->count > 0 && Q->front == Q->rear) {
printf("队列已满\n");
return 0;
}
else {
Q->queue[Q->rear] = x;
Q->rear = (Q->rear + 1) % maxsize;
Q->count++;
return 1;
}
}
//出队列
int QueueDelete(SeqQueue* Q, QDataType* x) {
if (Q->count == 0) {
printf("队列已空\n");
return 0;
}
else {
*x = Q->queue[Q->front];
Q->front = (Q->front + 1) % maxsize;
Q->count--;
return 1;
}
}
//线性表——顺序表
typedef char LDataType;
typedef struct {
LDataType list[Maxsize];
int size;
} SeqList;
//初始化
void ListInit(SeqList* L) {
L->size = 0;
}
//插入数据元素
int ListInsert(SeqList* L, int i, LDataType x) {
int j;
if (L->size >= Maxsize) {
printf("顺序表已满，无法插入\n");
return 0;
}
else {
for (j = L->size - 1; j > i; j--)
L->list[j] = L->list[j - 1];
L->list[i] = x;
L->size++;
return 1;
}
}
//建立图
typedef char GDataType;
typedef struct {
SeqList Vertices; //存放顶点
int edge[MaxVer][MaxVer];
int numOfEdges; //边数
} MGraph;
//初始化
void InitGraph(MGraph* G, int n) {
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
if (i == j)G->edge[i][j] = 0; //自己到自己权值都初始化为0
else G->edge[i][j] = INF; //所有顶点是断开的状态
}
G->numOfEdges = 0;
ListInit(&G->Vertices); //顺序表存放顶点
}
//插入顶点（图中增加一个顶点）
void InsertVer(MGraph* G, GDataType vertex) {
ListInsert(&G->Vertices, G->Vertices.size, vertex);//在表结尾插入
}
//插入边(插入一条有向边<v1, v2>)
void InsertEdge(MGraph* G, int v1, int v2, int weight) {
if (v1 < 0 || v2 < 0 || v1 >= G->Vertices.size || v2 >= G->Vertices.size) {
printf("参数出错\n");
return;
}
G->edge[v1][v2] = weight;
G->numOfEdges++;
}
//取第一个邻接点
int GetFirstVer(MGraph G, int v) {
int col;
if (v < 0 || v > G.Vertices.size) {
printf("v越界出错\n");
return -1;
}
for (col = 0; col < G.Vertices.size; col++)
if (G.edge[v][col] > 0 && G.edge[v][col] < INF)return col;
return -1;
}
//取下一个邻接顶点
int GetNextVer(MGraph G, int v1, int v2) {
int col;
if (v1 < 0 || v2 < 0 || v1 >= G.Vertices.size || v2 >= G.Vertices.size) {
printf("参数越界出错\n");
return -1;
}
for (col = v2 + 1; col < G.Vertices.size; col++)
if (G.edge[v1][col] > 0 && G.edge[v1][col] < INF) return col;
return -1;
}
typedef struct {
int row; //行下标
int col; //列下标
int weight; //权值
} MRowColWeight; //边信息结构体
//创建图,在图G中插入n个顶点信息V和e条边信息E
void CreatGraph(MGraph* G, GDataType V[], int n, MRowColWeight E[], int e) {
int i, j;
InitGraph(G, n);
for (i = 0; i < n; i++)
InsertVer(G, V[i]); //插入顶点
for (j = 0; j < e; j++)
InsertEdge(G, E[j].row, E[j].col, E[j].weight); //插入边
}
//邻接边结构体
typedef char GDataType;
typedef struct GNode {
int dest; //邻接边的头顶点序号
struct GNode* next; //单链表的下一个结点指针
int weight; //权值
} Edge;
typedef struct {
GDataType data; //顶点数据
int order; //顶点在数组中存放的序号
Edge* adj; //邻接边头指针
} VHeadNode;
typedef struct {
VHeadNode a[MaxVerSize];//邻接表数组
int numOfVer; //顶点个数
int numOfEdges; //边数
} LGraph;
//初始化
void InitLGraph(LGraph* G) {
G->numOfEdges = 0;
G->numOfVer = 0;
for (int i = 0; i < MaxVerSize; i++) {
G->a[i].order = i; //初始化各个顶点序号
G->a[i].adj = NULL;
}
}
//插入顶点
void InsertLVer(LGraph* G, int i, GDataType ver) {//第i个位置插入
if (i >= 0 && i < MaxVerSize) {
G->a[i].data = ver;
G->numOfVer++;
}
else printf("顶点位置越界\n");
}
//插入边<v1, v2>
void InsertLEdge(LGraph* G, int v1, int v2, int weight) {
Edge* p;
if (v1 < 0 || v2 < 0 || v1 >= G->numOfVer || v2 >= G->numOfVer) {
printf("参数错误\n");
return;
}
p = (Edge*)malloc(sizeof(Edge));
p->dest = v2;
p->weight = weight;
p->next = G->a[v1].adj;
G->a[v1].adj = p;
G->numOfEdges++;
}
//插入双边<v1, v2>
void InsertDbLEdge(LGraph* G, int v1, int v2, int weight) {
Edge* p1, * p2;
if (v1 < 0 || v2 < 0 || v1 >= G->numOfVer || v2 >= G->numOfVer) {
printf("参数错误\n");
return;
}
p1 = (Edge*)malloc(sizeof(Edge));
p2 = (Edge*)malloc(sizeof(Edge));
p1->dest = v2;
p1->weight = weight;
p1->next = G->a[v1].adj;
G->a[v1].adj = p1;
p2->dest = v2;
p2->weight = weight;
p2->next = G->a[v1].adj;
G->a[v1].adj = p2;
G->numOfEdges += 2;
}
typedef struct {
int row; //行下标
int col; //列下标
int weight; //边上的权值
} LRowColWeight; //边信息结构体
//有向图
void CreateLGraph(LGraph* G, GDataType v[], int n, LRowColWeight d[], int e) {
int i, j;
InitLGraph(G);
for (i = 0; i < n; i++)InsertLVer(G, i, v[i]); //插入顶点
for (j = 0; j < e; j++)InsertLEdge(G, d[j].row, d[j].col, d[j].weight); //插入边
}
//创建无向图
void CreateDbLGraph(LGraph* G, GDataType v[], int n, LRowColWeight d[], int e) {
int i, j;
InitLGraph(G);
for (i = 0; i < n; i++)InsertLVer(G, i, v[i]); //插入顶点
for (j = 0; j < e; j++)InsertDbLEdge(G, d[j].row, d[j].col, d[j].weight); //插入边
}
//图的深度优先遍历---连通图
void DFS(MGraph G, int v, int visited[]) {
int w;
printf("%c ", G.Vertices.list[v]); //访问顶点v
visited[v] = 1;
w = GetFirstVer(G, v); //取v的第一个邻接顶点
while (w != -1) {
if (!visited[w])
DFS(G, w, visited); //递归
w = GetNextVer(G, v, w);
}
}
//广度优先搜索--连通图
void BFS(MGraph G, int v, int visited[]) {
int u, w;
SeqQueue queue;
QueueInit(&queue);
printf("%c ", G.Vertices.list[v]);//访问v顶点
visited[v] = 1;
QueueAppend(&queue, v);//初始顶点入队列
while (QueueNotEmpty(queue)) {
QueueDelete(&queue, &u);
w = GetFirstVer(G, u);
while (w != -1) {
if (!visited[w]) {
printf("%c ", G.Vertices.list[w]);
visited[w] = 1;
QueueAppend(&queue, w);
}
w = GetNextVer(G, u, w);
}
}
}
//Prime生成最小生成树
void Prim(MGraph G, int v) {
int lowCost[MaxVer];
int closest[MaxVer];
int min, i, j, k;
for (i = 0; i < G.Vertices.size; i++) {
lowCost[i] = G.edge[v][i];
closest[i] = v;
}
for (i = 0; i < G.Vertices.size - 1; i++) {
min = INF;
k = -1;
for (j = 0; j < G.Vertices.size; j++)
if (lowCost[j] != 0 && lowCost[j] < min) {
min = lowCost[j];
k = j;
}
printf(" (%c, %c, %d)\n", G.Vertices.list[closest[k]], G.Vertices.list[k], min);
lowCost[k] = 0;
for (j = 0; j < G.Vertices.size; j++)
if (lowCost[j] != 0 && G.edge[k][j] < lowCost[j]) {
lowCost[j] = G.edge[k][j];
closest[j] = k;
}
}
}
//用狄克斯特拉（Dijkastra）算法求从有向图的某个节点出发到其余各顶点的最短路径和最短路径值
void ShortestPathDjk(MGraph G, int v0, int distance[], int path[]) {
int n = G.Vertices.size;
int* s = (int*)malloc(sizeof(int) * n); //用来标记顶点是否从集合T加入集合S,加入为1，没加为0
int minDis, i, j, u;
//初始化
for (i = 0; i < n; i++) {
distance[i] = G.edge[v0][i];
s[i] = 0;
if (i != v0 && distance[i] < INF)path[i] = v0;
else path[i] = -1;
}
s[v0] = 1;
//在当前还未找到最短路径的顶点集合中，选最短路径的顶点
for (i = 1; i < n; i++) {
minDis = INF;
for (j = 0; j < n; j++)
if (s[j] == 0 && distance[j] < minDis) {
u = j;
minDis = distance[j];
}
if (minDis == INF) return;//对于非连通要加，这里连通可以不加
s[u] = 1;
//修改相应的最短距离和路径
for (j = 0; j < n; j++)
if (s[j] == 0 && (G.edge[u][j] < INF && distance[u] + G.edge[u][j] < distance[j])) {
distance[j] = distance[u] + G.edge[u][j];
path[j] = u;
}
}
}
//递归打印所有最短路径
void DisplayPath(MGraph G, int v0, int v1, int path[]) {
if (!v1)return;
DisplayPath(G, v0, path[v1], path);
printf("%c -> ", G.Vertices.list[path[v1]]);
}
//打印邻接矩阵
void printMatrix(MGraph G) {
int i, j;
printf("顶点集合为:\n");
for (i = 0; i < G.Vertices.size; i++)
printf("%c ", G.Vertices.list[i]);
printf("\n");
printf("\n输出邻接矩阵:\n");
for (i = 0; i < G.Vertices.size; i++) {
for (j = 0; j < G.Vertices.size; j++)
printf("%5d ", G.edge[i][j]);
printf("\n");
}
}
//打印邻接表
void printLTable(LGraph G) {
int i;
printf("\n顶点集合为：\n");
for (i = 0; i < G.numOfVer; i++)
printf("%c ", G.a[i].data);
printf("\n\n输出邻接表:\n");
i = 0;
while (i < G.numOfVer) {
Edge* p = G.a[i].adj;
while (p) {
printf(" %c--%d--%c ", G.a[i].data, p->weight, G.a[p->dest].data);
p = p->next->next;
}
printf("\n");
i++;
}
}
void ShortestToOtherVer(MGraph G, int v0) {
int i, distance[MaxVer], path[MaxVer];
ShortestPathDjk(G, v0, distance, path);
printf("\n从顶点%c到其他顶点的最短距离为：\n", G.Vertices.list[v0]);
for (i = 1; i < G.Vertices.size; i++) {
printf("%c->%c: 最短路径值 = %-6d", G.Vertices.list[v0], G.Vertices.list[i], distance[i]);
DisplayPath(G, v0, i, path);
printf("%c\n", G.Vertices.list[i]);
}
}
int main() {
int a;
printf("请输入1带权无向图 2带权有向图:");
scanf("%d", &a);
if (a == 1) {
int n = 0, e = 0, i = 0;
//从文件读取数据
FILE* fp = fopen("data.txt", "r");
if (!fp) {
printf("文件打开失败\n");
exit(0);
}
fscanf(fp, "%d %d ", &n, &e); //n是顶点个数，e是边数
GDataType mv[n], lv[n];
for (i = 0; i < n; i++) {
fscanf(fp, "%c", &mv[i]);
lv[i] = mv[i];
}
i = 0;
MRowColWeight mRCW[e];//定义边
LRowColWeight lRCM[e];//定义边
while (i < e) {
fscanf(fp, "%d %d %d", &mRCW[i].row, &mRCW[i].col, &mRCW[i].weight);
lRCM[i].row = mRCW[i].row;
lRCM[i].col = mRCW[i].col;
lRCM[i].weight = mRCW[i].weight;
i++;
}
fclose(fp);
MGraph G1;
LGraph G2;
//邻接矩阵创建无向图，并输出邻接矩阵
CreatGraph(&G1, mv, n, mRCW, e);
printMatrix(G1);
//邻接表创建无向图，并输出邻接表
CreateDbLGraph(&G2, lv, n, lRCM, e);
printLTable(G2);
//按DFS算法输出图G中顶点的遍历序列
printf("\n按DFS算法输出图G中顶点的遍历序列:\n");
int visitDFS[MaxVer];
DFS(G1, 0, visitDFS);
//按BFS算法输出图G中顶点的遍历序列
printf("\n按BFS算法输出图G中顶点的遍历序列:\n");
int visitBFS[MaxVer];
BFS(G1, 0, visitBFS);
//Prime生成最小生成树
printf("\n\n用Prime算法从顶点A出发生成最小生成树:\n");
Prim(G1, 0);
}
if (a == 2) {
int p = 0, q = 0, j = 0;
FILE* fp = fopen("dataDirect.txt", "r");
if (!fp) {
printf("文件打开失败\n");
exit(0);
}
fscanf(fp, "%d %d ", &p, &q); //p是顶点个数，q是边数
GDataType mv[p];
for (j = 0; j < p; j++) {
fscanf(fp, "%c", &mv[j]);
}
j = 0;
MRowColWeight mRCW[q];//定义边
while (j < q) {
fscanf(fp, "%d %d %d", &mRCW[j].row, &mRCW[j].col, &mRCW[j].weight);
j++;
}
fclose(fp);
MGraph G;
CreatGraph(&G, mv, p, mRCW, q);//构造带权有向图
printMatrix(G);//打印出邻接矩阵
//求从有向图的某个节点出发到其余各顶点的最短路径和最短路径值
ShortestToOtherVer(G, 0);
return 0;
}
}