adjmultilist.cpp

数据结构无向图的深搜和广搜

#include <iostream>
using namespace std;
#define MAX 30
int IsPassed[MAX]={0};
typedef struct Node//头节点
{
	int data;
	struct AML *first;
}Node,NList[MAX];
typedef struct AML//节点
{
	int mark,iv,jv;
	struct AML *ilink,*jlink,*info;
}AML;
typedef struct AMLGraph{//图
	NList vs;
	int vnum,edgenum;
}AMLGraph;

typedef struct duilie//队列
{
	int front;
	int rear;
	int body[2*MAX];
}duilie;
void EQ(duilie *&Q,int n)
{
	if ((Q->rear+1)%(2*MAX)==Q->front)
	{
		cout<<" 队列满了！\n";
		return ;
	}
	Q->body[Q->rear]=n;
	Q->rear=(Q->rear+1)%(2*MAX);
}
void DQ(duilie* &Q,int &n)//队列
{
	n=Q->body[Q->front];
	Q->front=(Q->front+1)%(2*MAX);
}

void MapToAML(int A[MAX][MAX],int n,int m,AMLGraph* &G)//邻接矩阵到广义表
{
	int i,j;AML *p,*t;
	G=(AMLGraph *)malloc(sizeof(AMLGraph));
	for(i=0;i<n;i++)
		G->vs[i].first=NULL;

	for (i=0;i<n;i++)
	{
		for (j=n-1;j>=0;j--) 
		{
			if(A[i][j]!=0)
			{
				if(i<=j)//右上半部分，要建新节点；
				{
					p=(AML *)malloc(sizeof(AML));
					p->iv=i;
					p->jv=j;

					p->ilink=G->vs[i].first;
					G->vs[i].first=p;

				}
				else//坐下半部分，找之前建好的节点；
				{			
						t=G->vs[j].first;
						while(t!=NULL) 
						{
							if (t->jv==i)
							{
								t->jlink=G->vs[i].first;//A[i][j]肯定在A[j][i]中
								G->vs[i].first=t;
								break;
							}
							if(t->iv==j)t=t->ilink;//在本层对应ilink，其他jlink
								else t=t->jlink;
						}
				}
			}
		}
	}
	G->vnum=n;G->edgenum=m;
	
}
void display(AMLGraph *G,int n)//给自己看得
{
	AML *t;int i=0;
	for(i=0;i<n;i++)
	{
		t=G->vs[i].first;
		while(t)
		{
			cout<<t->iv<<" "<<t->jv<<endl;
			if (t->iv==i) t=t->ilink;
				else t=t->jlink;
		}

	}
}
void DFS(AMLGraph* &G,int n)//深搜
{
	AML *p;IsPassed[n]=1;
	p=G->vs[n].first;
	
	while(p!=NULL)
	{

			if (IsPassed[p->iv]==0)
			{ 
				printf("%2d %2d -> %2d\n",1+p->iv,n+1,1+p->iv);
				//cout<<1+p->iv<<" "<<n+1<<"->"<<1+p->iv<<endl;
				DFS(G,p->iv);//搜出发点
			}
			else 
				if (IsPassed[p->jv]==0)
				{
					printf("%2d %2d -> %2d\n",1+p->jv,n+1,1+p->jv);
					//cout<<1+p->jv<<" "<<n+1<<"->"<<1+p->jv<<endl;
					DFS(G,p->jv);//搜到达点
				}
		if (p->iv==n) p=p->ilink;//下一结点，方法如上
				else p=p->jlink;
	}

}
void BFS(AMLGraph* G,int star)//广搜
{
	int n,u;
	AML *p;
	p=G->vs[star].first;
	for(n=0;n<G->vnum;n++)IsPassed[n]=0;
	duilie *Q=(duilie *)malloc(sizeof(duilie));
	Q->front=Q->rear=0;//队列初始化
	//for(n=0;n<G->vnum;n++)
	//{
		//star=(n+star)%(G->vnum);
		if(!IsPassed[star])
		{
			IsPassed[star]=1;
			printf(" %d \n",star+1);
			EQ(Q,star);
		}
		while (Q->front!=Q->rear) 
		{
			DQ(Q,u);
			p=G->vs[u].first;//第u+1行
			while (p)
			{
				if (IsPassed[p->iv]==0)
				{ 	
					printf("%2d %2d -> %2d\n",p->iv+1,u+1,p->iv+1);
					//cout<<1+p->iv<<" "<<1+u<<"->"<<1+p->iv<<endl;
					EQ(Q,p->iv);IsPassed[p->iv]=1;
				}
				else 
					if (IsPassed[p->jv]==0)
					{
						printf("%2d %2d -> %2d\n",p->jv+1,u+1,p->jv+1);
						//cout<<1+p->jv<<" "<<1+u<<"->"<<1+p->jv<<endl;
						EQ(Q,p->jv);IsPassed[p->jv]=1;
					}
				if (p->iv==u) p=p->ilink;//下一节点
				else p=p->jlink;
			}
		}
		
	//}
	
}
int main()
{
	int n,m,i,j,store[30][30];
	AMLGraph *G;
	cout<<"请输入图的节点数n边数m和邻接矩阵："<<endl;
	cin>>n>>m;
	for (i=0;i<n;i++) 
	{
		for (j=0;j<n;j++) 
		{
			cin>>store[i][j];
		}
	}
	MapToAML(store,n,m,G);
	//display(G,n);
	cout<<"请输入深搜的开始点编号："<<endl;
	cin>>i;
	cout<<"遍历点 边集\n"<<i<<endl;
	DFS(G,i-1);
	cout<<"请输入广搜的开始点编号："<<endl;
	cin>>j;
	cout<<"遍历点 边集"<<endl;
	BFS(G,j-1);
	return 1;
}