无向图的存储与遍历

    很多涉及图上操作的算法都是以图的遍历操作为基础的。下面为我写的一个演示无向图的遍历操作。

 

基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。分别输出每种遍历下结点的访

        问序列。设图的结点不超过30个，每个结点用一个编号表示（如果一个图有N个结点，则它们的编号

        分别为1，2。。。N）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺

        序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

源码：

 

#include
#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<<"队列为空"<  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<<"请输入顶点个数和边数."< 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<<"请输入边的信息."<  cout<<"请输入第"<  cin>>m;
  cout<<"请输入第"<  cin>>n;
  if(m<=v&&n<=v&&m>0&&n>0)
  {
   ArcAdd(G,m,n);
   ArcAdd(G,n,m);
  }
  else
  {
   cout<<"你的输入有误."<   return 0;
  }
 }
 return 0;
}
void show(ALGraph G)  //在屏幕上输入无向图的邻接表存储形式
{
 cout<<"无向图的创建完成,该图的邻接表表示为:"< ArcNode *p;
 for(int i=1;i<=G.vexnum;i++)
 {
  if(G.vertices[i].firstarc==NULL)
   cout<NULL"<  else
  {
   p=G.vertices[i].firstarc;
   cout<";
   while(p->nextarc!=NULL)
   {
    cout<adjvex<<"-->";
    p=p->nextarc;
   }
   cout<adjvex<<"-->NULL"<  }
 }
}
void VisitFunc(char a)  //对无向图的数据进行访问的函数
{
 cout<}
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<<"深度优先搜索的结果为:"< 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<}
void BFSTraverse(ALGraph G)//对图G作广度优先遍历。
{
 cout<<"广度优先搜索的结果为:"< 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<}
int main()//主函数
{
 ALGraph G;
 CreateDG(G);
 show(G);
 DFSTraverse(G);
 BFSTraverse(G);
 return 0;
}