建立自己的网站有什么用,个人备案域名可以做哪些网站吗,免费建立自己的个人网站,中考管理系统登录网站目录
一、实验目的
1. 邻接矩阵
2. 邻接矩阵表示图的结构定义 3. 图的初始化
4. 边的添加 5. 边的删除
6. Dijkstra算法
三、实验内容
实验内容
代码
截图
分析 一、实验目的
1#xff0e;掌握图的邻接矩阵的存储定义#xff1b;
2#xff0e;掌握图的最短路径…目录
一、实验目的
1. 邻接矩阵
2. 邻接矩阵表示图的结构定义 3. 图的初始化
4. 边的添加 5. 边的删除
6. Dijkstra算法
三、实验内容
实验内容
代码
截图
分析 一、实验目的
1掌握图的邻接矩阵的存储定义
2掌握图的最短路径Dijsktra算法的实现。
二、实验原理
1. 邻接矩阵
邻接矩阵是一种表示图的方法。它是一个二维数组用于表示图中各个顶点之间的连接关系。如果图是有向图那么邻接矩阵是对称的如果是无向图邻接矩阵可能不是对称的。 顶点的编号 假设图有n个顶点通常是从1到n。 构建矩阵 创建一个n x n的矩阵其中元素a[i][j]表示顶点i到顶点j是否有边。如果存在边通常用1表示如果不存在边通常用0表示。 例如对于无向图如果顶点i和顶点j之间有边则a[i][j]和a[j][i]都设置为1。对于有向图只需设置a[i][j]为1表示从顶点i到顶点j有一条有向边。 权重 如果图中的边有权重可以在矩阵中存储这些权重。矩阵的元素a[i][j]可以表示从顶点i到顶点j的权重值。 2. 邻接矩阵表示图的结构定义
#define MAX_SIZE 100struct Graph {int numVertices;//节点数int adjMatrix[MAX_SIZE][MAX_SIZE];//邻接矩阵
}; 3. 图的初始化
创建一个空的图数据结构并为其设置初始状态。
void InitializeGraph(struct Graph* graph,int num) {int i, j;graph-numVertices num;for (i 0; i num; i) {for (j 0; j num; j) {graph-adjMatrix[i][j] 0;}}
}
4. 边的添加 在图中增加边将该边置为1表示存在或者权值
若是无向图由于对称性则需要改变两条边
//添加边
void addEdge(struct Graph* graph, int startVertex, int endVertex) {graph-adjMatrix[startVertex][endVertex] 1;//若是无向图graph-adjMatrix[endVertex][startVertex] 1;
} 5. 边的删除
置为0(不存在)或者无限大的权值
void deleteEdge(struct Graph* graph, int startVertex, int endVertex) {graph-adjMatrix[startVertex][endVertex] 0;//若是无向图graph-adjMatrix[endVertex][startVertex] 0;
}
6. Dijkstra算法
Dijkstra算法是一种用于在带有非负权重的图中找到单源最短路径的算法。该算法的基本思想是从起始顶点开始逐步扩展到离起始顶点的距离最短的顶点直到到达目标顶点为止。 初始化 对于每个顶点v初始化距离值dist[v]为无穷大表示尚未到达该顶点并将起始顶点的距离值dist[start]设置为0。创建一个优先队列最小堆将起始顶点加入队列。 更新距离值 从优先队列中取出距离值最小的顶点u。对于u的每个邻接顶点v如果通过u可以缩短到达v的距离dist[start] weight(u, v) dist[v]则更新dist[v]的值。更新后将v加入优先队列。 重复步骤2 重复上述步骤直到优先队列为空。这样对于每个顶点dist数组中存储的值就是从起始顶点到达该顶点的最短路径距离。 Dijkstra算法的关键在于通过贪心策略每次选择距离起始顶点最近的顶点进行扩展。这确保了每个顶点的最短路径被逐步确定直到到达目标顶点 //Dijkstra算法
void dijkstra(struct Graph* graph, int startVertex) {int dist[MAX_SIZE]; // 存储从起始节点到各节点的最短距离int visited[MAX_SIZE] { 0 }; // 标记节点是否被访问过// 初始化距离数组for (int i 0; i graph-numVertices; i) {dist[i] INT_MAX;}// 起始节点到自身的距离为0dist[startVertex] 0;for (int count 0; count graph-numVertices - 1; count) {int minDist 9999;int minIndex;// 选择距离最小的未访问节点for (int v 0; v graph-numVertices; v) {if (!visited[v] dist[v] minDist) {minDist dist[v];//当前最短距离minIndex v;//当前最短的点}}// 标记节点为已访问visited[minIndex] 1;// 更新最短距离数组//!visited[v]检查节点 v 是否已经被访问过如果节点已经被访问过则不需要更新最短距离。//graph-adjacencyMatrix[minIndex][v] ! 9999检查从当前节点 minIndex 到节点 v 是否存在边。9999 表示两个节点之间没有直接的连接因此如果这个条件为真说明节点 minIndex 和节点 v 之间存在边。// dist[minIndex] ! 9999检查起始节点到节点 minIndex 的最短距离是否已经被初始化如果没有被初始化说明当前节点 minIndex 不可达无法通过它来更新其他节点的距离。//(dist[minIndex] graph-adjMatrix[minIndex][v] dist[v])检查通过当前节点 minIndex 更新节点 v 的距离是否比已知的最短距离 dist[v] 更短。如果是就更新 dist[v] 为更短的距离。for (int v 0; v graph-numVertices; v) {if (!visited[v] graph-adjMatrix[minIndex][v] ! 9999 dist[minIndex] ! 9999 (dist[minIndex] graph-adjMatrix[minIndex][v] dist[v])) {dist[v] dist[minIndex] graph-adjMatrix[minIndex][v];}}}// 打印最短距离cout从 startVertex节点为起点endl;for (int i 0; i graph-numVertices; i) {cout到i节点的最短距离为 dist[i]endl;}
} 三、实验内容
实验内容 必做内容 设计安徽大学的校园平面图所含景点不少于 8 个。以图中顶点表示学校内各景点存放景点的名称、景点介绍信息等以边表示路径存放路径长度信息。要求将这些信息保存在文件 graph.txt 中系统执行时所处理的数据要对此文件分别进行读写操作。 1从文件 graph.txt 中读取相应数据, 创建一个图,使用邻接矩阵表示图 2景点信息查询为来访客人提供校园任意景点相关信息的介绍 3问路查询为来访客人提供校园任意两个景点之间的一条最短路径 选做内容对文件进行操作相应信息变化后再次进行景点信息查询和 问路查询时应该有所体现 1. 修改一个已有景点的相关信息 2. 增加一个新景点及其相关信息 3. 增加一条新的路径 4. 删除一个景点及其相关信息 5. 删除一条路径。 代码
#define _CRT_SECURE_NO_WARNINGS
#includefstream
#includeiostream
using namespace std;#define MAX_SIZE 100struct Graph {int numVertices;//节点数int adjMatrix[MAX_SIZE][MAX_SIZE];//邻接矩阵用来储存距离char address[MAX_SIZE][MAX_SIZE];//景点名称char intro[MAX_SIZE][MAX_SIZE];//景点介绍
};//图的初始化
void InitializeGraph(struct Graph* graph,int num) {int i, j;graph-numVertices num;for (i 0; i num; i) {for (j 0; j num; j) {graph-adjMatrix[i][j] 9999;}}
}//添加边
void addEdge(struct Graph* graph, int startVertex, int endVertex,int length) {graph-adjMatrix[startVertex][endVertex] length;//若是无向图graph-adjMatrix[endVertex][startVertex] length;
}//删除边
void deleteEdge(struct Graph* graph, int startVertex, int endVertex) {graph-adjMatrix[startVertex][endVertex] 0;//若是无向图graph-adjMatrix[endVertex][startVertex] 0;
}//找到编号对应的景点名称
void find_address(struct Graph* graph, int index) {cout graph-address[index];
}//Dijkstra算法
void dijkstra(struct Graph* graph, int startVertex, int endVertex) {int visited[MAX_SIZE] { 0 };//记录是否被访问过int pre[MAX_SIZE] { startVertex };//记录前驱点编号int min_leng[MAX_SIZE];for (int i 0; i MAX_SIZE; i) {min_leng[i] 9999;}visited[startVertex] 1;int min_length 9999;int min_index startVertex;//第一轮for (int j 0; j graph-numVertices; j) {if (visited[j] 0) {//如果未被访问过//cout graph-adjMatrix[startVertex][j] min_leng[j] endl;if (graph-adjMatrix[startVertex][j] min_leng[j]) {//如果新的起始点到达终点的距离更短则前驱节点为新的起始点//find_address(graph, j);pre[j] startVertex;min_leng[j] graph-adjMatrix[startVertex][j] ;}}//cout endl;for (int j 0; j graph-numVertices; j) {//找最短路径作为新一轮的起始点if (visited[j] 0) {//如果未被访问过if (min_leng[j] min_length) {min_length min_leng[j];min_index j;}}}visited[min_index] 1;}for (int i 0; i graph-numVertices - 2; i) {//共顶点数-2轮 for (int j 0; j graph-numVertices; j) {if (visited[j] 0) {//如果未被访问过//cout graph- adjMatrix[min_index][j] min_leng[j] endl;if ((graph-adjMatrix[min_index][j] min_length) min_leng[j]) {//如果新的起始点到达终点的距离更短则前驱节点为新的起始点//find_address(graph, j);pre[j] min_index;min_leng[j] graph-adjMatrix[min_index][j] min_length;}}//cout endl;}//cout 更新一轮endl;for (int j 0; j graph-numVertices; j) {//cout min_leng[j] ;}min_length 9999;min_index startVertex;for (int j 0; j graph-numVertices; j) {//找最短路径作为新一轮的起始点if (visited[j] 0) {//如果未被访问过if (min_leng[j] min_length) {min_length min_leng[j];min_index j;}}}visited[min_index] 1;//cout 这一轮起始点为;//find_address(graph, min_index);// cout endl 到达起始点距离为 min_length endl;}cout 最短距离为 min_leng[endVertex]endl;//输出最短路径从后往前找前驱cout 最短路径为;int count 2;int road[MAX_SIZE] ;for (int i 0; i MAX_SIZE; i) {road[i] endVertex;}road[0] startVertex;int end endVertex;//尾while (pre[end] ! startVertex) {//计算路径中的景点数count;end pre[end];}end endVertex;for (int i count - 2; i 0; i--) {road[i] pre[end];end pre[end];}int flag 1;for (int i 0; i count; i) {if (flag 0) {cout -;}find_address(graph, road[i]);flag 0;}return;
}//找到该景点对应的编号
int find_index(struct Graph* graph, char string[]) {for (int i 0; i graph-numVertices; i) {if (strcmp(string, graph-address[i]) 0) {return i;}}cout 不存在该景点 endl;return -1;
}//景点信息查询
void volun1(struct Graph* graph) {cout 本校景点有 endl;for (int i 0; i graph-numVertices; i) {cout i: graph-address[i] endl;}char string1[MAX_SIZE];cout 请输入你要查询的景点:;cin string1;int index find_index(graph, string1);cout graph-intro[index] endl;
}//最短路径查询
void volun2(struct Graph* graph) {char source[MAX_SIZE], destination[MAX_SIZE];cout 请输入起始景点和目的景点:;cin source destination;int start 0, end 0;start find_index(graph, source);end find_index(graph, destination);dijkstra(graph, start, end);cout endl;
}//增加景点相关信息
void volun3(struct Graph* graph) {char address[MAX_SIZE], intro[MAX_SIZE];cout 请输入你要增加的景点名称及其相关信息endl;cin address intro;//将信息复制进去strcpy(graph-address[graph-numVertices], address);strcpy(graph-intro[graph-numVertices], intro);graph-numVertices;//修改节点数//相关路径全改为无穷大for (int i 0; i graph-numVertices; i) {graph-adjMatrix[i][graph-numVertices - 1] 9999;}for (int i 0; i graph-numVertices; i) {graph-adjMatrix[graph-numVertices - 1][i] 9999;}
}//修改景点的相关信息
void volun4(struct Graph* graph) {char address[MAX_SIZE], intro[MAX_SIZE];cout 请输入你要修改的景点名称及其相关信息 endl;cin address intro;//找到编号int des_index find_index(graph, address);//修改memset(graph-intro[des_index], MAX_SIZE, sizeof(char));//清空strcpy(graph-intro[des_index], intro);
}//增加路径
void volun5(struct Graph* graph) {char source[MAX_SIZE], destination[MAX_SIZE]; int length;cout 请输入你要增加的路径: endl;cin source destination length;int start find_index(graph, source);int end find_index(graph, destination);addEdge(graph, start, end, length);
}//删除一个景点及其相关信息
void volun6(struct Graph* graph) {char address[MAX_SIZE];cout 请输入你要删除的景点 endl;cin address;int index find_index(graph, address);//清空memset(graph-address[index], MAX_SIZE, sizeof(char));memset(graph-intro[index], MAX_SIZE, sizeof(char));
}//删除一条路径
void volun7(struct Graph* graph) {char source[MAX_SIZE], destination[MAX_SIZE];cout 请输入你要删除的路径: endl;cin source destination;int start find_index(graph, source);int end find_index(graph, destination);deleteEdge(graph, start, end);
}int main() {struct Graph q;int num_V, num_a;//顶点数目边的个数FILE* filePointer;filePointer fopen(C:\\Users\\Administrator\\Desktop\\graph.txt, r);// 检查文件是否成功打开if (filePointer NULL) {cout 无法打开文件;return 1; // 退出程序}char buffer[1000];char Address[MAX_SIZE], Intro[MAX_SIZE];// 读取一行数据if (fgets(buffer, sizeof(buffer), filePointer) ! NULL) {if (sscanf(buffer, %d %d, num_V, num_a) 2) {q.numVertices num_V;//cout num_V num_aendl;}else {cout错误无法从字符串中提取两个数字。 endl;}} else {cout错误文件为空或无法读取。 endl;}InitializeGraph(q, num_V);//初始化图//读取景点名称及其介绍for (int i 0; i num_V; i) {if (fgets(buffer, sizeof(buffer), filePointer) ! NULL) {if (sscanf(buffer, %s %s, Address, Intro) 2) {strcpy(q.address[i], Address);strcpy(q.intro[i], Intro);//cout q.address[i] endl;//cout q.intro[i] endl;}else {printf(错误无法从字符串中提取两个字符串。\n);}}else {cout 错误文件为空或无法读取。 endl;}}//读取景点之间距离char source[MAX_SIZE], destination[MAX_SIZE];int length0;for (int i 0; i num_a; i) {if (fgets(buffer, sizeof(buffer), filePointer) ! NULL) {if (sscanf(buffer, %s %s %d, source, destination,length) 3) {int index1 find_index(q, source);int index2 find_index(q, destination);q.adjMatrix[index1][index2] length;q.adjMatrix[index2][index1] length;//cout index1 index2 length endl;}else {cout错误无法从字符串中提取两个字符串一个数字。endl;}}else {cout 错误文件为空或无法读取。 endl;}}// 关闭文件fclose(filePointer);//信息填充完毕接下来是查阅环节int code;cout ********************欢迎来到安徽大学******************** endl;cout 1.查询景点信息 endl;cout 2.问路查询 endl;cout 3.增加一个景点及其相关信息 endl;cout 4.修改一个景点的相关信息 endl;cout 5.增加一个新的路径 endl;cout 6.删除一个景点及其相关信息 endl;cout 7.删除一条路径 endl;cout 8.退出 endl;cout ********************安大校园导游系统********************* endl;cout 请选择需要的服务(1-8) endl;cin code;while (code ! 8) {switch (code){case 1: volun1(q); break;case 2: volun2(q); break;case 3: volun3(q); break;case 4: volun4(q); break;case 5: volun5(q); break;case 6: volun6(q); break;case 7: volun7(q); break;}cin code;}cout 退出 endl;return 0;
}
截图 分析 对于上述代码是存在一个问题的比如增加一个节点删除俩个节点总数目减少但是最大索引值是在增加的所以再次实现其他功能的时候是不切实际的 way1提供一个有效位数组按最大索引值的范围查找 way2: 当删除时后面的节点索引值应该加以改变但是很麻烦 此外上述代码提到了sscanf函数 sscanf函数接受一个字符串作为输入并根据指定的格式从该字符串中读取数据然后将数据存储在相应的变量中。 #include stdio.hint sscanf(const char *str, const char *format, ...);str是包含格式化数据的输入字符串。format是描述输入字符串中数据格式的格式字符串。可变参数...是用于存储从输入字符串中读取的数据的变量列表。
