310 lines
6.5 KiB
C++
310 lines
6.5 KiB
C++
/*--------------------------无向图的邻接矩阵表示-----------------------------*/
|
||
|
||
#define MAX_VEXNUM 20 // 最大顶点数
|
||
|
||
template <class DT>
|
||
struct MGraph // 图的邻接矩阵表示存储定义
|
||
{
|
||
DT vexs[MAX_VEXNUM]; // 顶点信息
|
||
int arcs[MAX_VEXNUM][MAX_VEXNUM];
|
||
int vexnum,arcnum; // 顶点数和边数
|
||
};
|
||
|
||
|
||
template <class DT>
|
||
void DispG(MGraph<DT> G) // 显示图信息
|
||
{
|
||
int i,j;
|
||
DT u,v;
|
||
cout<<G.vexnum<<"个顶点："<<endl;
|
||
for(i=0;i<G.vexnum;i++)
|
||
cout<<G.vexs[i]<<" ";
|
||
cout<<endl;
|
||
cout<<G.arcnum<<"条边信息如下："<<endl;
|
||
for(i=0;i<G.vexnum;i++)
|
||
{
|
||
for(j=i+1;j<G.vexnum;j++)
|
||
if (G.arcs[i][j]!=0)
|
||
{
|
||
GetVex(G,i,u);
|
||
GetVex(G,j,v);
|
||
cout<<'('<<u<<","<<v<<")"<<'\t';
|
||
}
|
||
}
|
||
cout<<endl;
|
||
}
|
||
|
||
|
||
//算法6.1 顶点定位
|
||
template <class DT>
|
||
int LocateVex(MGraph<DT> G,DT v)
|
||
{
|
||
for(int i = 0;i<G.vexnum;i++)
|
||
{
|
||
if(G.vexs[i] == v)
|
||
{
|
||
return i;
|
||
}
|
||
}
|
||
return -1;
|
||
}
|
||
|
||
//6.2 创建无向图
|
||
template <class DT>
|
||
void CreateUDG(MGraph<DT> &G)
|
||
{
|
||
int i,j,k;
|
||
DT v1,v2;
|
||
cout<<"请输入无向图的顶点数 "; // 1. 输入顶点数、边数
|
||
cin>>G.vexnum ;
|
||
cout<<"请输入无向图的边数 ";
|
||
cin>>G.arcnum ;
|
||
cout<<"请输入"<<G.vexnum<<"个顶点的值（单个字符）"<<endl; // 2. 输入顶点值
|
||
for(i = 0;i<G.vexnum;i++)
|
||
cin>>G.vexs[i];
|
||
for(i=0;i<G.vexnum;i++) // 3.邻接矩阵初始化
|
||
for(j=0;j<G.vexnum;j++)
|
||
G.arcs[i][j]=0;
|
||
cout<<"请输入各条边的两个邻接点"<<endl; // 4.创建各条边
|
||
for( k=0;k<G.arcnum;k++)
|
||
{
|
||
cout<<"输入第"<<k<<"条边的两个顶点："<<endl;
|
||
cin>>v1>>v2; // 4.1 输入边的两个邻接点
|
||
i = LocateVex(G,v1); // 4.2 定位两个邻接点
|
||
j = LocateVex(G,v2);
|
||
if(i<0 || j<0 || i==j)
|
||
{
|
||
cout<<"顶点信息错，重新输入！"<<endl;
|
||
k--;
|
||
continue;
|
||
}
|
||
G.arcs[i][j]=1; // 4.3 修改邻接矩阵
|
||
G.arcs[j][i]=1;
|
||
}
|
||
}
|
||
|
||
|
||
template <class DT>
|
||
bool GetVex(MGraph<DT> G, int k, DT &v) // 获取第 u 个顶点值v
|
||
{
|
||
if(k<0 || k>=G.vexnum) // u不存在，返回false
|
||
return false;
|
||
else
|
||
{
|
||
v=G.vexs[k];
|
||
return true;
|
||
}
|
||
}
|
||
|
||
|
||
template <class DT>
|
||
bool PutVex(MGraph<DT> &G,DT &u,DT v) // 为第u个顶点赋值
|
||
{
|
||
int k;
|
||
k=LocateVex(G,u);
|
||
if(k<0 ) // u不存在，返回false
|
||
return false;
|
||
else // u存在，赋值
|
||
{
|
||
G.vexs[k] = v;
|
||
return true;
|
||
}
|
||
}
|
||
|
||
//算法6.3 按值查找第一邻接点
|
||
template <class DT>
|
||
int FirstAdjvex(MGraph<DT> G,int u)
|
||
{
|
||
if(u<0 || u>=G.vexnum) // 顶点不存在
|
||
return -1; // 无邻接点，返回-1
|
||
for(int j=0;j<G.vexnum;j++) // 扫描邻接矩阵第u行
|
||
if(G.arcs[u][j]!=0) // 如果有非零元，
|
||
return j; // 第一个非零元所在列号，为其邻接点序号
|
||
return -1; // 否则，无邻接点，返回-1
|
||
}
|
||
|
||
template <class DT>
|
||
int NextAdjvex(MGraph<DT> G,int u,int w) //查找第u个顶点邻接点W的下一个邻接点
|
||
{
|
||
if(u<0 || u>=G.vexnum || w<0
|
||
|| w>=G.vexnum || G.arcs[u][w]==0 ) // 参数不合理
|
||
return -1; // 无邻接点
|
||
for(int j=w+1;j<G.vexnum;j++) // 扫描邻接矩阵第u行w列后的元素
|
||
if(G.arcs[u][j]!=0) // 如果有非零元，
|
||
return j; // 第一个非零元所在列号，为其邻接点序号
|
||
return -1; // 否则无邻接点，返回-1
|
||
}
|
||
|
||
|
||
template <class DT>
|
||
bool InsertVex(MGraph<DT> &G,DT v) // 插入值为v的顶点
|
||
{
|
||
DT w;
|
||
int j;
|
||
char ans;
|
||
if(G.vexnum>=MAX_VEXNUM) // 无存储空间，不能插入
|
||
{
|
||
cout<<"无存储空间，不能插入!"<<endl;
|
||
return false;
|
||
}
|
||
G.vexs[G.vexnum++]= v; // 顶点信息加入至G.vexs中，顶点数增1
|
||
for(j=0;j<G.vexnum;j++) // 初始化邻接矩阵最后一行和最后一列值
|
||
{
|
||
G.arcs[G.vexnum-1][j]=0;
|
||
G.arcs[j][G.vexnum-1]=0;
|
||
}
|
||
cout<<"创建边吗（Y/N)?"<<endl;
|
||
cin>>ans;
|
||
while(ans=='Y'|| ans=='y')
|
||
{
|
||
cout<<"输入另一个顶点值"<<endl;
|
||
cin>>w;
|
||
j=LocateVex(G,w);
|
||
if(j>=0) // 顶点存在
|
||
InsertArc(G,v,w);
|
||
else
|
||
cout<<w<<"顶点不存在！";
|
||
cout<<"继续创建边吗（Y/N)?"<<endl;
|
||
cin>>ans;
|
||
};
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
bool InsertArc(MGraph<DT> &G,DT v,DT w) // 在值为v、w顶点间加边
|
||
{ int i = LocateVex(G,v);
|
||
int j = LocateVex(G,w);
|
||
if(i<0 || j<0 || i==j) // 顶点不存在或两端点相同
|
||
{
|
||
cout<<"\n顶点不存在或两顶点相同，不能插入！"<<endl;
|
||
return false;
|
||
}
|
||
return false; // 不能插入边，返回false
|
||
if(G.arcs[i][j]==1)
|
||
{
|
||
cout<<"\n边已存在，不能插入！"<<endl;
|
||
return false;
|
||
}
|
||
G.arcs[i][j]=1;
|
||
G.arcs[j][i]=1;
|
||
G.arcnum++;
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
bool DeleteArc(MGraph<DT> &G,DT v,DT w) // 按顶点值删除边
|
||
{
|
||
int i = LocateVex(G,v);
|
||
int j = LocateVex(G,w);
|
||
if(i<0||j<0||i == j) // 边不存在，返回false
|
||
{
|
||
cout<<"边不存在！"<<endl;
|
||
return false;
|
||
}
|
||
G.arcs[i][j]=0; // 置邻接矩阵第 i 行第 j 列为零
|
||
G.arcs[j][i]=0; // 置邻接矩阵第 i 列第 j 行为零
|
||
G.arcnum--; // 边数减1
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
bool DeleteVex(MGraph<DT> &G,DT v) // 按值删除顶点
|
||
{
|
||
int i,j;
|
||
DT w;
|
||
i = LocateVex(G,v); // 顶点定位
|
||
if(i<0)
|
||
{
|
||
cout<<"顶点不存在！"<<endl; // 顶点不存在
|
||
return false;
|
||
}
|
||
for(j=0;j<G.vexnum;j++) // 删除与顶点v相连的边
|
||
{
|
||
if(G.arcs[i][j]!=0)
|
||
{
|
||
GetVex(G,j,w);
|
||
DeleteArc(G,v,w);
|
||
}
|
||
}
|
||
for(j=i+1;j<G.vexnum;j++) // 排在顶点v后面的顶点前移
|
||
{
|
||
G.vexs[j-1] = G.vexs[j];
|
||
}
|
||
G.vexnum--;
|
||
return true;
|
||
}
|
||
|
||
|
||
// 算法6.10
|
||
template <class DT>
|
||
void DFS2(MGraph<DT> G,int v) // 连通图深度优先遍历
|
||
{
|
||
int w;
|
||
visited[v] = true; // 先访问index
|
||
cout<<G.vexs[v];
|
||
for(w=0;w<G.vexnum;w++)
|
||
{
|
||
if(G.arcs[v][w]!=0 && !visited[w] )
|
||
DFS2(G,w);
|
||
}
|
||
//cout<<endl;
|
||
}
|
||
|
||
// 算法6.9
|
||
template <class DT>
|
||
void DFSTraverse(MGraph<DT> G) // 非连通图深度优先遍历
|
||
{
|
||
int i;
|
||
for(i=0;i<G.vexnum;i++) // 访问标志初始化
|
||
visited[i]=0;
|
||
for( i=0;i<G.vexnum;i++) // 对未被访问的顶点
|
||
{
|
||
if(!visited[i])
|
||
DFS2(G,i); // 进行深度优先递归
|
||
}
|
||
cout<<endl;
|
||
return ;
|
||
}
|
||
|
||
// 算法 6.11 广度优先遍历
|
||
template <class DT>
|
||
void BFS(MGraph<DT> G,int v)
|
||
{
|
||
int w;
|
||
LinkQueue<int> Q; // 创建一个队列
|
||
InitQueue(Q);
|
||
cout<<G.vexs[v]; // 访问顶点v
|
||
visited[v]=true; // 做访问标志
|
||
EnQueue(Q,v); // 入队
|
||
while(!QueueEmpty(Q)) // 队非空
|
||
{
|
||
DeQueue(Q,v); // 出队
|
||
for(w=FirstAdjvex(G,v);w>=0;w=NextAdjvex(G,v,w)) // 遍历v的邻接点
|
||
if(!visited[w]) // 未被访问
|
||
{
|
||
cout<<G.vexs[w]; // 访问
|
||
visited[w]=true; // 做访问标志
|
||
EnQueue(Q,w); // 入队
|
||
}
|
||
}
|
||
}
|
||
|
||
// 算法6.12
|
||
template <class DT>
|
||
void BFSTraverse(MGraph<DT> G) // 广度优先遍历
|
||
{
|
||
int i;
|
||
for(i=0;i<G.vexnum;i++) // 访问标志初始化
|
||
visited[i]=0;
|
||
for(i=0;i<G.vexnum;i++) // 对未被访问的结点
|
||
{
|
||
if(!visited[i])
|
||
BFS(G,i); // 进行BFS遍历
|
||
}
|
||
|
||
}
|
||
|
||
|
||
|
||
|