📄 p263.cpp
字号:
//图的邻接矩阵表示,求最短路径算法
#include "iostream.h"
#include "stdio.h"
#include "assert.h"
#include "queue.h"#include "sqlist.h"
//#include "minspantree.h"const int MaxNumEdges = 50; //最大边数
const int MaxNumVertices=10; //最大顶点数const int MAXINT=200; //权值的最大值
//const int MaxSize=MaxNumVertices; //顺序表的最大顶点数
template <class NameType, class DistType> class Graph { //图的类定义
private:
int n; //实际顶点数
// int MaxNumEdges;
// int MaxNumVertices; SeqList <NameType> VerticesList; //顶点表 DistType Edge[MaxNumVertices][MaxNumVertices]; //邻接矩阵
DistType dist[MaxNumVertices]; //存放从顶点0到其它各顶点的最短路径长度
DistType path[MaxNumVertices]; //存放在最短路径上该顶点的前一顶点的顶点号
DistType S[MaxNumVertices]; //已求得的在最短路径上的顶点的顶点号
int CurrentEdges; //当前边数
int GetVertexPos ( NameType & vertex )
{
// return FindVertex ( VerticesList(MaxNumVertices), vertex );
return FindVertex ( VerticesList, vertex );}
//给出顶点vertex在图中的位置 int FindVertex ( SeqList<NameType> &L, NameType &vertex ) { return L.Find ( vertex); } //在顶点表L中搜索顶点vertexpublic: Graph ( const int sz=MaxNumEdges ); //构造函数
int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); } //判图空否 int GraphFull ( ) const { return VerticesList.IsFull ( ) || CurrentEdges ==MaxNumEdges; } int NumberOfVertices ( ) { return VerticesList.Length(); } //返回当前顶点数 int NumberOfEdges ( ) { return CurrentEdges; } //返回当前边数 NameType GetValue ( const int i ) //取顶点i的值, i不合理则返回空 { return VerticesList.Get(i); } DistType GetWeight ( const int v1, const int v2 ); //给出以顶点v1和v2为两端点的边上的权值 int GetFirstNeighbor ( const int v ); //给出顶点位置为v的第一个邻接顶点的位置 int GetNextNeighbor ( const int v1, const int v2 ); //给出顶点位置v1的某邻接顶点v2的下一个邻接顶点 void InsertVertex ( NameType & vertex ); //插入一个顶点vertex, 该顶点没有入边 void InsertEdge ( const int v1, const int v2, DistType weight ); //插入一条边(v1, v2), 该边上的权值为weight void RemoveVertex ( const int v ); //在图中删去顶点vertex和所有与它相关联的边 void RemoveEdge ( const int v1, const int v2 ); //在图中删去边(v1,v2)// void Prim ( MinSpanTree &T ) ;// void Kruskal ( MinSpanTree &T ); //求最小生成树算法
void ShortestPath ( const int ); //求最短路径
int choose ( const int );
void BestPath(); //输出最短路径
void BellmanFord ( const int v );
void DFS ( );
void DFS ( const int v, int visited [ ] );
void BFS ( int v );
friend istream& operator >>(istream& , Graph&);};
template <class NameType, class DistType> Graph<NameType, DistType>::Graph ( int sz ):n(0){//构造函数
// SeqList <NameType> VerticesList(int sz); for ( int i=0; i<sz; i++ ) //邻接矩阵初始化 for ( int j=0; j<sz; j++ ) Edge[i][j] = MAXINT; CurrentEdges = 0; //图中当前边数初始化
};
template <class NameType, class DistType>DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2 ) {//给出以顶点v1和v2为两端点的边上的权值 if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2]; else return NULL; //带权图中权值为0, 表示无权值};template <class NameType, class DistType> int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {//给出顶点位置为v的第一个邻接顶点的位置, 如果找不到, 则函数返回-1。 if ( v != -1 ) { for ( int col=0; col<VerticesList.Length(); col++ ) if ( Edge[v][col] > 0 ) return col; } return -1;};template <class NameType, class DistType>int Graph<NameType, DistType>::GetNextNeighbor ( const int v1, const int v2 ) {//给出顶点v1的某邻接顶点v2的下一个邻接顶点 if ( v1 != -1 && v2 != -1 ) { for ( int col=v2+1; col<VerticesList.Length(); col++ ) if ( Edge[v1][col] > 0 ) return col; } return -1;};template <class NameType, class DistType>void Graph<NameType, DistType>::InsertVertex ( NameType & vertex ) //插入一个顶点vertex, 该顶点没有入边{
if(VerticesList.Length()<MaxNumVertices) VerticesList.Insert ( vertex, VerticesList.Length() ); };template <class NameType, class DistType>void Graph<NameType, DistType>:: InsertEdge ( const int v1, const int v2, DistType weight ) //插入一条边(v1, v2), 该边上的权值为weight{ CurrentEdges++; Edge[v1][v2]=weight;};template <class NameType, class DistType>istream& operator >>(istream& is, Graph<NameType,DistType>& g){ int n,e,k,j; NameType head,tail,name; DistType weight;
cout<<"please input the number of vertex"<<endl; is >> g.n; //输入顶点个数
cout<<"please input the vertex"<<endl; for ( int i=0; i<g.n; i++) { is >> name; g.InsertVertex ( name ); } //依次输入顶点, 插入图中
cout<<"please input the number of edge"<<endl; is >> e; //输入边数 cout<<"please input the edges"<<endl; for ( i=0; i<e; i++) { //依次输入边信息 is >> tail >> head >> weight; //输入各边 k = g.GetVertexPos ( tail ); j = g.GetVertexPos ( head ); //取两顶点位置 g.InsertEdge ( k, j, weight ); //插入图中 } return is;}
template <class NameType, class DistType>
void Graph< NameType, DistType>::DFS ( ) { //对连通图进行深度优先搜索的主过程
int *visited = new int [n]; //创建辅助数组
for ( int i=0; i<n; i++ ) visited [i] = 0; //辅助数组初始化
for ( i=0; i<n; i++)
if (!visited[i]) DFS (i ,visited); //从顶点0开始深度优先搜索
delete [ ] visited;
};
template <class NameType, class DistType>
void Graph< NameType, DistType>::DFS ( const int v, int visited [ ] ) { //子过程
//从顶点位置v出发, 以深度优先的次序访问所有可读入的尚未访问过的顶点。算法中用到一个辅助数组
// visited, 对已访问过的顶点作访问标记。
cout << GetValue (v) << ' '; //访问该顶点的数据
visited[v] = 1; //访问标志改为已访问过
int w = GetFirstNeighbor (v); //找顶点v的第一个邻接顶点w
while ( w != -1 ) { //有邻接顶点
if ( !visited[w] ) DFS ( w, visited ); //若未访问过, 从w递归访问
w = GetNextNeighbor ( v, w ); //找顶点v的下一个邻接顶点
}
}
template <class NameType, class DistType>
void Graph<NameType, DistType>::BFS ( int v ) {
//从顶点v出发, 以广度优先的次序横向搜索图, 算法中使用了一个队列。
int *visited = new int[n]; //visited记录顶点是否访问过
for ( int i=0; i<n; i++ ) visited[i] = 0; //初始化
cout << GetValue (v) << ' ';
visited[v] = 1; //首先访问顶点v, 做已访问标记
Queue<int> q; //q是实现分层访问的队列
q.EnQueue (v); //顶点v进队列
while ( !q.IsEmpty ( ) ) {
v = q.DeQueue ( ); //从队列中退出顶点v
int w = GetFirstNeighbor (v); //找顶点v的第一个邻接顶点
while ( w != -1 ) { //w是v的邻接顶点
if ( !visited[w] ) { //若未访问过
cout << GetValue (w) << ' '; visited[w] = 1; //访问顶点w
q.EnQueue (w); //顶点w进队列
}
w = GetNextNeighbor (v, w); //找顶点v的下一个邻接顶点
}
}
delete [ ] visited;
}
template <class NameType, class DistType>
void Graph<NameType, DistType>::ShortestPath ( const int v ) {
//G是一个具有n个顶点的带权有向图, 各边上的权值由Edge[i][j]给出。本算法建立起一个数组: dist[j], 0 < j < n,
//是当前求到的从顶点v到顶点j的最短路径长度, 同时用数组path[j], 0 < j < n, 存放求到的最短路径。
assert(((v<n) &&(v>=0)));
for ( int i=0; i<n; i++) { // dist和path数组初始化
dist[i] = Edge[v][i]; //邻接矩阵第v行元素复制到dist中
S[i] = 0; //已求出最短路径的顶点集合初始化
if ( i != v && dist[i] < MAXINT ) path[i] = v;
else path[i] = -1; //路径存放数组初始化
}
S[v] = 1; dist[v] = 0; //顶点v加入顶点集合
for ( i=0; i<n-1; i++ ) { //从顶点v确定n-1条路径
int min = MAXINT;
int u = v;
for ( int j=0; j<n; j++ ) //选择当前不在集合S中具有最短路径的顶点u
if ( !S[j] && dist[j] < min ) { u = j; min = dist[j]; }
S[u] = 1; //将顶点u加入集合S, 表示它已在最短路径上
for ( int w=0; w<n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXINT && dist[u] + Edge[u][w] < dist[w] ) {
dist[w] = dist[u] + Edge[u][w]; path[w] = u;
}
}
}
template <class NameType, class DistType>
void Graph<NameType, DistType>::BestPath()
{
NameType s;
int pos;
cout<<"shortest dist:"<<endl;
for (int i=0;i<n;i++)
{
cout<<dist[i]<<" ";
}
cout<<endl;
cout<<"shortest path:";
for (i=0;i<n;i++)
{
cout<<path[i]<<" ";
}
cout<<endl;
cout<<"输入最短路径终点："<<endl;
cin>>s;
cout<<"源点到终点的最短路径为：";
pos=GetVertexPos(s);
cout<<pos<<" ";
for (i=pos;i!=0;)
{
/* switch(path[i])
{
case 0: cout<<"顶点0: "<<"故宫"<<endl; break;
case 1: cout<<"顶点1: "<<"颐和园"<<endl; break;
case 2: cout<<"顶点2: "<<"天安门"<<endl; break;
case 3: cout<<"顶点3: "<<"长城"<<endl; break;
case 4: cout<<"顶点4: "<<"动物园"<<endl; break;
}
*/
cout<<path[i]<<" ";
i=path[i];
}
cout<<endl;
}
void main()
{
Graph <char,int> G(10);
cin>>G;
cout<<"the result of DFS"<<endl;
G.DFS();
cout<<endl;
cout<<"the result of BFS"<<endl;
G.BFS(0);
cout<<endl;
G.ShortestPath(0);
G.BestPath();
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -