本文共 2341 字，大约阅读时间需要 7 分钟。

【描述】：  图的bfs

【输入】：

【输出】：

0 1 2 3 4 5 6 7

/* *图的广度优先遍历 *1.链式队列（链表的头节点中存数据、节点的尾插法、头节点的删除） *2.bfs 8 1 2 -1 0 3 4 -1 0 5 6 -1 1 7 -1 1 7 -1 2 7 -1 2 7 -1 3 4 5 6 -1  */#include
   
    #include
    
     using namespace std;/* 宏定义 */#define MAX_NUM 50#define ElementType int/* 定义动态链式队列节点 */typedef struct QueueNode{    ElementType data;    struct QueueNode *next;}QueueNode,*QueuePointer;/* 邻接表表节点 */typedef struct TableNode{    ElementType vertex;    struct TableNode *next;}TableNode,*TablePointer;/* 头节点数组 */TablePointer graph[MAX_NUM];/* 定义visited数组 */bool visited[MAX_NUM];/* 顶点数 */int vertices;/* * 动态链式队列 * 1.addq -> 入队 * 2.deleteq -> 出队 *//*在链式队列的队尾插入元素*/void addq(QueuePointer &front, QueuePointer &rear, ElementType item){    QueuePointer temp = new QueueNode;    temp->data = item;    temp->next = NULL;    //插入    if(front){        rear->next = temp;    }else{        front = temp;    }    rear = temp;}/*从链式队列的头部出队*/ElementType deleteq(QueuePointer &front){    QueuePointer temp = front;    ElementType item;    //出队    item = temp->data;    front = temp->next;    delete temp;    return item;}/* * 邻接表存储的图 * 1.创建图 * 2.bfs *//*创建*/void CreateGraph(){      ElementType ch;      TablePointer pnew,qnode;      pnew = qnode = NULL;        for(int i = 0; i < vertices; i++){          cin>>ch;          if(ch == -1) continue; /*当ch 为-1是结束该vertex的创建*/          //链表的头节点          pnew = new TableNode;          pnew->vertex = ch;          pnew->next = NULL;          //将头节点存入 头节点数组          graph[i] = pnew;          //尾插法创建链表          cin>>ch;          while(ch != -1){              //申请内存、处理数据域、处理指针域              qnode = new TableNode;              qnode->vertex = ch;              qnode->next =NULL;              //插入              pnew->next = qnode;              //更新尾指针              pnew = qnode;              cin>>ch;          }      }  }/*bfs*/void bfs(ElementType v){    TablePointer w;    QueuePointer front, rear;    front = rear = NULL;    //将第一个节点输入、标记、进队    cout<
     
      <
      
       next){            if(!visited[w->vertex]){                cout<
       
        vertex<<" ";		visited[w->vertex] = true;                addq(front, rear, w->vertex);            }	}    }	cout<
        
         >vertices; CreateGraph(); cout<<"广度优先遍历"<
        
       
      
     
    
   

转载地址：https://lipenglin.blog.csdn.net/article/details/49963697 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！