tutrav.cpp

此程序用来求图的遍历问题……题中采用的是图的邻接矩阵存储

#include <stdio.h>
#include <malloc.h>
#include<iostream.h>
#define max 20
typedef int VexType;
int w;
int visited[max];
typedef struct arcnode
{
 int adjvex;//该弧指向的顶点的位置
 struct arcnode *next;//弧尾相同的下一条弧
}arcnode;

typedef struct vexnode
{
VexType data;//结点信息
 arcnode *firstarc;//指想第一条依附该结点的弧的指针
}vexnode;
typedef struct
{
 vexnode g[max];
 int vexnum,arcnum;
}Graph;


typedef struct Qnode
{
int data;
 struct Qnode *next;
}QNode,*Qptr;

typedef struct
{
 Qptr front;
 Qptr rear;
}Queue;



int LocateVex(Graph G,VexType v){
	int i=0;
	while(i<G.vexnum&&G.g[i].data!=v)
		i++;
	return i;
	}

void CreateAdjList(Graph &G)
{   int i,m,n;
	VexType v1,v2; 
	arcnode *p,*q;
 printf("输入图中结点个数v（0<v<100）：\n");
 scanf("%d",&G.vexnum);
 printf("输入图中弧个数arc(0<arc<100)：\n");
 scanf("%d",&G.arcnum);
 
 for(i=0;i<G.vexnum;)
 {
 printf("请输入第%d个结点值：\n",i+1);
  scanf("%d",&G.g[i].data);
  G.g[i++].firstarc=NULL;
 }
   
 for(i=0;i<G.arcnum;i++)
	{//对每一条边
	   printf("请输入第%d条边的两个结点值：\n",i+1);
	scanf("%d %d",&v1,&v2);
	m=LocateVex(G,v1);
	n=LocateVex(G,v2);
	p=(arcnode *)malloc(sizeof(arcnode));
	p->adjvex=n;
	p->next=G.g[m].firstarc;
	G.g[m].firstarc=p;
	q=(arcnode *)malloc(sizeof(arcnode));
	q->adjvex=m;
	q->next=G.g[n].firstarc;
	G.g[n].firstarc=q;
	}//for
   for(i=0;i<G.vexnum;i++)
	   { 
	   printf("\n位置为%d的结点值为：v%d\n",i,G.g[i].data);
	   p=G.g[i].firstarc; 
	   if(p)
		   printf("该点邻接点的位置：");
	   while(p){
		   printf("%d\t",p->adjvex);
		  p=p->next;
				}
		 }//for
}//CreateAdjList


int FirstAdjvex(Graph G,VexType v)
	//返回依附顶点V的第一个点
         //即以V为尾的第一个结点
{ 
	int m;  
	arcnode *p;
 m=LocateVex(G,v);
 p=G.g[m].firstarc;
 if(p)
 return p->adjvex;
 else
	 return max;
}

int NextAdjvex(Graph G,VexType v,int w)//返回依附顶点V的相对于W的下一个顶点
{
 arcnode *p;
 int m;     
 m=LocateVex(G,v);
 p=G.g[m].firstarc;
 while(p)
 {
  if(p->adjvex!=w)
   p=p->next;
  if(p->adjvex==w&&p->next!=NULL)
   return p->next->adjvex;
  else return max;
 }
 return max;
}


void InitQueue(Queue &Q)//初始化队列
{
 Q.rear=(Qptr)malloc(sizeof(QNode));
 Q.front=Q.rear;
 if(!Q.front)
  printf("分配失败！！！");
 Q.front->next=NULL;
}

void EnQueue(Queue &Q,int e)//入队
{

 Qptr p;
 p=(Qptr)malloc(sizeof(QNode));
 if(!p)
  printf("分配失败！！！");

 p->data=e;
 p->next=NULL;
 Q.rear->next=p;
 Q.rear=p;
}


void DeQueue(Queue &Q,int &e)//出队
{
   Qptr p;
  if(Q.front==Q.rear)
 printf("栈空！！");

 p=Q.front->next;
 e=p->data;
 Q.front->next=p->next;
 if(Q.rear==p)
  Q.rear=Q.front;
 free(p);
}



int QueueEmpty(Queue Q)//判断队为空
{
 if(Q.front==Q.rear)
 return 1;
 else return 0;
}


void BFSTra(Graph G)//广度优先遍历
{
 int i,e;
 Queue Q;
 InitQueue(Q);
 for(i=0;i<G.vexnum;i++)
  visited[i]=0;
 
 for(i=0;i<G.vexnum;i++)//对每一个结点
  if(!visited[i])
  {
   visited[i]=1;
   printf("\n%d\t",G.g[i].data);
   EnQueue(Q,i);
   while(!QueueEmpty(Q))
   {
    DeQueue(Q,e);
   for(w=FirstAdjvex(G,G.g[e].data);w>=0,w<max;w=NextAdjvex(G,G.g[e].data,w))
    if(!visited[w])
    {
		visited[w]=1;
		printf("%d\t",G.g[w].data);
     EnQueue(Q,w);
    }
   }
  }
}

void DFS(Graph G,int i)
{
 visited[i]=1;
	printf("%d\t",G.g[i].data);
 for(w=FirstAdjvex(G,G.g[i].data);w>=0,w<max;w=NextAdjvex(G,G.g[i].data,w))
  if(!visited[w])
   DFS(G,w);

}

void DFSTra(Graph G)//深度优先遍历
{
 int i;
 for(i=0;i<G.vexnum;i++)
  visited[i]=0;
 for(i=0;i<G.vexnum;i++)
  if(!visited[i])
   DFS(G,i); 
}



void main()
{int ch;
 Graph G;
 
 printf("请选择你的操作！\n");
 printf("1、创建邻接表：\n");
 printf("2、广度优先遍历：\n");
 printf("3、深度优先遍历：\n");
 printf("0、退出系统\n");
 scanf("%d",&ch);
 while(ch)
 {
	switch(ch)
	{	case 1:CreateAdjList(G);break;
		case 2:printf("广度遍历结果\n");BFSTra(G);break;
		case 3:printf("深度遍历结果\n");DFSTra(G);break;
		default:printf("选择错误！");
	}
	printf("请选择你的操作！\n");
	printf("1、创建邻接表：\n");
	printf("2、广度优先遍历：\n");
	printf("3、深度优先遍历：\n");
	printf("0、退出系统\n");
	scanf("%d",&ch);
}
}