《数据结构（C语言版）第二版》第六章-图（算法设计题）

server/2024/9/29 15:34:27/

习题1

分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：
①增加一个新顶点v, InsertVex(G, v);
②删除顶点v及其相关的边，DeleteVex(G,v);
③增加一条边<v, w>, InsertArc(G, v, w);
④删除一条边<v, w>, DeleteArc(G, v, w)。

以邻接矩阵作为存储结构（有向图）

#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100typedef char VerTexType;
typedef int ArcType;typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateDG(AMGraph& G);
int LocateVex(AMGraph& G, VerTexType v);
void printfAMGraph(AMGraph& G);
void InsertVex(AMGraph& G, VerTexType v);
void DeleteVex(AMGraph& G, VerTexType v);
void InsertArc(AMGraph& G, VerTexType v, VerTexType w);
void DeleteArc(AMGraph& G, VerTexType v, VerTexType w);int main()
{AMGraph G = { {'\0'}, {0}, 0, 0 };CreateDG(G);printfAMGraph(G);printf("\n\n增加一个点'5'后：\n");InsertVex(G, '5');printfAMGraph(G);printf("\n\n删除一个点'4'后：\n");DeleteVex(G, '4');printfAMGraph(G);printf("\n\n增加一条弧<5,2>后：\n");InsertArc(G, '5', '2');printfAMGraph(G);printf("\n\n删除一条弧<5,2>后：\n");DeleteArc(G, '5', '2');printfAMGraph(G);return 0;
}//采用邻接矩阵表示法创建有向图
void CreateDG(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入有向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入有向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素：", i + 1);scanf_s(" %c", &G.vexs[i], sizeof(VerTexType));}//初始化邻接矩阵，将边的权值均置为0for (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = 0;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车） : ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = 1;}
}//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(AMGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); ++i){;}return i;
}//打印邻接矩阵表示法中的顶点表vexs和邻接矩阵arcs
void printfAMGraph(AMGraph& G)
{int i = 0;int j = 0;printf("各顶点为：");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为：\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == 32767){printf("%d  ", G.arcs[i][j]);}else{printf("%d      ", G.arcs[i][j]);}}printf("\n");}
}//增加一个新顶点v, InsertVex(G, v)
void InsertVex(AMGraph &G, VerTexType v)
{G.vexs[G.vexnum] = v;G.vexnum++;
}//删除顶点v及其相关的边，DeleteVex(G, v)
void DeleteVex(AMGraph& G, VerTexType v)
{int k = 0;k = LocateVex(G, v);int i = 0;int j = 0;int m = k;//从第k+2个元素起，数组vexs中的每一个元素都向前移动一个for (i = k+1,m = k; i < G.vexnum; i++,m++){G.vexs[m] = G.vexs[i];}//从第k+1行起，邻接矩阵中的每一行都向上移一行for (i = k + 1, m = k; i < G.vexnum; i++,m++){for (j = 0; j < G.vexnum; j++){G.arcs[m][j] = G.arcs[i][j];}}//从第k+1列起，邻接矩阵中的每一行都向前移一列for (j = k + 1, m = k; j < G.vexnum; j++, m++){for (i = 0; i < G.vexnum; i++){G.arcs[i][m] = G.arcs[i][j];}}//最后一行全部变为0for (i = 0; i < G.vexnum; i++){G.arcs[G.vexnum - 1][i] = 0;}//最后一列全部变为0for (i = 0; i < G.vexnum; i++){G.arcs[i][G.vexnum - 1] = 0;}G.vexnum--;
}//增加一条边<v, w>, InsertArc(G, v, w); 
void InsertArc(AMGraph &G, VerTexType v, VerTexType w)
{int i = LocateVex(G, v);int j = LocateVex(G, w);G.arcs[i][j] = 1;G.arcnum++;
}//删除一条边<v, w>, DeleteArc(G, v, w)。
void DeleteArc(AMGraph &G, VerTexType v, VerTexType w)
{int i = LocateVex(G, v);int j = LocateVex(G, w);G.arcs[i][j] = 0;G.arcnum--;
}

在这里插入图片描述
在这里插入图片描述

以邻接表作为存储结构（无向图）

#include <stdio.h>
#include <stdlib.h>#define MVNum 100typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct ArcNode
{int adjvex;struct ArcNode* nextarc;OtherInfo info;
}ArcNode;  //边结点typedef struct VNode
{VerTexType data;ArcNode* firstarc;
}VNode, AdjList[MVNum];  //表头结点typedef struct
{AdjList vertices;  //存储所有顶点int vexnum;  //顶点总数int arcnum;  //总边数
}ALGraph;  //图的信息void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
void InsertVex(ALGraph& G, VerTexType v);
void DeleteVex(ALGraph& G, VerTexType v);
void InsertArc(ALGraph& G, VerTexType v, VerTexType w);
void DeleteArc(ALGraph& G, VerTexType v, VerTexType w);int main()
{ALGraph G = { {'\0',NULL}, 0,0 };CreateUDG(G);printALGraph(G);printf("\n\n\n增加一个点'6'后：\n");InsertVex(G, '6');printALGraph(G);printf("\n\n\n删除一个点'4'后：\n");DeleteVex(G, '4');printALGraph(G);printf("\n\n\n增加一条边(6,2)后：\n");InsertArc(G, '6', '2');printALGraph(G);printf("\n\n\n删除一条边(6,2)后：\n");DeleteArc(G, '6', '2');printALGraph(G);return 0;
}void CreateUDG(ALGraph& G)
{int i = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;int j = 0;ArcNode* p1 = NULL;ArcNode* p2 = NULL;printf("请输入无向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值：", i + 1);scanf_s(" %c", &(G.vertices[i].data));G.vertices[i].firstarc = NULL;   //初始化}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部p2 = (ArcNode*)malloc(sizeof(ArcNode));p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部}
}//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i){;}return i;
}//打印邻接表
void printALGraph(ALGraph& G)
{int i = 0;ArcNode* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);pMove = G.vertices[i].firstarc;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点为：", i + 1);while (pMove){printf("%c ",G.vertices[pMove->adjvex].data);pMove = pMove->nextarc;}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//增加一个新顶点v, InsertVex(G, v)
void InsertVex(ALGraph&G, VerTexType v)
{G.vertices[G.vexnum].data = v;G.vertices[G.vexnum].firstarc = NULL;G.vexnum++;
}//删除顶点v及其相关的边，DeleteVex(G, v)
void DeleteVex(ALGraph& G, VerTexType v)
{int i = 0;int j = 0;int k = 0;int m = 0;ArcNode* p = NULL;int num = 0;k = LocateVex(G, v);for (i = 0; i < G.vexnum; i++){p = G.vertices[i].firstarc;if (i != k && p){if (p && p->adjvex == k){G.vertices[i].firstarc = p->nextarc;free(p);p = NULL;}else{ArcNode* Pre = p;while (p && p->adjvex != k){Pre = p;p = p->nextarc;}if (!p){continue;}else{Pre->nextarc = p->nextarc;free(p);p = NULL;}}}if (i == k){while (p){ArcNode* temp = p;p = p->nextarc;free(temp);temp = NULL;}}}G.vexnum--;//从第k+2个元素起，数组vexs中的每一个元素都向前移动一个for (i = k; i < G.vexnum; i++){G.vertices[i]= G.vertices[i+1];}// 清空数组vexs中最后一个顶点的信息G.vertices[G.vexnum].data = '\0';G.vertices[G.vexnum].firstarc = NULL;//更新所有边表中的顶点索引/*  删除顶点后，顶点数组中的顶点被向前移动了一位，这意味着比被删除顶点索引高的顶点的索引都减少了 1。否则，它们会仍然指向旧的索引位置及顶点值。*/for (i = 0; i < G.vexnum; i++){p = G.vertices[i].firstarc;while (p){if (p->adjvex > k)p->adjvex--; // 如果该边指向的顶点索引大于k，则减1p = p->nextarc;}}
}//增加一条边(v, w), InsertArc(G, v, w); 
void InsertArc(ALGraph& G, VerTexType v, VerTexType w)
{int i = LocateVex(G, v);int j = LocateVex(G, w);ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p;ArcNode* q = (ArcNode*)malloc(sizeof(ArcNode));q->adjvex = i;q->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = q;G.arcnum++;
}//删除一条边(v, w), DeleteArc(G, v, w)。
void DeleteArc(ALGraph& G, VerTexType v, VerTexType w)
{int i = LocateVex(G, v);int j = LocateVex(G, w);ArcNode *p1 = G.vertices[i].firstarc;ArcNode *p2 = G.vertices[j].firstarc;if (p1->adjvex == j){G.vertices[i].firstarc = p1->nextarc;free(p1);p1 = NULL;}else{ArcNode* pPre1 = NULL;while (p1->adjvex != j){pPre1 = p1;p1 = p1->nextarc;}pPre1->nextarc = p1->nextarc;free(p1);p1 = NULL;}if (p2->adjvex == i){G.vertices[j].firstarc = p2->nextarc;free(p2);p2 = NULL;}else{ArcNode* pPre2 = NULL;while (p2->adjvex != i){pPre2 = p2;p2 = p2->nextarc;}pPre2->nextarc = p2->nextarc;free(p2);p2 = NULL;}G.arcnum--;
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

习题2

一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

#include <stdio.h>
#include <stdlib.h>#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false"，如果被访问过，则置其相应的分量为 "true"typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct ArcNode
{int adjvex;struct ArcNode* nextarc;OtherInfo info;
}ArcNode;  //边结点typedef struct VNode
{VerTexType data;ArcNode* firstarc;
}VNode, AdjList[MVNum];  //表头结点typedef struct
{AdjList vertices;  //存储所有顶点int vexnum;  //顶点总数int arcnum;  //总边数
}ALGraph;  //图的信息typedef struct stackNode
{int data; //存放顶点的位置数struct stackNode* next;
}stackNode, * LinkStack;void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
void InitStack(LinkStack& S);
void Push(LinkStack& S, int e);
void Pop(LinkStack& S, int& e);
int EmptyStack(LinkStack S);
void DFS_Nonrecursive(ALGraph G, int v);int main()
{ALGraph G = { {'\0',NULL}, 0,0 };int i = 0;int j = 0;CreateUDG(G);printALGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始，采用邻接矩阵表示图的深度优先搜索遍历序列为：", i + 1);DFS_Nonrecursive(G, i + 1);//将visited数组初始化（重置visited数组）for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}void CreateUDG(ALGraph& G)
{int i = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;int j = 0;ArcNode* p1 = NULL;ArcNode* p2 = NULL;printf("请输入无向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值：", i + 1);scanf_s(" %c", &(G.vertices[i].data));G.vertices[i].firstarc = NULL;   //初始化}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部p2 = (ArcNode*)malloc(sizeof(ArcNode));p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部}
}//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i){;}return i;
}//打印邻接表
void printALGraph(ALGraph& G)
{int i = 0;ArcNode* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);pMove = G.vertices[i].firstarc;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);while (pMove){printf("%d ", pMove->adjvex);pMove = pMove->nextarc;}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//初始化栈
void InitStack(LinkStack& S)
{S = NULL;
}//入栈
void Push(LinkStack& S, int e)
{struct stackNode* p = (struct stackNode*)malloc(sizeof(struct stackNode));if (!p){printf("元素入栈时，内存分配失败。\n");return;}p->data = e;p->next = S;S = p;
}//出栈
void Pop(LinkStack& S, int& e)
{if (!S){printf("元素出栈时，栈为空。\n");return;}struct stackNode* p = S;e = p->data;S = p->next;free(p);p = NULL;
}//判断栈空
int EmptyStack(LinkStack S)
{if (!S){return 1;}else{return 0;}
}//使用非递归的方式，完成采用邻接表表示图的深度优先搜索遍历
void DFS_Nonrecursive(ALGraph G, int v)
{printf("%c ", G.vertices[v - 1].data);visited[v - 1] = true;ArcNode* p = NULL;int w = 0;LinkStack S = NULL;InitStack(S);Push(S, v);while (!EmptyStack(S)){Pop(S, v);  // 弹出栈顶元素// 指向该顶点的第一个邻接顶点p = G.vertices[v - 1].firstarc;while (p != NULL){w = p->adjvex;if (!visited[w]){// p指向该被弹出顶点的第一个未被访问的邻接顶点printf("%c ", G.vertices[w].data);visited[w] = true;Push(S, w + 1);break;  //退出整个while(p)循环}p = p->nextarc;}}
}

在这里插入图片描述

习题3

设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。

#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100typedef char VerTexType;
typedef int ArcType;ArcType D[MVNum][MVNum]; //记录顶点Vi和Vj之间的最短路径长度。
int Path[MVNum][MVNum]; //最短路径上顶点Vj的前一顶点的序号（下标）。
//这两个数组中的关于顶点的每个下标，与G.vexs中各顶点的下标是一致的typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath_Floyd(AMGraph G);
void find(AMGraph G, int i, int j);
void printPath(AMGraph G);int main()
{AMGraph G = { {0},{0},0,0 };int i = 0;CreateAMGraph(G);printAMGraph(G);printf("\n");ShortestPath_Floyd(G);printPath(G);return 0;
}//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; i++){printf("请输入第%d个顶点的值：", i + 1);scanf_s(" %c", &G.vexs[i]);for (j = 0; j < G.vexnum; j++){if (i != j){G.arcs[i][j] = MaxInt;}else{G.arcs[i][j] = 0;/* 在弗洛伊德算法中，每个顶点到其自身，（中间不存在弧），就已经是最短路径了。即使可以通过其它顶点中转再到达其本身，也是比其直接到其自身长的，所以把每个顶点与自身之间的权值均设为0.  */}}}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边的两个顶点：", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));printf("请输入第%d条边的权值：", k + 1);scanf_s(" %d", &w);i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w;}
}int LocateVex(AMGraph G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++){;}return i;
}void printAMGraph(AMGraph G)
{int i = 0;int j = 0;printf("各顶点值为：");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为：\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == MaxInt){printf("%d   ", G.arcs[i][j]);}else if (G.arcs[i][j] > 9){printf("%d      ", G.arcs[i][j]);}else{printf("%d       ", G.arcs[i][j]);}}printf("\n");}
}//用Floyd算法求有向网G中各对顶点i和j之间的最短路径
void ShortestPath_Floyd(AMGraph G)
{int i = 0;int j = 0;int k = 0;for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){D[i][j] = G.arcs[i][j];if (D[i][j] < MaxInt && D[i][j] != 0){Path[i][j] = i;}else{Path[i][j] = -1;}}}for (k = 0; k < G.vexnum; k++){for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (D[i][k] + D[k][j] < D[i][j]){D[i][j] = D[i][k] + D[k][j];Path[i][j] = Path[k][j];}}}}
}//递归打印G中从下标为i的顶点，到下标为j的顶点的最短路径
void find(AMGraph G, int i, int	j)
{if (i == j){printf("%c ", G.vexs[i]);return;}else{find(G, i, Path[i][j]);  //不断取从序号为i的顶点到序号为j的顶点最短路径上，序号为j的顶点的直接前驱顶点的序号printf(" -> %c", G.vexs[j]); //并且打印该序号对应的顶点值}
}void printPath(AMGraph G)
{int i = 0;int j = 0;int max = 0;int maxVex = 0;for (i = 0; i < G.vexnum; i++){max = 0;maxVex = 0;for (j = 0; j < G.vexnum; j++){if (j != i){if (Path[i][j] == -1){printf("\n从第%d个顶点%c到第%d个顶点%c不存在最短路径。", i + 1, G.vexs[i], j + 1, G.vexs[j]);}else{printf("\n从第%d个顶点%c到第%d个顶点%c的最短路径为：", i + 1, G.vexs[i], j + 1, G.vexs[j]);find(G, i, j);printf(" ，其长度为：%d", D[i][j]);if (D[i][j] != MaxInt && D[i][j] > max){max = D[i][j];maxVex = j;}}}}if (max != 0){printf("\n距离顶点%c的最短路径长度最大的一个顶点是：%c，其最短路径长度为：%d\n ", G.vexs[i], G.vexs[maxVex], max);}}
}

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

习题4 （存在时如何输出路径？）

试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j）。

#include <stdio.h>
#include <stdlib.h>#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false"，如果被访问过，则置其相应的分量为 "true"bool visited_findPath[MVNum];typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct ArcNode
{int adjvex;struct ArcNode* nextarc;OtherInfo info;
}ArcNode;  //边结点typedef struct VNode
{VerTexType data;ArcNode* firstarc;
}VNode, AdjList[MVNum];  //表头结点typedef struct
{AdjList vertices;  //存储所有顶点int vexnum;  //顶点总数int arcnum;  //总边数
}ALGraph;  //图的信息void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
void DFS_AL(ALGraph G, int v);
void DFSTraverse(ALGraph G);
int findPath_DFS(ALGraph G, int i, int j);int main()
{ALGraph G = { {'\0',NULL}, 0,0 };int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';char choice = '\0';CreateUDG(G);printALGraph(G);printf("\n");DFSTraverse(G);while (1){printf("\n\n请输入要判断是否存在路径的两个顶点值：");scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);k = findPath_DFS(G, i, j);if (k == 1){printf("\n顶点%c与%c之间存在路径。", v1,v2);}else{printf("\n顶点%c与%c之间不存在路径。", v1, v2);}//将visited_findPath数组初始化（重置visited_findPath数组）for (j = 0; j < G.vexnum; j++){visited_findPath[j] = false;}printf("\n是否继续？(y/n): ");scanf_s(" %c", &choice);  //这里的"%c"前面必须要有空格，否则输入y也会退出主函数getchar(); // 清除输入缓冲区中的换行符if (choice != 'y' && choice != 'Y')break;}return 0;
}void CreateUDG(ALGraph& G)
{int i = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;int j = 0;ArcNode* p1 = NULL;ArcNode* p2 = NULL;printf("请输入无向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值：", i + 1);scanf_s(" %c", &(G.vertices[i].data));G.vertices[i].firstarc = NULL;   //初始化}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部p2 = (ArcNode*)malloc(sizeof(ArcNode));p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部}
}//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i){;}return i;
}//打印邻接表
void printALGraph(ALGraph& G)
{int i = 0;ArcNode* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);pMove = G.vertices[i].firstarc;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);while (pMove){printf("%d ", pMove->adjvex);pMove = pMove->nextarc;}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//算法6.6 采用邻接表表示图的深度优先搜索遍历
void DFS_AL(ALGraph G, int v)
{printf("%c ", G.vertices[v - 1].data);visited[v - 1] = true;ArcNode* p = G.vertices[v - 1].firstarc;int w = 0;while (p != NULL){w = p->adjvex;if (!visited[w]){DFS_AL(G, w + 1);}p = p->nextarc;}
}//算法6.4 深度优先搜索遍历非连通图
void DFSTraverse(ALGraph G)
{int v = 0;for (v = 0; v < G.vexnum; ++v){visited[v] = false;}printf("\n非连通图G的深度优先搜索遍历序列为：");for (v = 0; v < G.vexnum; ++v){if (!visited[v]){DFS_AL(G, v + 1);}}
}int findPath_DFS(ALGraph G, int i, int j)
{ArcNode* p = NULL;int m = 0;if (i == j){//printf(" %c ", G.vertices[j].data);return 1;}else{//printf("%c -> ", G.vertices[i].data);visited_findPath[i] = 1;for (p = G.vertices[i].firstarc; p; p = p->nextarc){m = p->adjvex;if (!visited_findPath[m] && findPath_DFS(G, m, j)){return 1;}}//由于p为空跳出for循环时if (!p){return 0;}}
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

int findPath_DFS(ALGraph G, int i, int j)
{ArcNode* p = NULL;int m = 0;printf(" \n\nG.vertices[i].data =  G.vertices[%d].data = %c", i, G.vertices[i].data);printf(" \nG.vertices[j].data =  G.vertices[%d].data = %c\n", j, G.vertices[j].data);if (i == j){printf("\n【1】%c \n", G.vertices[j].data);return 1;}else{printf("\n【2】%c -> \n", G.vertices[i].data);visited_findPath[i] = 1;printf("\n【3】visited_findPath[i] =  visited_findPath[%d] = %d\n", i, visited_findPath[i]);for (p = G.vertices[i].firstarc; p; p = p->nextarc){printf(" \n【4】G.vertices[p->adjvex].data =  G.vertices[%d].data = %c\n", p->adjvex, G.vertices[p->adjvex].data);m = p->adjvex;printf("\n【5】m = %d\n", m);printf("\n【6】visited_findPath[m] =  visited_findPath[%d] = %d\n", m, visited_findPath[m]);if (!visited_findPath[m] && findPath_DFS(G, m, j)){return 1;}}//由于p为空跳出for循环时if (!p){return 0;}}
}

习题5（存在时如何输出路径？）

采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为k 的简单路径。

#include <stdio.h>
#include <stdlib.h>#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false"，如果被访问过，则置其相应的分量为 "true"bool visited_findPath[MVNum];
bool visited_PathLen[MVNum];
int path[MVNum];typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct ArcNode
{int adjvex;struct ArcNode* nextarc;OtherInfo info;
}ArcNode;  //边结点typedef struct VNode
{VerTexType data;ArcNode* firstarc;
}VNode, AdjList[MVNum];  //表头结点typedef struct
{AdjList vertices;  //存储所有顶点int vexnum;  //顶点总数int arcnum;  //总边数
}ALGraph;  //图的信息void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
void DFS_AL(ALGraph G, int v);
void DFSTraverse(ALGraph G);
int findPath_DFS(ALGraph G, int i, int j);
int findPathLen(ALGraph G, int i, int j, int k);int main()
{ALGraph G = { {'\0',NULL}, 0,0 };int i = 0;int j = 0;int k = 0;int k1 = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';int len = 0;int k2 = 0;char choice = '\0';CreateUDG(G);printALGraph(G);printf("\n");DFSTraverse(G);while (1){printf("\n\n请输入要判断是否存在路径的两个顶点值：");scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);k1 = findPath_DFS(G, i, j);if (k1 == 1){printf("顶点%c与%c之间存在路径。", v1, v2);}else{printf("顶点%c与%c之间不存在路径。", v1, v2);}//将visited_findPath数组初始化（重置visited_findPath数组）for (k = 0; k < G.vexnum; k++){visited_findPath[k] = false;}if (k1 == 1){printf("\n请输入要查找的长度len ：");scanf_s(" %d", &len);k2 = findPathLen(G, i, j, len);if (k2 == 1){printf("顶点%c与%c之间存在长度为%d的路径。", v1, v2, len);}else{printf("顶点%c与%c之间不存在长度为%d的路径。", v1, v2, len);}//将visited_PathLen数组初始化（重置visited_PathLen数组）for (k = 0; k < G.vexnum; k++){visited_PathLen[k] = false;}}printf("\n是否继续？(y/n): ");scanf_s(" %c", &choice);  //这里的"%c"前面必须要有空格，否则输入y也会退出主函数getchar(); // 清除输入缓冲区中的换行符if (choice != 'y' && choice != 'Y')break;}return 0;
}void CreateUDG(ALGraph& G)
{int i = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;int j = 0;ArcNode* p1 = NULL;ArcNode* p2 = NULL;printf("请输入无向图的总顶点数：");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数：");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值：", i + 1);scanf_s(" %c", &(G.vertices[i].data));G.vertices[i].firstarc = NULL;   //初始化}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部p2 = (ArcNode*)malloc(sizeof(ArcNode));p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部}
}//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i){;}return i;
}//打印邻接表
void printALGraph(ALGraph& G)
{int i = 0;ArcNode* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);pMove = G.vertices[i].firstarc;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);while (pMove){printf("%d ", pMove->adjvex);pMove = pMove->nextarc;}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//算法6.6 采用邻接表表示图的深度优先搜索遍历
void DFS_AL(ALGraph G, int v)
{printf("%c ", G.vertices[v - 1].data);visited[v - 1] = true;ArcNode* p = G.vertices[v - 1].firstarc;int w = 0;while (p != NULL){w = p->adjvex;if (!visited[w]){DFS_AL(G, w + 1);}p = p->nextarc;}
}//算法6.4 深度优先搜索遍历非连通图
void DFSTraverse(ALGraph G)
{int v = 0;for (v = 0; v < G.vexnum; ++v){visited[v] = false;}printf("\n非连通图G的深度优先搜索遍历序列为：");for (v = 0; v < G.vexnum; ++v){if (!visited[v]){DFS_AL(G, v + 1);}}
}int findPath_DFS(ALGraph G, int i, int j)
{ArcNode* p = NULL;int m = 0;if (i == j){//printf(" %c ", G.vertices[j].data);return 1;}else{//printf("%c -> ", G.vertices[i].data);visited_findPath[i] = 1;for (p = G.vertices[i].firstarc; p; p = p->nextarc){m = p->adjvex;if (!visited_findPath[m] && findPath_DFS(G, m, j)){return 1;}}//由于p为空跳出for循环时if (!p){return 0;}}
}int findPathLen(ALGraph G, int i, int j, int k)
{ArcNode* p = NULL;int m = 0;if (i == j && k == 1){return 1;}else{visited_PathLen[i] = 1;for (p = G.vertices[i].firstarc; p; p = p->nextarc){m = p->adjvex;if (!visited_PathLen[m] && findPathLen(G, m, j, k - 1)){return 1;}}visited_PathLen[i] = 0;//由于p为空跳出for循环时if (!p){return 0;}}
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

int findPathLen(ALGraph G, int i, int j, int k)
{ArcNode* p = NULL;int m = 0;printf(" \n\nG.vertices[i].data =  G.vertices[%d].data = %c", i, G.vertices[i].data);printf(" \nG.vertices[j].data =  G.vertices[%d].data = %c\n", j, G.vertices[j].data);if (i == j && k == 1){printf("\n【1】%c \n", G.vertices[j].data);return 1;}else{printf("\n【2】%c -> \n", G.vertices[i].data);visited_PathLen[i] = 1;printf("\n【3】visited_PathLen[i] =  visited_PathLen[%d] = %d\n", i, visited_PathLen[i]);for (p = G.vertices[i].firstarc; p; p = p->nextarc){printf("\n【4】G.vertices[p->adjvex].data =  G.vertices[%d].data = %c\n", p->adjvex, G.vertices[p->adjvex].data);m = p->adjvex;printf("\n【5】m = %d\n", m);printf("\n【6】visited_PathLen[m] =  visited_PathLen[%d] = %d\n", m, visited_PathLen[m]);if (!visited_PathLen[m] && findPathLen(G, m, j, k - 1)){return 1;}}printf("\n【7】visited_PathLen[i] =  visited_PathLen[%d] = %d\n", i, visited_PathLen[i]);visited_PathLen[i] = 0;printf("\n【8】visited_PathLen[i] =  visited_PathLen[%d] = %d\n", i, visited_PathLen[i]);}//由于p为空跳出for循环时if (!p){return 0;}
}

http://www.ppmy.cn/server/106122.html

相关文章

普通人用 AI 变现的4大方向

普通人用 AI 变现的4大方向

前言 AI出现&#xff0c;几家欢喜几家愁。 有人担心受怕恐因AI被裁&#xff0c;有人却早已利用AI躺赚&#x1f4b0;。 “利用AI发展副业的方式究竟有哪些&#xff1f;怎么样才能利用AI做到躺赚&#xff1f;” 我相信这是绝大部分人的疑惑点&#xff0c;包括我&#xff01;&…
阅读更多...
基于大模型的Agent体系框架

基于大模型的Agent体系框架

引言 在上一节中&#xff0c;我们知道了大模型对于Agent的重要性&#xff0c;可以说大模型就是 Agent 的"大脑"。大模型为AI Agent提供了强大的自然语言理解和生成能力&#xff0c;使其能够在复杂环境中进行决策和行动&#xff0c;并展现出高度的自主性和灵活性。 L…
阅读更多...
打卡第五十天：图论理论基础、深度优先搜索理论基础、所有可达路径、广度优先搜索理论基础

打卡第五十天：图论理论基础、深度优先搜索理论基础、所有可达路径、广度优先搜索理论基础

一、图论理论基础 图的基本概念 二维坐标中&#xff0c;两点可以连成线&#xff0c;多个点连成的线就构成了图。当然图也可以就一个节点&#xff0c;甚至没有节点&#xff08;空图&#xff09; 图的种类 整体上一般分为 有向图 和 无向图。有向图是指 图中边是有方向的&…
阅读更多...
三、联合索引失效场景，哪一个字段使用到了联合索引，根据sql如何建立联合索引

三、联合索引失效场景，哪一个字段使用到了联合索引，根据sql如何建立联合索引

目录 一、联合索引失效场景二、哪一个字段使用到了联合索引三、根据sql如何建立联合索引 一、联合索引失效场景 1、对&#xff08;a,b,c&#xff09;创建联合索引 where b2where c3where b2 and c3 以上场景均在在a无序的情况下b、c无法有序 where b2 and a4where b2 and c…
阅读更多...
Python在excel复制一列到另一个sheet页上

Python在excel复制一列到另一个sheet页上

要在Python中复制一个Excel列到另一个sheet页&#xff0c;可以使用openpyxl库。以下是一个简单的例子&#xff0c;演示如何复制列A的所有数据到sheet2的列B。 首先&#xff0c;确保安装了openpyxl库&#xff1a; from openpyxl import load_workbook# 加载Excel文件 wb load…
阅读更多...
VMware上Linux系统报错--mount: 在 /dev/sr0 上找不到媒体【解决办法】

VMware上Linux系统报错--mount: 在 /dev/sr0 上找不到媒体【解决办法】

问题背景 在VMware上使用CentOS7系统&#xff0c;想要在CentOS7系统上挂载一个镜像文件&#xff0c;在系统下使用mount命令挂载报错如下所示&#xff1a; 解决办法 用lsblk命令查看sr0设备是存在的 查看虚拟机侧问题&#xff0c;右键虚拟机&#xff0c;点击设置 镜像文件已选…
阅读更多...
【附源码】Python ：三棱锥建模

【附源码】Python ：三棱锥建模

系列文章目录 Python 建模入门&#xff1a;三棱锥建模 文章目录 系列文章目录一、建模需求二、源代码三、代码分析四、效果展示总结 一、建模需求 使用matplotlib和numpy库来创建一个三棱锥模型。 二、源代码 代码如下&#xff1a; import numpy as np import matplotlib.pyp…
阅读更多...
【PyTorch】关于torchvision中的数据集以及dataloader的使用

【PyTorch】关于torchvision中的数据集以及dataloader的使用

前提文章目录 【PyTorch】深度学习PyTorch环境配置及安装【详细清晰】 【PyTorch】深度学习PyTorch加载数据 【PyTorch】关于Tensorboard的简单使用 【PyTorch】关于Transforms的简单使用 文章目录 前提文章目录数据集简介程序中下载数据集读取数据集结合transform进行读取数据…
阅读更多...
最新文章

Copyright @ 2022~2023