dfs_bfs.c

C++的电子教程

//程序实例8_3
//图的邻接表表示
#include<stdio.h>
#include<stdlib.h>
#define Max 50

typedef struct e_node               //定义边结点的数据类型
{	int adjvex;
	int weight;
	struct e_node *next;
}E_node;

typedef struct v_node              //定义顶点结点的数据类型
{	int vertex;
	E_node *link;
}V_node;

V_node head[Max];                  //定义顶点结点的数组
int visit[Max];


//邻接表的建立
void adjl(V_node head[],int v[][2],int w[],int n,int e,int t)
{
	int i,k,m=0;
	E_node *p;

	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;	//////////////////////////////////
		head[i].vertex=i;   //顶点信息设为顶点编号
	}

	for(k=1;k<=e;k++)
	{
		p=(E_node *)malloc(sizeof(E_node));  //新结点存放w
		p->adjvex=v[m][1];    //终点为w的边结点链到第v个链表
		p->next=head[v[m][0]].link;
		head[v[m][0]].link=p;
		if(t==0)        //无向图
		{	
			p=(E_node *)malloc(sizeof(E_node));  //新结点存放v
			p->adjvex=v[m][0];  //终点为v的边结点链到第w个链表
			p->next=head[v[m][1]].link;
			head[v[m][1]].link=p;
		}
		if(t==2)        //带权有向图
			p->weight=w[m];   //赋权值

		m++;
	}
}

//输出邻接表
void Print(V_node head[],int n,int t)
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)
	{	printf("\nhead[%d]",i);
		if(head[i].link)
		{	p=head[i].link;
			while(p)
			{	printf("->[%d]",p->adjvex);
			    if (t==2)      //带权有向图
					printf("[%d]",p->weight);  //输出权值
				p=p->next;
			}
		}
		printf("\n");
	}
	printf("\n");
}

//DFS遍历(递归)
void dfs(int v,V_node head[])    //v为开始结点
{	E_node *p;
	visit[v]=1;
	printf("[v%d]",v);
	p=head[v].link;

	if(!p->next)
		printf("割点[v%d]",p->adjvex);

	while(p!=NULL)
	{	if(visit[p->adjvex]==0)
			dfs(p->adjvex,head);
		p=p->next;
	}
	//printf("\n");
}

//BFS遍历
void bfs(int v,V_node head[])  //使用队列的广度优先搜索
{	E_node *p;
	int queue[Max];
	int front=0,rear=0,w;
	printf("[v%d]",v);visit[v]=1;   //访问初始点，置v已访问
	queue[rear++]=v;    //并让其进队

	while(front!=rear)
	{	w=queue[front++];  //队首出队，并送w
		p=head[w].link;   //找与顶点w邻接的顶点
		while(p!=NULL)
		{	if(visit[p->adjvex]==0)
			{	printf("[v%d]",p->adjvex);
		        visit[p->adjvex]=1;
				queue[rear++]=p->adjvex;
			}
			p=p->next;  //找下一个邻接顶点
		}
	}

	//printf("\n");
}

void Init()
{
	int i;
	for(i=1;i<=Max;i++)
    	visit[i]=0;
}


//主函数
void main()
{
	int n,e,t;//无向图、有向图、带权有向图的t分别为0、1、2
	//int d1[][2]={{1,2},{1,3},{1,5},{2,4},{2,6},{3,6},{5,6}};
	int d1[][2]={{1,2},{1,3},{2,4},{3,6},{5,6}};
	int d2[][2]={{1,2},{1,3},{2,4},{3,2},{4,6},{5,1},{6,3},{6,4},{6,5}};
	int d3[][2]={{1,2},{2,3},{2,5},{4,1},{4,3},{5,4}};
	int w[Max],w3[]={10,8,15,5,2,23};


	int d4[][2]={{1,4},{1,2},{1,3},{3,5},{3,4},{5,4},{5,2}};

	printf("\n图8.1.1无向图G1的邻接表:\n");
	n=6; e=5; t=0;
	adjl(head, d1, w, n, e, t);

	//n=5; e=7; t=1;
	//adjl(head, d2, w, n, e, t);

	Print(head,n,t);

	Init();
	printf("\n深度优先搜索顺序: ");
	dfs(1,head);
	printf("\n");
				
	Init();
	printf("\n广度优先搜索顺序: ");
	bfs(1,head);
	printf("\n");
/*

	printf("\n图8.1.2有向图G2的邻接表:\n");
	n=6; e=9; t=1;
	adjl(head,d2, w, n, e, t);
	Print(head,n,t);

	printf("\n图8.1.8带权有向图G3的邻接表:\n");
	n=5; e=6; t=2;
	adjl(head,d3, w3, n, e, t);
	Print(head,n,t);*/
}