#include<iostream>
#define MAX_VERTEX_NUM 30
#define NULL 0
#define OK 1
using namespace std;
bool visit[MAX_VERTEX_NUM];
typedef struct ArcNode //定义边结点
{
int adjvex;
ArcNode *nextarc;
}ArcNode;
typedef struct VNode //定义顶点结点
{
char data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct //定义无向图
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct node //定义结点
{
int data;
node *next;
}*Link;
typedef struct //定义链表
{
Link head,tail;
int len;
}LinkList;
int InitList(LinkList &L)//构造一个带头结点和尾结点的空的线性链表L
{
L.head=new node;
L.head->next=L.tail=new node;
L.tail->next=NULL;
L.len=0;
return 0;
}
void add(LinkList &L,int e)//在线性链表L的结尾添加一个结点
{
Link q=new node;
L.tail->next=q;
L.tail->data=e;
L.tail=q;
L.tail->next=NULL;
L.len++;
}
void Delete(LinkList &L,int &e)//出列，并将出列的元素值用e返回
{
if(L.head->next==L.tail)
{
cout<<"队列为空"<<endl;
e=NULL;
}
else
{
Link p,q;
p=L.head->next;
q=p->next;
L.head->next=q;
e=p->data;
delete p;
L.len--;
}
}
void ArcAdd(ALGraph &G,int m,int n)//在无向图中添加以m,n为顶点的边
{
ArcNode *p,*h,*q;
p=new ArcNode;
p->adjvex=m;
p->nextarc=NULL;
h=q=G.vertices[n].firstarc;
if(q==NULL)
G.vertices[n].firstarc=p;
else
{
if((p->adjvex)>(q->adjvex))
{
p->nextarc=q;
G.vertices[n].firstarc=p;
}
else
{
while(G.vertices[n].firstarc!=NULL&&q->nextarc!=NULL&&(p->adjvex)<(q->adjvex))//使邻接表中边的数据按大到小排列。
{
h=q;
q=q->nextarc;
}
if(q->nextarc==NULL&&(p->adjvex)<(q->adjvex))
{
q->nextarc=p;
}
else
{
p->nextarc=q;
h->nextarc=p;
}
}
}
}
int CreateDG(ALGraph &G) //创建无向图
{
int v,a,m,n;
ArcNode *p,*q,*h;
cout<<"请输入顶点个数和边数."<<endl;
cout<<"请输入顶点数:";
cin>>v;
cout<<"请输入边数:";
cin>>a;
G.vexnum=v;
G.arcnum=a;
for(int i=1;i<=G.vexnum;i++)
{
char t;
cout<<"请输入顶点值:";
cin>>t;
G.vertices[i].data=t;
G.vertices[i].firstarc=NULL;
}
for(int k=1;k<=G.arcnum;k++)
{
cout<<"请输入边的信息."<<endl;
cout<<"请输入第"<<k<<"条边的起点:";
cin>>m;
cout<<"请输入第"<<k<<"条边的终点:";
cin>>n;
if(m<=v&&n<=v&&m>0&&n>0)
{
ArcAdd(G,m,n);
ArcAdd(G,n,m);
}
else
{
cout<<"你的输入有误."<<endl;
return 0;
}
}
return 0;
}
void show(ALGraph G) //在屏幕上输入无向图的邻接表存储形式
{
cout<<"无向图的创建完成,该图的邻接表表示为:"<<endl;
ArcNode *p;
for(int i=1;i<=G.vexnum;i++)
{
if(G.vertices[i].firstarc==NULL)
cout<<i<<G.vertices[i].data<<"-->NULL"<<endl;
else
{
p=G.vertices[i].firstarc;
cout<<i<<G.vertices[i].data<<"-->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"-->";
p=p->nextarc;
}
cout<<p->adjvex<<"-->NULL"<<endl;
}
}
}
void VisitFunc(char a) //对无向图的数据进行访问的函数
{
cout<<a<<" ";
}
int FirstAdjVex(ALGraph G,int v)//返回v的第一个邻接顶点。若顶点在G中没有邻接表顶点，则返回“空”。
{
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
else
return NULL;
}
int NextAdjVex(ALGraph G,int v,int w) //返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“回”。
{
ArcNode *p;
if(G.vertices[v].firstarc==NULL)
return NULL;
else
{
p=G.vertices[v].firstarc;
while(p->adjvex!=w)
{
p=p->nextarc;
}
if(p->nextarc==NULL)
return NULL;
else
return p->nextarc->adjvex;
}
}
void DFS(ALGraph G,int v)//从第v个顶点出发递归地深度优先遍历图G。
{
visit[v]=true;
VisitFunc(G.vertices[v].data);
for(int w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w))
if(!visit[w])
DFS(G,w);
}
void DFSTraverse(ALGraph G)//对图G作深度优先遍历。
{
cout<<"深度优先搜索的结果为:"<<endl;
for(int v=1;v<=G.vexnum;v++)
visit[v]=false;
for(int m=1;m<=G.vexnum;m++)
if(!visit[m])
DFS(G,m);
cout<<endl;
}
void BFSTraverse(ALGraph G)//对图G作广度优先遍历。
{
cout<<"广度优先搜索的结果为:"<<endl;
LinkList Q;
int u;
for(int m=1;m<=G.vexnum;m++)
visit[m]=false;
InitList(Q);//借助辅助队列。
for(int v=1;v<=G.vexnum;v++)
if(!visit[v])
{
visit[v]=true;
VisitFunc(G.vertices[v].data);
add(Q,v);
while(Q.len!=0)
{
Delete(Q,u);
for(int w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w))
if(!visit[w])
{
visit[w]=true;
VisitFunc(G.vertices[w].data);
add(Q,w);
}
}
}
cout<<endl;
}
int main()//主函数
{
ALGraph G;
CreateDG(G);
show(G);
DFSTraverse(G);
BFSTraverse(G);
return 0;
}