游客 Signup | Login
中文 | En

1361 - 算法7-6：图的遍历——广度优先搜索

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 32 MB
广度优先搜索遍历类似于树的按层次遍历的过程。其过程为：假设从图中的某顶点v出发，在访问了v之后依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点。重复上述过程，直至图中所有顶点都被访问到为止。
其算法可以描述如下： 

<span style="font-family:宋体;">在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。</span>


<span></span>

Input

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。

Output

只有一行，包含n个整数，表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

Examples

Input Format

4
0 0 0 1
0 0 1 1
0 1 0 1
1 1 1 0

Output Format

0 3 1 2

Solution C

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 60
typedef int WeightType;
typedef int Elemtype;
typedef struct EdgeNode
{
    int adjvex;
	int data;
    WeightType weight;
    struct EdgeNode *next;
}EdgeNode;

typedef struct VexNode
{
    EdgeNode *firstarc;
}VexNode, AdjList[MAXVEX];

typedef struct GraphADJ{
    AdjList adjlist;
    int numvex, numedge;
}GraphADJ;

void InitGraph(GraphADJ *G,int n)
{
    int i;
    G->numvex = n;
    for(i=0; i<n; i++)
	{
		G->adjlist[i].firstarc= NULL;
	}
}
void InsertEdge(GraphADJ *G,int s,int t,int w)
{
    EdgeNode *newn = (EdgeNode *)malloc(sizeof(EdgeNode));
    newn->adjvex = t;
    newn->weight = w;
    newn->next=G->adjlist[s].firstarc;
    G->adjlist[s].firstarc=newn;
	
}
int LocateEdge(GraphADJ G,int s,int t)
{
    EdgeNode *p = G.adjlist[s].firstarc;
    while(p!=NULL)
	{
        if(p->adjvex == t)
            return 0;
        p = p->next;
    }
    return 1;
}
void Create(GraphADJ *G,int n)
{
	int i,j,x,k=0,t;
	int a[60][60],visit[60],b[60];
	InitGraph(G,n);
	for(i=0;i<n;i++)
		visit[i]=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
	        scanf("%d",&a[i][j]);
	for(i=0;i<n;i++)
		for(j=n-1;j>=0;j--)
		{
            if(a[i][j]==1)
               InsertEdge(G,i,j,1);
		}
	EdgeNode *p;
	i=0;
    while(k==0)
	{
		j=0,t=0;
		printf("%d ",i);
	   do
	   {
	     p=G->adjlist[i].firstarc;
	     visit[i]=1;
	     while(p!=NULL)
		 {
	       i=p->adjvex;
		   if(visit[i]!=1)
		   {
	          b[j++]=i;
              visit[i]=1;
		      printf("%d ",i);
		   }
	       p=p->next;
		 }
	     i=b[t];
		 b[t]=-1;
		 t++;
	   }while(t<=j);
	for(i=0;i<n;i++)
	{
		if(visit[i]==1)
			k=1;
		else
		{
			k=0;
			break;
		}
	}
	}
}
void main()
{
	int n;
	scanf("%d",&n);
	GraphADJ G;
    Create(&G,n);
	printf("\n");
}

Solution C++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status; /* 函数结果状态代码,如OK等 */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 50 /* 最大顶点个数 */
typedef int VRType;
typedef char InfoType;
typedef int VertexType;
typedef VRType QElemType; /* 队列类型 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct {
	VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
	/* 对带权图，c则为权值类型 */
	InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
	AdjMatrix arcs; /* 邻接矩阵 */
	int vexnum,arcnum; /* 图的当前顶点数和弧数 */
	GraphKind kind; /* 图的种类标志 */
}MGraph;
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
	QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

Status CreateUDG(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G */
	int i,j;
	scanf("%d",&(*G).vexnum);
	for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
		(*G).vexs[i] = i;
	for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
		for(j=0;j<(*G).vexnum;++j)
		{
			scanf("%d",&(*G).arcs[i][j].adj); /* 图 */
			(*G).arcs[i][j].info=NULL; /* 没有相关信息 */
		}
	(*G).kind=AG;
	return OK;
}

int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
	/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
	int i;
	for(i=0;i<G.vexnum;++i)
		if(u == G.vexs[i])
			return i;
	return -1;
}

VertexType* GetVex(MGraph G,int v)
{ /* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */
	if(v>=G.vexnum||v<0)
		exit(ERROR);
	return &G.vexs[v];
}

int FirstAdjVex(MGraph G,VertexType v)
{ /* 初始条件: 图G存在,v是G中某个顶点 */
	/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
	int i,j=0,k;
	k=LocateVex(G,v); /* k为顶点v在图G中的序号 */
	if(G.kind==DN||G.kind==AN) /* 网 */
	j=INFINITY;
	for(i=0;i<G.vexnum;i++)
	if(G.arcs[k][i].adj!=j)
	return i;
	return -1;
}

int NextAdjVex(MGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
	/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
	/*           若w是v的最后一个邻接顶点,则返回-1 */
	int i,j=0,k1,k2;
	k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */
	k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */
	if(G.kind==DN||G.kind==AN) /* 网 */
	j=INFINITY;
	for(i=k2+1;i<G.vexnum;i++)
	if(G.arcs[k1][i].adj!=j)
	return i;
	return -1;
}

Status InitQueue(LinkQueue *Q)
{ /* 构造一个空队列Q */
	(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
	if(!(*Q).front)
	exit(OVERFLOW);
	(*Q).front->next=NULL;
	return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
	if(Q.front==Q.rear)
	return TRUE;
	else
	return FALSE;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
	QueuePtr p;
	if((*Q).front==(*Q).rear)
	return ERROR;
	p=(*Q).front->next;
	*e=p->data;
	(*Q).front->next=p->next;
	if((*Q).rear==p)
	(*Q).rear=(*Q).front;
	free(p);
	return OK;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p) /* 存储分配失败 */
	exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	(*Q).rear->next=p;
	(*Q).rear=p;
	return OK;
}

bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
Status(*VisitFunc)(VertexType); /* 函数变量 */
void BFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.6 */
	/* 操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 */
	/*           Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
	/*           使用辅助队列Q和访问标志数组visited */
	int v,u,w;
	VertexType w1,u1;
	LinkQueue Q;
	for(v=0;v<G.vexnum;v++)
	visited[v]=FALSE; /* 置初值 */
	InitQueue(&Q); /* 置空的辅助队列Q */
	for(v=0;v<G.vexnum;v++)
	if(!visited[v]) /* v尚未访问 */
	{
		visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
		Visit(G.vexs[v]);
		EnQueue(&Q,v); /* v入队列 */
		while(!QueueEmpty(Q)) /* 队列不空 */
		{
			DeQueue(&Q,&u); /* 队头元素出队并置为u */
			u1 = *GetVex(G,u);
			for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,w1 = *GetVex(G,w)))
				if(!visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
				{
					visited[w]=TRUE;
					Visit(G.vexs[w]);
					EnQueue(&Q,w);
				}
		}
	}
	printf("\n");
}

Status visit(VertexType i)
{
	printf("%d ",i);
	return OK;
}

int main() {
	int i,j,k,n;
	MGraph g;
	CreateUDG(&g);
	BFSTraverse(g,visit);
	return 0;
}

Solution Java



import java.util.LinkedList;
import java.util.Scanner;

public class Main {
   private static Scanner s = new Scanner(System.in) ;
   
   public static void main(String[] args) {
	  int n = s.nextInt() ;
	  int a[][] = new int[n][n] ;
	  for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			a[i][j] = s.nextInt() ;
		}
	  }
	  
	  for (int i = 0; i < a.length; i++) {
		 a[i][i] = 1 ;
	  }
	  
	  boolean visited[] = new boolean[a.length] ;
	  
	  LinkedList<Integer> queue = new LinkedList<Integer>() ;
	  
	  queue.add(0) ;
	  System.out.print(0+ " ") ;
	  visited[0] = true ;
	  
	  while(queue.size()!=0){
		  int k = queue.pollFirst() ;
		  
		  for (int i = 0; i < visited.length; i++) {
			if(visited[i]==false&&a[k][i]==1){
				visited[i] = true ;
				queue.add(i) ;
				System.out.print(i+" ") ;
			}
		  }
	  }
	  System.out.println();
   }
   
   
}
请先登陆