[数据结构与算法]图的深度优先（递归、栈实现）&广度优先（队列）

?数据结构：

#define  MaxVertexNum 100
typedef struct ArcNode{
    int adjvex;
    ArcNode *next;
}ArcNode;

typedef struct VNode{
    int data;
    ArcNode *first;
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;


int visited[MaxVertexNum] = {false};

void visit(VNode node){
    printf("%d",node.data);
}

int FirstNeighbor(ALGraph graph,int i){
    VNode node = graph.vertices[i];
    return node.first!= nullptr ? node.first->adjvex:-1;
}
int NextNeighbor(ALGraph graph,int i,int j){
    ArcNode *node = graph.vertices[i].first;
    while(node!= nullptr){
        if(node->adjvex == j){
            return node->next != nullptr ? node->next->adjvex : -1;
        }
        node = node->next;
    }
}

 VNode node1;
        node1.data= 1;
        VNode node2;
        node2.data= 2;
        VNode node3;
        node3.data= 3;
        VNode node4;
        node4.data= 4;
        VNode node5;
        node5.data= 5;
        VNode node6;
        node6.data= 6;

        node3.first= nullptr;
        ALGraph graph;


       ArcNode anode12;
       anode12.adjvex=2;
       node1.first = &anode12;

       ArcNode anode13;
       anode13.adjvex = 3;
       anode12.next = &anode13;

       ArcNode anode14;
       anode14.adjvex=4;
       anode13.next = &anode14;

       anode14.next = nullptr;

       ArcNode anode23;
       anode23.adjvex = 3;
       node2.first = &anode23;

       ArcNode anode26;
       anode26.adjvex=6;
       anode26.next= nullptr;
       node6.first = nullptr;
    
       ArcNode anode21;
       anode21.next = &anode26;
       anode21.adjvex=1;
       anode23.next = &anode21;

       ArcNode anode34;
       anode34.adjvex=4;
       node3.first = &anode34;

       ArcNode anode35;
       anode35.adjvex=5;
       anode34.next = &anode35;
       anode35.next = nullptr;

       node4.first= nullptr;
       node5.first= nullptr;


    graph.vertices[1] = node1;
    graph.vertices[2] = node2;
    graph.vertices[3] = node3;
    graph.vertices[4] = node4;
    graph.vertices[5] = node5;
    graph.vertices[6] = node6;

邻接表：

?图：

?

一、深度优先（DFS）

typedef struct{
    AdjList list;
    int p;
}Stack;
void push(Stack &stack,VNode node){
    stack.list[stack.p++] = node;
}
VNode pop(Stack &stack){
    return stack.list[--stack.p];
}
void initStack(Stack &stack){
    stack.p=0;
}

（1）递归

void DFS(ALGraph graph,int i){        //i开始结点序号
    printf("%d",i);
    visited[i] = true;
    for(int w = FirstNeighbor(graph,i);w!=-1;w = NextNeighbor(graph,i,w)){
        if(visited[w]==false){
            DFS(graph,w);             //递归
        }
    }
}

（2）借助栈

void DFS_stack(ALGraph graph,int i){
    Stack stack;
    initStack(stack);                    //初始化栈
    VNode node = graph.vertices[i];
    visit(graph.vertices[i]);                
    visited[i] = true;                   //结点已访问标记
    push(stack,graph.vertices[i]);       //将结点入栈
    while(stack.p!=0){                   //栈不为空
        VNode vnode = pop(stack);         //出栈一个元素
        for(int w = FirstNeighbor(graph,vnode.data);w!=-1;w = NextNeighbor(graph,vnode.data,w)){                    //遍历元素所有相邻结点
            if(visited[w]==false){
                visited[w]=true;
                push(stack,graph.vertices[w]);         //相邻结点依次入栈   
                visit(graph.vertices[w]);
            }
        }
    }

}

二、广度优先（BFS）

typedef struct{
    AdjList list;
    int head;
    int rear;
}Queue;
void initQueue(Queue &queue){
    queue.rear = 0;
    queue.head = 0;
}
void enQueue(Queue &queue,VNode node){
    queue.list[queue.rear++] = node;
}
VNode deQueue(Queue &queue){
    if(queue.head!=queue.rear){
        return queue.list[queue.head++];
    }
}

void BFS(ALGraph graph,int i){
    Queue queue;
    initQueue(queue);

    if(visited[i]==false){
        visited[i]=true;
        enQueue(queue, graph.vertices[i]);
        visit(graph.vertices[i]);
    }
    while(queue.head!=queue.rear) {
        i = deQueue(queue).data;                       //出队列
        for (int w = FirstNeighbor(graph, i); w != -1; w = NextNeighbor(graph, i, w)) {
            if(visited[w]==false) {
                enQueue(queue, graph.vertices[w]);       //进队列
                visited[w] = true;
                visit(graph.vertices[w]);
            }

        }
    }
}

结点序列：

//    DFS(graph,1);           //深度序列结果：123456
//    DFS_stack(graph,1);     //深度序列结果：123456
    BFS(graph,1);        //广度序列结果：123465