guangdu.cpp

2、广度优先搜索遍历图的算法：首先访问指定的起始顶点V0

        #include<stdio.h>
        #include<stdlib.h>
        #define vertexnum 9  //定义顶点数为9
        #define QueueMax 10
        typedef struct node    //定义表结点结构
        {
			int adjvex;
            struct node *next;
		}nodetype;
        typedef struct node *Graph;        //定义图形结构
        struct node Head[vertexnum];
        int Queue[QueueMax];
        int front=-1;
        int rear=-1;
        int visited[vertexnum];            //查找记录
        void CreatGraph(int *node,int adjvex2)     //建立邻接顶点至邻接列表内
		{
			Graph Pointer;         //节点声明
			Graph New;             //新节点声明
            int first;                      // 边线的起点
            int end;                        // 边线的终点
            int value;                   // 边线的值
            int i;
            for (i=0;i<adjvex2;i++ )    // 读取边线的回路
			{
	  			first=node[i*2];           // 边线的起点
      			end=node[i*2+1];           // 边线的终点
	  			value=node[i*2+2];        // 边线的值      
      			New=(Graph) malloc(sizeof(struct node));// 建立新顶点记忆体
      			New->adjvex=end;       // 建立顶点内容
      			New->next=NULL;   // 设定指标初值
      			Pointer=&(Head[first]);        // 顶点位置
      			while (Pointer->next!=NULL ) // 遍历至链表尾
					Pointer=Pointer->next;         // 下一个顶点
        		Pointer->next=New;        // 插入结尾
			}
		}
		int EEqueue(int a)
		{
			if(rear>=QueueMax)
				return -1;
            else
			{
	  			rear++;
	  			Queue[rear]=a;
	  			return 1;   
			}
		}
        int DDqueue()
		{
			if(front==rear)
				return -1;
            else
			{
				front++;	  
	  			return Queue[front];
			}
		}
		void bfs(int b)    //广度优先搜索遍历递归算法
		{   
			Graph Pointer;         //节点声明
	 		EEqueue(b);     //存入列表中
     		visited[b]=1;
     		printf("%d－>",b);
     		while(front!=rear)
			{
				b=DDqueue();
				Pointer=Head[b].next;
				while(Pointer!=NULL)
				{
					if(visited[Pointer->adjvex]==0)
					{
		      			EEqueue(Pointer->adjvex);
              			visited[Pointer->adjvex]=1;
			  			printf("%d－>",Pointer->adjvex);
					}			   
		            Pointer=Pointer->next;
				}  
			}
		}
        void main()
		{
			Graph Pointer;
   			int i;
   			int node[20][2]={{1,2},{1,3},{1,5},{1,6},{2,1},{2,4},{2,3},{3,1},{3,4},{3,2},{4,2},{4,5},{4,3},{4,6},{5,4},{5,6},{5,1},{6,5},{6,1},{6,4} };
   			for(i=0;i<vertexnum;i++)
			{
     			Head[i].adjvex=i;
	 			Head[i].next=NULL;
			}
   			for(i=0;i<vertexnum;i++)
	   			visited[i]=0;   
   			CreatGraph(*node,20);
   			printf("构造邻接表如图:\n");  
   			for(i=1;i<vertexnum;i++)
			{
				printf("adjvex %d:",i);
	     		printf("%d－－>",Head[i].adjvex);		 
	     		for(Pointer=Head[i].next;Pointer!=NULL;Pointer=Pointer->next)
				{
             		printf("%d",Pointer->adjvex);			
				}
			    printf("\n");
			}
   			printf("\n");
   			printf("广度优先搜索遍历:\n");
   			bfs(5);
			printf("\n");
		}