406 lines
8.3 KiB
C++
406 lines
8.3 KiB
C++
/*----------------------图的邻接表示存储------------------------*/
|
||
//无向图
|
||
|
||
#define MAX_VEXNUM 20 // 最大顶点数
|
||
|
||
struct ArcNode{
|
||
int adjvex; // 该弧所指向的顶点的位置
|
||
ArcNode *nextarc; // 指向下一条弧的指针
|
||
};
|
||
|
||
template <class DT>
|
||
struct VNode{
|
||
DT data; // 顶点信息
|
||
ArcNode *firstarc; // 指向第一条依附该顶点的指针
|
||
};
|
||
|
||
template <class DT>
|
||
struct ALGraph{
|
||
VNode<DT> vertices[MAX_VEXNUM]; //顶点集
|
||
int vexnum;//顶点数
|
||
int arcnum;//边数
|
||
};
|
||
|
||
template <class DT>
|
||
void DispG(ALGraph<DT> G)
|
||
{
|
||
int i;
|
||
ArcNode *p;
|
||
cout<<G.vexnum<<"个顶点:"<<endl; //输出顶点
|
||
for(i=0;i<G.vexnum;i++)
|
||
{
|
||
cout<<G.vertices[i].data<<" ";
|
||
}
|
||
cout<<endl;
|
||
cout<<G.arcnum<<"条弧（边）:"<<endl;
|
||
for(i = 0;i<G.vexnum;i++)
|
||
{
|
||
p = G.vertices[i].firstarc;
|
||
while(p)
|
||
{
|
||
if(i<p->adjvex) //避免了无向的时候一条边被输出两次
|
||
{
|
||
cout<<"("<<G.vertices[i].data<<","
|
||
<<G.vertices[p->adjvex].data<<")"<<'\t';
|
||
}
|
||
p = p->nextarc;
|
||
}
|
||
}
|
||
cout<<endl;
|
||
}
|
||
|
||
//算法6.4 顶点定位
|
||
template <class DT>
|
||
int LocateVex(ALGraph<DT> G, DT v)
|
||
{
|
||
for(int i=0;i<G.vexnum;i++)
|
||
{
|
||
if(G.vertices[i].data == v)
|
||
{
|
||
return i;
|
||
}
|
||
}
|
||
return -1;
|
||
}
|
||
|
||
//算法6.5 创建无向图
|
||
template <class DT>
|
||
void CreateUDG(ALGraph<DT> &G)
|
||
{
|
||
int i,j,k;
|
||
DT v1,v2;
|
||
ArcNode *p;
|
||
cout<<"请输入无向图的顶点数 "; // 1. 输入顶点数、边数
|
||
cin>>G.vexnum ;
|
||
cout<<"请输入无向图的边数 ";
|
||
cin>>G.arcnum ;
|
||
cout<<"请输入"<<G.vexnum<<"个顶点的值"<<endl; // 2. 输入顶点值
|
||
for(i = 0;i<G.vexnum;i++) // 初始化顶点结点
|
||
{
|
||
cin>>G.vertices[i].data;
|
||
G.vertices[i].firstarc = NULL;
|
||
}
|
||
for(k=0;k<G.arcnum;k++) //构造表结点链表
|
||
{
|
||
cout<<"请输入边的两个顶点值: "<<endl;
|
||
cin>>v1>>v2;
|
||
i = LocateVex(G,v1);
|
||
j = LocateVex(G,v2);
|
||
if(i<0 || j<0 || i==j)
|
||
{
|
||
cout<<"顶点信息错，重新输入！"<<endl;
|
||
k--;
|
||
continue;
|
||
}
|
||
p = new ArcNode; // 创建一个新的边
|
||
p->adjvex = j;
|
||
p->nextarc = G.vertices[i].firstarc; // 在v1链表表头插入新边结点
|
||
G.vertices[i].firstarc = p;
|
||
p = new ArcNode; // 创建一个新的边
|
||
p->adjvex = i;
|
||
p->nextarc = G.vertices[j].firstarc; // 在v2链表表头插入新边结点
|
||
G.vertices[j].firstarc = p;
|
||
}
|
||
}
|
||
|
||
|
||
template <class DT>
|
||
void DestroyGraph(ALGraph<DT> G) // 销毁边结点
|
||
{
|
||
int i;
|
||
ArcNode *p,*q;
|
||
for(i = 0;i<G.vexnum;i++) // 从顶点序号为0的顶点开始依次释放掉相应的邻接表
|
||
{
|
||
p = G.vertices[i].firstarc;
|
||
while(p)
|
||
{
|
||
q = p->nextarc;
|
||
delete p; // 删除边结点
|
||
p = q;
|
||
}
|
||
}
|
||
G.arcnum = 0;
|
||
G.vexnum = 0;
|
||
}
|
||
|
||
template <class DT>
|
||
bool GetVex(ALGraph<DT> G, int k,DT &v) // 获取第 k 个顶点的值
|
||
{
|
||
if(k<0||k>=G.vexnum) // 顶点不存在，返回false
|
||
return false;
|
||
v=G.vertices[k].data; // 顶点存在，获取第 k 个顶点的值
|
||
return true; // 返回true
|
||
}
|
||
|
||
template <class DT>
|
||
bool PutVex(ALGraph<DT> &G, DT &u,DT v) // 修改顶点 u 的值
|
||
{
|
||
int k = LocateVex(G,u);
|
||
if(k<0) // 顶点 u 不存在
|
||
return false;
|
||
G.vertices[k].data = v; // 重置顶点u的值
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
int FirstAdjVex(ALGraph<DT> G, int u) // 求顶点 u 的第一个邻接点
|
||
{
|
||
ArcNode * p;
|
||
if(u<0 || u>=G.vexnum) // 顶点 u 不存在
|
||
return -1;
|
||
p = G.vertices[u].firstarc; // 顶点u存在，有邻接点，p 为第一个邻接点位序
|
||
if(p)
|
||
{
|
||
return p->adjvex;
|
||
}
|
||
else
|
||
{
|
||
return -1;
|
||
}
|
||
}
|
||
|
||
template <class DT>
|
||
int NextAdjVex(ALGraph<DT> G, int u,int w) // 求顶点 u 相对于 w 的下一个邻接点
|
||
{
|
||
ArcNode *p;
|
||
if(u<0 || u>=G.vexnum || w<0
|
||
|| w>=G.vexnum ) // 参数不合理
|
||
return -1;
|
||
p = G.vertices[u].firstarc; // 从 u 的边链表出发
|
||
while( p && (p->adjvex!=w)) // 找 w 边结点
|
||
{
|
||
p = p->nextarc;
|
||
}
|
||
if(!p||!p->nextarc) // 没找到 w 或 w 是最后一个顶点
|
||
return -1;
|
||
else // 否则，返回下一个邻接点位序
|
||
{
|
||
return p->nextarc->adjvex;
|
||
}
|
||
}
|
||
|
||
template <class DT>
|
||
bool InsertVex(ALGraph<DT> &G, DT v) // 增加顶点
|
||
{
|
||
int j;
|
||
char ans;
|
||
DT w;
|
||
if(G.vexnum > MAX_VEXNUM) // 顶点数为最多顶点数，不能增加新顶点
|
||
{
|
||
cout<<"无存储空间，不能插入!"<<endl;
|
||
return false;
|
||
}
|
||
G.vertices[G.vexnum].data = v; // 在顶点信息表中新增顶点
|
||
G.vertices[G.vexnum].firstarc = NULL;
|
||
G.vexnum++; // 顶点数增1
|
||
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<<"\n顶点不存在！";
|
||
cout<<"继续创建边吗（Y/N)?"<<endl;
|
||
cin>>ans;
|
||
};
|
||
return true;
|
||
}
|
||
|
||
|
||
template <class DT>
|
||
bool InsertArc(ALGraph<DT> &G, DT v,DT w) // 增加边(v,w)
|
||
{
|
||
ArcNode *p;
|
||
int i,j;
|
||
i = LocateVex(G,v);
|
||
j = LocateVex(G,w);
|
||
if(i<0||j<0 || i==j) // 顶点不存在或两端点相同,不能插入
|
||
{
|
||
cout<<"\n顶点不存在或两顶点相同，不能插入！"<<endl;
|
||
return false;
|
||
}
|
||
p=G.vertices[i].firstarc; // 边已存在，不能新增
|
||
while(p)
|
||
{
|
||
if(p->adjvex==j)
|
||
{
|
||
cout<<"边存在，不能插入！"<<endl;
|
||
return false;
|
||
}
|
||
p=p->nextarc;
|
||
}
|
||
G.arcnum++; // 边数增 1
|
||
p = new ArcNode;
|
||
p->adjvex = j;
|
||
p->nextarc = G.vertices[i].firstarc; // (v,w)边结点插在第i条链表表头
|
||
G.vertices[i].firstarc = p;
|
||
p = new ArcNode;
|
||
p->adjvex = i; // (w,v)边结点插在第j链表表头
|
||
p->nextarc = G.vertices[j].firstarc;
|
||
G.vertices[j].firstarc = p;
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
bool DeleteArc(ALGraph<DT> &G, DT v,DT w) // 删除边(v,w)
|
||
{
|
||
ArcNode *p,*q;
|
||
int i,j;
|
||
cout<<"Hello DeleteArc!"<<endl;
|
||
cout<<"删除边顶点为："<<endl;
|
||
cout<<"("<<v<<","<<w<<")"<<endl;
|
||
i = LocateVex(G,v);
|
||
j = LocateVex(G,w);
|
||
if(i<0||j<0||i == j) // 边(v,w)不存在，不能删除
|
||
{
|
||
cout<<"\n边不存在！"<<endl;
|
||
return false;
|
||
}
|
||
p = G.vertices[i].firstarc; // 寻找边(v,w)的边结点
|
||
while(p && p->adjvex!=j) // p 不空且 p 指向的不是待删弧结点
|
||
{
|
||
q = p;
|
||
p = p->nextarc;
|
||
}
|
||
if(p&&p->adjvex ==j) // 找到边(v,w)
|
||
{
|
||
if(p == G.vertices[i].firstarc) // 第 1 个边结点
|
||
{
|
||
G.vertices[i].firstarc = p->nextarc;
|
||
}
|
||
else // 非第 1 个边结点
|
||
{
|
||
q->nextarc = p->nextarc;
|
||
}
|
||
delete p;
|
||
G.arcnum--;
|
||
p = G.vertices[j].firstarc;
|
||
while(p&&p->adjvex!=i) // p不空且q指向的不是待删弧结点
|
||
{
|
||
q = p;
|
||
p = p->nextarc;
|
||
}
|
||
if(p == G.vertices[j].firstarc) // 第 1 个边结点
|
||
{
|
||
G.vertices[j].firstarc = p->nextarc;
|
||
}
|
||
else // 非第1个边结点
|
||
{
|
||
q->nextarc = p->nextarc;
|
||
}
|
||
delete p;
|
||
}
|
||
cout<<"Bye-bye DeleteArc!"<<endl;
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
bool DeleteVex(ALGraph<DT> &G, DT v) // 删除顶点v
|
||
{
|
||
int i,j;
|
||
ArcNode *p;
|
||
DT w;
|
||
i = LocateVex(G,v);
|
||
if(i<0)
|
||
{
|
||
cout<<"顶点不存在！"<<endl; // 顶点不存在
|
||
return false;
|
||
}
|
||
p = G.vertices[i].firstarc;
|
||
while(p) // 删除以 v 为邻接点边
|
||
{
|
||
j=p->adjvex;
|
||
GetVex(G,j,w);
|
||
DeleteArc(G,v,w);
|
||
p=G.vertices[i].firstarc;
|
||
}
|
||
for(j=i+1;j<G.vexnum;j++) // 顶点v后面的顶点前移
|
||
{
|
||
G.vertices[j-1].data = G.vertices[j].data;
|
||
G.vertices[j-1].firstarc=G.vertices[j].firstarc;
|
||
}
|
||
G.vexnum--; // 顶点数减一
|
||
return true;
|
||
}
|
||
|
||
// 算法6.8
|
||
template <class DT>
|
||
void DFS(ALGraph<DT> G, int v) // 连通图的深度优先遍历
|
||
{
|
||
int w;
|
||
visited[v] = true; // 标识已访问
|
||
cout<<G.vertices[v].data; // 访问顶点
|
||
for(w = FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) // 遍历v的邻接点w
|
||
{
|
||
if(!visited[w]) // 未访问，调用DFS
|
||
DFS(G,w);
|
||
}
|
||
}
|
||
|
||
// 算法6.9
|
||
template <class DT>
|
||
void DFSTraverse(ALGraph<DT> G) // 邻接表存储的图的深度优先遍历
|
||
{
|
||
int i ;
|
||
for(i = 0;i<G.vexnum;i++) // 初始化访问标志
|
||
visited[i] = false;
|
||
for(i = 0;i<G.vexnum;i++) // 对每个未被访问的顶点进行DFS
|
||
{
|
||
if(!visited[i])
|
||
DFS(G,i);
|
||
}
|
||
return;
|
||
}
|
||
|
||
// 算法6.13
|
||
template <class DT>
|
||
void BFS(ALGraph<DT> G, int v) // 连通图的广度优先遍历
|
||
{
|
||
int w;
|
||
ArcNode *p;
|
||
LinkQueue<int> Q;
|
||
InitQueue(Q);
|
||
cout<<G.vertices[v].data;
|
||
visited[v]=true;
|
||
EnQueue(Q,v);
|
||
while(!QueueEmpty(Q))
|
||
{
|
||
DeQueue(Q,v);
|
||
p=G.vertices[v].firstarc;
|
||
while(p)
|
||
{
|
||
w=p->adjvex;
|
||
if(!visited[w])
|
||
{
|
||
cout<<G.vertices[w].data;
|
||
visited[w]=true;
|
||
EnQueue(Q,w);
|
||
}
|
||
p=p->nextarc;
|
||
}
|
||
}
|
||
}
|
||
|
||
|
||
template <class DT>
|
||
bool BFSTraverse(ALGraph<DT> G) // 邻接表存储的图的广度优先遍历
|
||
{
|
||
int i;
|
||
for(i = 0;i<G.vexnum;i++) // 初始化访问标志
|
||
visited[i] = false;
|
||
for(i = 0;i<G.vexnum;i++) // 对每个未被访问的顶点进行BFS
|
||
if(!visited[i])
|
||
BFS(G,i);
|
||
//cout<<endl;
|
||
return true;
|
||
}
|
||
|
||
|
||
|
||
|
||
|