dfs and bfs.cpp

ck_conty为判断图的连通性的matlab mex文件

/*将main函数中的BFSTravers改为DFSTravers即可改为深度优先搜索*/
#define MAX_SIZE 5
#include <stdio.h>
#include <malloc.h>
#include <process.h>
bool visited[MAX_SIZE];
typedef struct ArcNode
{//表结点结构类型
	int adjvex;                          //该弧(边)的终点位置
   	struct ArcNode *nextarc;    //指向下一条弧的指针
   	double weight;   	        //该弧的相关信息
}ArcNode,*ArcPtr;
typedef struct Vnode 
{//头结点的类型
	struct ArcNode *firstarc;           //指向第一条弧
};
typedef struct ALGraph
{//邻接表
	struct Vnode vertices[MAX_SIZE];             	
	int vexnum,arcnum;		//图中顶点数n和边数e
};
typedef struct QNode
{
	bool data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct 
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

void main()
{
	void MatToList(double [][MAX_SIZE] ,ALGraph* );
	void DFSTraverse(ALGraph ,int );
	void BFSTraverse(ALGraph );

	double arcs[MAX_SIZE][MAX_SIZE]={0,1,0,0,1,1,0,1,1,0,0,1,0,1,1,0,1,1,0,0,1,0,1,0,0};
	ALGraph *G;
	G=(ALGraph *)malloc(sizeof(ALGraph));
	MatToList(arcs,G);
	G->vexnum=MAX_SIZE;
	G->arcnum=5;
	printf("+++=%d   %d   ",G->vexnum,G->arcnum);
	BFSTraverse(*G);
}

void MatToList(double g[][MAX_SIZE],ALGraph *G )
/*将邻接矩阵g转换成邻接表G;*/
{    
	int i,j;
	int n=MAX_SIZE;
	ArcNode *p; 	/*n为顶点数*/
	for (i=0;i<n;i++)  /*给所有头结点的指针域置初值*/
		G->vertices[i].firstarc=NULL;
	for (i=0;i<n;i++)	/*检查邻接矩阵中每个元素*/
	{
		for (j=n-1;j>=0;j--)
		{
			if (g[i][j]!=0) 
			{ 
				p=(ArcNode *)malloc(sizeof(ArcNode)); /*创建结点*p*/
				p->adjvex=j;
				p->weight=g[i][j];
				p->nextarc=G->vertices[i].firstarc;/*将*p链到链表上*/
				G->vertices[i].firstarc=p;
			}
		}
	}
}
void DFSTraverse(ALGraph G ,int k)
{
	int v;
	void DFS(ALGraph , int );
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)  //形成深度优先生成森林
		if (!visited[k])
		{
			DFS(G,k);
			k++;
			k/=MAX_SIZE;
		}
}

void DFS(ALGraph G ,int v )
{
	struct ArcNode *p;
	visited[v]=1;
	printf("%d  ",v);
	p=G.vertices[v].firstarc;
	while(p!=NULL)
	{
		if(visited[p->adjvex]==0)
			DFS(G,p->adjvex);
		p=p->nextarc;
	}
}

void InitQueue(LinkQueue *Q)
{
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	if (!Q->front)
	{
		exit(1);
	}
	Q->front->next=NULL;
}

void EnQueue(LinkQueue *Q,int e)
{
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)
		exit(1);
	p->data=e;
	p->next=NULL;
	Q->rear->next=p;
	Q->rear=p;
}

bool QueueEmpty(LinkQueue Q)
{
	if (Q.front==Q.rear)
	{
		return 1;
	}
	else return 0;
}

void DeQueue(LinkQueue* Q,int* e)
{
	if (Q->front==Q->rear)
	{
		exit(1);
	}
	QueuePtr p;
	p=Q->front->next;
	*e=p->data;
	Q->front->next=p->next;
	if (Q->rear==p)
	{
		Q->rear=Q->front;
	}
	free(p);
}
void BFSTraverse(ALGraph G)
{
	int v,u;
	LinkQueue Q;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	InitQueue(&Q);
	for(v=0;v<G.vexnum;v++) //形成广度优先生成森林
	{
		if(!visited[v])
		{
			visited[v]=1;
			printf("%d   ",v);
			EnQueue(&Q,v);
			while (!QueueEmpty(Q))
			{
				DeQueue(&Q,&u);
				ArcPtr p=G.vertices[u].firstarc;
				while (p)
				{
					if (!visited[p->adjvex])
					{
						visited[p->adjvex]=1;
						printf("%d   ",p->adjvex);
						EnQueue(&Q,p->adjvex);
					}//if
					p=p->nextarc;
				}//while(p)
			}//while(!Queue)
		}//if(!visited)
	}//for
}