//Graph.cpp #include <iostream> #include <bits/stdc++.h> #include "Graph.h" #include "Tourism.h" extern struct Graph m_Graph; using namespace std; void Init(void) { m_Graph.m_nVexNum = 0; for (int i = 0; i < 20; i++) { strcpy(m_Graph.m_aVexs[i].name, ""); strcpy(m_Graph.m_aVexs[i].desc, ""); m_Graph.m_aVexs[i].num = -1; for (int j = 0; j < 20; j++) { if (i == j) m_Graph.m_aAdjMatrix[i][j] = 0; else m_Graph.m_aAdjMatrix[i][j] = MAX; } } }// 初始化图结构。 void InsertVex(Vex sVex,int i) { m_Graph.m_aVexs[i].num =sVex.num; strcpy(m_Graph.m_aVexs[i].name, sVex.name); strcpy(m_Graph.m_aVexs[i].desc, sVex.desc); }// 将顶点添加到顶点数组中。 void InsertEdge(Edge sEdge) { m_Graph.m_aAdjMatrix[sEdge.vex1][sEdge.vex2] = sEdge.weight; m_Graph.m_aAdjMatrix[sEdge.vex2][sEdge.vex1] = sEdge.weight; }// 将边保存到邻接矩阵中。 void GetVex(int nVex) { cout << m_Graph.m_aVexs[nVex].name << endl; cout << m_Graph.m_aVexs[nVex].desc << endl; cout << "-----周边景区-----" << endl; FindEdge(nVex); }// 查询指定顶点信息。 int FindEdge(int nVex) { for (int i = 0; i < m_Graph.m_nVexNum; i++) { if (i != m_Graph.m_aVexs[nVex].num&&m_Graph.m_aAdjMatrix[m_Graph.m_aVexs[nVex].num][i] != MAX) { cout << m_Graph.m_aVexs[nVex].name << "-" << m_Graph.m_aVexs[i].name << " " << m_Graph.m_aAdjMatrix[m_Graph.m_aVexs[nVex].num][i] << endl; } } return 0; }// 查询与指定顶点相连的边。 int GetVexnum(void) { return m_Graph.m_nVexNum; }// 获取当前顶点数 void DFS(int nVex, bool bVisted[], int &nIndex, PathList &pList) { bVisted[nVex] = false; if (nIndex == m_Graph.m_nVexNum - 1) { pList->next = new Path(); for (int i = 0; i < m_Graph.m_nVexNum - 1; i++) { pList->next->vexs[i] = pList->vexs[i]; } pList = pList->next; pList->next = NULL; bVisted[nVex] = true; return; } for (int i = 0; i < m_Graph.m_nVexNum; i++) { if (i == nVex||!bVisted[i]) continue; if (m_Graph.m_aAdjMatrix[nVex][i] != MAX) { pList->vexs[nIndex++] = i; DFS(i, bVisted, nIndex, pList); nIndex--; } } bVisted[nVex] = true; } void DFSTraverse(int nVex, PathList &pList) { bool bVisted[20]; memset(bVisted, true, sizeof(bVisted)); int nIndex = 0, countn = 0; PathList temp = pList; pList->next = NULL; DFS(nVex, bVisted, nIndex, temp); while (pList != NULL) { cout << "路线" << ++countn << ": "<<m_Graph.m_aVexs[nVex].name; for (int i = 0; pList->vexs[i] != -1; i++) { cout << " -> " << m_Graph.m_aVexs[pList->vexs[i]].name; } cout << endl; pList = pList->next; } } int FindShortPath(int nVexStart, int nVexEnd) { int dp[20][20]; int index = 0,flag=0; //aPath[index].vex1 = nVexStart; //aPath[index].vex2 = nVexEnd; //aPath[index].weight = m_Graph.m_aAdjMatrix[nVexStart][nVexEnd]; int route[20]; memset(route, -1, sizeof(-1)); int Vexnum = GetVexnum(); for (int i = 0; i < Vexnum; i++) dp[0][i] = m_Graph.m_aAdjMatrix[nVexStart][i]; for (int i = 0; i < Vexnum; i++) { if (i == nVexStart) { for (int j = 0; j < Vexnum; j++) { dp[i + 1][j] = dp[i][j]; } continue; } for (int j = 0; j < Vexnum; j++) { dp[i+1][j] = min(dp[i][j], dp[i][i] + m_Graph.m_aAdjMatrix[i][j]); } } int x = Vexnum ; int y = nVexEnd; route[0] = nVexEnd; while (x) { if (x == nVexStart) { x--; continue; } for (int i = 0; i < Vexnum; i++) { if (dp[x][y] == dp[x - 1][i] + m_Graph.m_aAdjMatrix[i][y]) { route[++index] = i; y = i; if (i == nVexStart) { x = 1; break; } } } x--; } int minRoute = 0; cout << "最短路线为: "<<m_Graph.m_aVexs[nVexStart].name; for (int i = index-1; i>=0; i--) { minRoute += m_Graph.m_aAdjMatrix[route[i + 1]][route[i]]; cout << "->" << m_Graph.m_aVexs[route[i]].name; if (route[i] == nVexEnd) break; } cout << endl << "最短距离为：" << minRoute << endl; return minRoute; }//通过Dijkstra算法求得v1到v2的最短路径 struct neigbor_egde { int weight; int index; int parent; neigbor_egde(){} neigbor_egde(int weight,int index,int parent):weight(weight),index(index),parent(parent){} }; const bool operator< (neigbor_egde const temp1, neigbor_egde const temp2) { return temp1.weight > temp2.weight; } int FindMinTree() { priority_queue<neigbor_egde> que; set <int> V; V.insert(0); int index = 0,flag=1; int num = GetVexnum(); int sumRoute = 0; while (flag != num) { for (int i = 0; i < num; i++) { if (m_Graph.m_aAdjMatrix[index][i] != MAX && i != index) { neigbor_egde temp(m_Graph.m_aAdjMatrix[index][i], i, index); que.push(temp); } } while (true) { neigbor_egde temp = que.top(); que.pop(); if (V.count(temp.index) == 0) { V.insert(temp.index); cout << m_Graph.m_aVexs[temp.parent].name << " -> " << m_Graph.m_aVexs[temp.index].name<<" "<<temp.weight<<"米"<<endl; index = temp.index; flag++; sumRoute += temp.weight; break; } } } cout << "铺设的总长度为："<<sumRoute <<"米"<< endl; return 0; }
//Graph.h #pragma once #ifndef Graph_h //#define Graph_h struct Vex { int num; // 景点编号 char name[20]; // 景点名字 char desc[1024]; // 景点介绍 Vex(int num,char *name,char *desc) { this->num = num; strcpy(this->name, name); strcpy(this->desc , desc); } Vex(){} }; struct Edge { int vex1, vex2; //边的两个个顶点 int weight; //权值 Edge(int vex1, int vex2, int weight) { this->vex1 = vex1; this->vex2 = vex2; this->weight = weight; } Edge() { } }; struct Graph { int m_aAdjMatrix[20][20]; // 邻接矩阵 Vex m_aVexs[20]; // 顶点数组 int m_nVexNum; // 顶点个数 }; // Graph对象，用于存储景区景点图 typedef struct Path { int vexs[20]; //保存一条路径 Path *next; //下一条路径 Path() { memset(vexs, -1, sizeof(vexs)); } }*PathList; const int MAX = 0x7fffff; void Init(void);// 初始化图结构。 void InsertVex(Vex sVex,int i);// 将顶点添加到顶点数组中。 void InsertEdge(Edge sEdge);// 将边保存到邻接矩阵中。 void GetVex(int nVex);// 查询指定顶点信息。 int FindEdge(int nVex);// 查询与指定顶点相连的边。 int GetVexnum(void);// 获取当前顶点数 void DFS(int nVex, bool bVisted[], int &nIndex, PathList &pList); void DFSTraverse(int nVex, PathList &pList); int FindShortPath(int nVexStart, int nVexEnd); int FindMinTree();//求最小生成树 #endif
//Tourism.cpp #include <iostream> #include<fstream> #include <cstdio> #include <algorithm> #include "Graph.h" #include "Tourism.h" using namespace std; extern struct Graph m_Graph; void CreateGraph(void) { Init(); int num; // 景点编号 char name[20]; // 景点名字 char desc[1024];//景点描述 ifstream VexR("Vex.txt"), EdgeR("Edge.txt") ; if (VexR.is_open()) { VexR >> m_Graph.m_nVexNum; for (int i = 0; i < m_Graph.m_nVexNum; i++) { VexR >> num >> name >> desc; Vex temp(num, name, desc); InsertVex(temp,i); } } int vex1, vex2; //边的两个个顶点 int weight; //权值 if (EdgeR.is_open()) { while (!EdgeR.eof()) { EdgeR >> vex1 >> vex2 >> weight; Edge temp(vex1, vex2, weight); InsertEdge(temp); } } return; }//读取文件，创建景区景点图。 void GetSpotInfo(void) { cout << "=====查询景点信息=====" << endl; for (int i = 0; i < m_Graph.m_nVexNum; i++) { cout << m_Graph.m_aVexs[i].num << "-" << m_Graph.m_aVexs[i].name << endl; } cout << "请输入想要查询的景点编号:"; int option; cin >> option; GetVex(option); }// 查询指定景点信息，显示到相邻景点的距离。 void TravelPath() { cout << "=====旅游景点导航=====" << endl; for (int i = 0; i < m_Graph.m_nVexNum; i++) { cout << m_Graph.m_aVexs[i].num << "-" << m_Graph.m_aVexs[i].name << endl; } cout << "请输入起始点编号:"; int option; cin >> option; cout << "导航路线为:" << endl; PathList pList=new Path(); DFSTraverse(option, pList); }//输入起点游览所有景点的路线 void MinRoute(int begin, int end) { int dp[20]; int route[20]; route[0] = begin; int index = 1; memset(route, -1, sizeof(route)); int Vexnum = GetVexnum(); for (int i = 0; i < Vexnum; i++) dp[i] = m_Graph.m_aAdjMatrix[begin][i]; for (int i = 0; i < Vexnum; i++) { for (int j = 0; j < Vexnum; j++) { dp[j] = min(dp[j], dp[i] + m_Graph.m_aAdjMatrix[i][j]); } } for (int i = Vexnum - 1; i >= 0; i++) { if (dp[end] == dp[i] + m_Graph.m_aAdjMatrix[i][end]) route[index++] = i; } cout << begin << "(" << m_Graph.m_aVexs[begin].name << ")" << "-" << end << "(" << m_Graph.m_aVexs[end].name << ")" << "最短路径为：" << dp[end] << endl; /*for (int i = 0; i < index; i++) { cout << route[i] << "(" << m_Graph.m_aVexs[route[i]].name <<")"<< "-" << route[i+1] << "(" << m_Graph.m_aVexs[route[i+1]].name <<")"<< "路长:" <<m_Graph.m_aAdjMatrix[route[i]][route[i+1]]<< endl; if (route[i+1] == end) { break; } }*/ } void FindShortPath(void) { cout << "=====搜索最短路径=====" << endl; for (int i = 0; i < m_Graph.m_nVexNum; i++) { cout << m_Graph.m_aVexs[i].num << "-" << m_Graph.m_aVexs[i].name << endl; } int nVexStart,nVexEnd,minRoute=0; /*Edge *aPath=new Edge(); for (int i = 0; i < m_Graph.m_nVexNum; i++) { aPath[i] = *new Edge(-1, -1, 0); }*/ cout << "请输入起始编号: "; cin >> nVexStart; cout << "请输入终点编号: " ; cin >> nVexEnd; FindShortPath(nVexStart, nVexEnd); /*cout << "最短路线为: " ; for (int i = 0; aPath[i].vex1 != -1; i++) { minRoute += aPath[i].weight; if (i != 0) cout << "->" << m_Graph.m_aVexs[aPath[i].vex2].name; else cout << m_Graph.m_aVexs[aPath[i].vex1].name <<"->" << m_Graph.m_aVexs[aPath[i].vex2].name; } cout << "最短距离为：" << minRoute;*/ }//通过调用m_Graph()函数查询两个景点间的最短路径和距离 void DesignPath(void) { cout << "=====铺设电路规划=====" << endl; cout << "在以下两个景点之间铺设电路：" << endl; FindMinTree(); }//电路设计
//Tourism.h #pragma once #ifndef Tourism_h #define Tourism_h void CreateGraph(void);//读取文件，创建景区景点图。 void GetSpotInfo(void);//查询指定景点信息，显示到相邻景点的距离。 void MinRoute(int begin, int end);//最短路求解 void TravelPath();//输出旅游导航路径 void FindShortPath(void);//查询最短路径 void DesignPath(void);//电路线路设计 #endif
