416 lines
7.4 KiB
C++
416 lines
7.4 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;
|
||
}
|
||
|
||
|
||
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;
|
||
}
|
||
|
||
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;
|
||
}
|
||
//cout<<"请输入每条边两个邻接点： "<<endl;
|
||
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; //插在表头
|
||
G.vertices[i].firstarc = p;
|
||
p = new ArcNode; //创建一个新的弧结点
|
||
p->adjvex = i;
|
||
p->nextarc = G.vertices[j].firstarc; //插在表头
|
||
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)
|
||
{
|
||
if(k<0||k>=G.vexnum) //顶点不存在
|
||
return false;
|
||
v=G.vertices[k].data;
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
bool PutVex(ALGraph<DT> &G, DT &u,DT v)
|
||
{
|
||
int k = LocateVex(G,u);
|
||
if(k<0) //该顶点不存在
|
||
return false;
|
||
G.vertices[k].data = v;
|
||
return true;
|
||
}
|
||
|
||
template <class DT>
|
||
int FirstAdjVex(ALGraph<DT> G, int u)
|
||
{
|
||
ArcNode * p;
|
||
if(u<0 || u>=G.vexnum) // 顶点不存在
|
||
return -1;
|
||
p = G.vertices[u].firstarc;//p指向下标为i的第一个邻接点
|
||
if(p)
|
||
{
|
||
return p->adjvex;
|
||
}
|
||
else
|
||
{
|
||
return -1;
|
||
}
|
||
}
|
||
|
||
template <class DT>
|
||
int NextAdjVex(ALGraph<DT> G, int u,int w)
|
||
{
|
||
ArcNode *p;
|
||
if(u<0 || u>=G.vexnum || w<0
|
||
|| w>=G.vexnum ) // 参数不合理
|
||
return -1;
|
||
p = G.vertices[u].firstarc;
|
||
while(p &&(p->adjvex!=w))
|
||
//让p指向顶点w
|
||
{
|
||
p = p->nextarc;
|
||
}
|
||
if(!p||!p->nextarc) //没找到w或w是最后一个顶点
|
||
return -1;
|
||
else
|
||
//找到w且w不是最后一个顶点
|
||
{
|
||
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++;
|
||
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)
|
||
{
|
||
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++;
|
||
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)
|
||
{
|
||
ArcNode *p,*q;
|
||
int i,j;
|
||
cout<<"Hello DeleteArc!"<<endl;
|
||
cout<<"删除边顶点为："<<endl;
|
||
cout<<"("<<v<<","<<w<<")"<<endl;
|
||
i = LocateVex(G,v);
|
||
j = LocateVex(G,w);
|
||
cout<<"删除边顶点序号为："<<endl;
|
||
cout<<"("<<i<<","<<j<<")"<<endl;
|
||
if(i<0||j<0||i == j)
|
||
{
|
||
cout<<"\n边不存在！"<<endl;
|
||
return false;
|
||
}
|
||
p = G.vertices[i].firstarc;
|
||
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)
|
||
{
|
||
int i,j;
|
||
ArcNode *p;
|
||
DT w;
|
||
i = LocateVex(G,v);
|
||
cout<<"将删除第"<<i<<"个顶点！"<<endl;
|
||
if(i<0)
|
||
{
|
||
cout<<"顶点不存在！"<<endl; // 顶点不存在
|
||
return false;
|
||
}
|
||
p = G.vertices[i].firstarc;
|
||
while(p) // 删除以v为邻接点边
|
||
{
|
||
j=p->adjvex;
|
||
cout<<"删除边顶点序号为："<<endl;
|
||
cout<<"("<<i<<","<<j<<")"<<endl;
|
||
GetVex(G,j,w);
|
||
cout<<"删除边顶点为："<<endl;
|
||
cout<<"("<<v<<","<<w<<")"<<endl;
|
||
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))
|
||
{
|
||
if(!visited[w])
|
||
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++) //对每个未被访问的顶点进行深度优先遍历
|
||
{
|
||
if(!visited[i])
|
||
DFS(G,i);
|
||
}
|
||
//cout<<endl;
|
||
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++)
|
||
if(!visited[i])
|
||
BFS(G,i);
|
||
//cout<<endl;
|
||
return true;
|
||
}
|
||
|
||
|
||
|
||
|
||
|