7:1图的遍历

构建队列

typedef struct GraphNodeQueue{
    
    int* nodes;
    int front;
    int rear;
    
}GraphNodeQueue, *QueuePtr;

初始化循环队列

QueuePtr initQueue(){
    
    QueuePtr resultQueuePtr = (QueuePtr) malloc (sizeof(struct GraphNodeQueue));
    resultQueuePtr->nodes = (int*) malloc (QUEUE_SIZE * sizeof(int));
    resultQueuePtr->front = 0;
    resultQueuePtr->rear = 1;
    return resultQueuePtr;
    
}

判断队列是否为空

bool isQueueEmpty(QueuePtr paraQueuePtr){
    
    if((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear){
        //为空
        return true;
    }
    //非空
    return false;
    
}

向队列添加结点

void enqueue(QueuePtr paraQueuePtr, int paraNode){
    
    printf("front = %d, rear = %d.rn", paraQueuePtr->front, paraQueuePtr->rear);
    //判断队列是否已满
    if((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE){
        printf("Error, trying to enqueue %d. queue full.rn", paraNode);
        return;
    }
    //在队尾入队
    paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode;
    paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
    printf("enqueue %d ends.rn", paraNode);
    
}

队头出队并返回当前值

int dequeue(QueuePtr paraQueuePtr){
    
    //判断队列是否为空
    if(isQueueEmpty(paraQueuePtr)){
        printf("Error, empty queuern");
        return NULL;
    }
    
    paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;
    
    //打印队尾元素
    printf("dequeue %d ends.rn", paraQueuePtr->nodes[paraQueuePtr->front]);
    return paraQueuePtr->nodes[paraQueuePtr->front];
    
}

构建图

typedef struct Graph{
    
    int** connections;
    int numNodes;
    
} *GraphPtr;

图的初始化

GraphPtr initGraph(int paraSize, int** paraData){
    
    int i, j;
    GraphPtr resultPtr = (GraphPtr) malloc (sizeof(Graph));
    resultPtr -> numNodes = paraSize;
    resultPtr -> connections = (int**)malloc(paraSize * sizeof(int*));
    
    for(i = 0; i < paraSize; i++){
        resultPtr -> connections[i] = (int*)malloc(paraSize * sizeof(int));
        for (j = 0; j < paraSize; j++){
            resultPtr -> connections[i][j] = paraData[i][j];
        }
    }
    
    
    
    return resultPtr;
}

初始化

void initTranverse(GraphPtr paraGraphPtr){

    int i;
    //初始化数据
    visitedPtr = (int*) malloc(paraGraphPtr -> numNodes * sizeof(int));
    
    for (i = 0; i < paraGraphPtr -> numNodes; i++){
        visitedPtr[i] = 0;
    }
}

深度优先遍历

void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode){
    
    int i;
    
    visitedPtr[paraNode] = 1;
    printf("%dt", paraNode);
    
    //寻找最近相邻元素
    for(i = 0; i < paraGraphPtr -> numNodes; i++){
        if(!visitedPtr[i]){
            if(paraGraphPtr -> connections[paraNode][i]){
                depthFirstTranverse(paraGraphPtr, i);
            }
        }
    }
}

广度优先遍历

void widthFirstTranverse(GraphPtr paraGraphPtr, int paraStart){
    
    //用队列管理
    int i, j, tempNode;
    i = 0;
    QueuePtr tempQueuePtr = initQueue();
    printf("%dt", paraStart);
    visitedPtr[paraStart] = 1;
    enqueue(tempQueuePtr, paraStart);
    
    while(!isQueueEmpty(tempQueuePtr)){
        tempNode = dequeue(tempQueuePtr);
        visitedPtr[tempNode] = 1;
        
        i++;

        for(j = 0; j < paraGraphPtr->numNodes; j++){
            if(visitedPtr[j])
                continue;

            if(paraGraphPtr->connections[tempNode][j] == 0)
                continue;
            
            //打印最近的几个元素
            printf("%dt", j);
            visitedPtr[j] = 1;
            enqueue(tempQueuePtr, j);
        }
    }
}

//
//  main.c
//  图的遍历
//
//  Created on 2022/5/30.
//


#include 
#include 

#define QUEUE_SIZE 10

int* visitedPtr;

//构建队列
typedef struct GraphNodeQueue{
    
    int* nodes;
    int front;
    int rear;
    
}GraphNodeQueue, *QueuePtr;

//初始化循环队列
QueuePtr initQueue(){
    
    QueuePtr resultQueuePtr = (QueuePtr) malloc (sizeof(struct GraphNodeQueue));
    resultQueuePtr->nodes = (int*) malloc (QUEUE_SIZE * sizeof(int));
    resultQueuePtr->front = 0;
    resultQueuePtr->rear = 1;
    return resultQueuePtr;
    
}

//判断队列是否为空
bool isQueueEmpty(QueuePtr paraQueuePtr){
    
    if((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear){
        //为空
        return true;
    }
    //非空
    return false;
    
}

//向队列添加结点
void enqueue(QueuePtr paraQueuePtr, int paraNode){
    
    printf("front = %d, rear = %d.rn", paraQueuePtr->front, paraQueuePtr->rear);
    //判断队列是否已满
    if((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE){
        printf("Error, trying to enqueue %d. queue full.rn", paraNode);
        return;
    }
    //在队尾入队
    paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode;
    paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
    printf("enqueue %d ends.rn", paraNode);
    
}

//队头出队并返回当前值
int dequeue(QueuePtr paraQueuePtr){
    
    //判断队列是否为空
    if(isQueueEmpty(paraQueuePtr)){
        printf("Error, empty queuern");
        return NULL;
    }
    
    paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;
    
    //打印队尾元素
    printf("dequeue %d ends.rn", paraQueuePtr->nodes[paraQueuePtr->front]);
    return paraQueuePtr->nodes[paraQueuePtr->front];
    
}

//构建图
typedef struct Graph{
    
    int** connections;
    int numNodes;
    
} *GraphPtr;

//图的初始化
GraphPtr initGraph(int paraSize, int** paraData){
    
    int i, j;
    GraphPtr resultPtr = (GraphPtr) malloc (sizeof(Graph));
    resultPtr -> numNodes = paraSize;
    resultPtr -> connections = (int**)malloc(paraSize * sizeof(int*));
    
    for(i = 0; i < paraSize; i++){
        resultPtr -> connections[i] = (int*)malloc(paraSize * sizeof(int));
        for (j = 0; j < paraSize; j++){
            resultPtr -> connections[i][j] = paraData[i][j];
        }
    }
    
    
    
    return resultPtr;
}

//初始化
void initTranverse(GraphPtr paraGraphPtr){
    
    int i;
    //初始化数据
    visitedPtr = (int*) malloc(paraGraphPtr -> numNodes * sizeof(int));
    
    for (i = 0; i < paraGraphPtr -> numNodes; i++){
        visitedPtr[i] = 0;
    }
}

//深度优先遍历
void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode){
    
    int i;
    
    visitedPtr[paraNode] = 1;
    printf("%dt", paraNode);
    
    //寻找最近相邻元素
    for(i = 0; i < paraGraphPtr -> numNodes; i++){
        if(!visitedPtr[i]){
            if(paraGraphPtr -> connections[paraNode][i]){
                depthFirstTranverse(paraGraphPtr, i);
            }
        }
    }
}
    
//广度优先遍历
void widthFirstTranverse(GraphPtr paraGraphPtr, int paraStart){
    
    //用队列管理
    int i, j, tempNode;
    i = 0;
    QueuePtr tempQueuePtr = initQueue();
    printf("%dt", paraStart);
    visitedPtr[paraStart] = 1;
    enqueue(tempQueuePtr, paraStart);
    
    while(!isQueueEmpty(tempQueuePtr)){
        tempNode = dequeue(tempQueuePtr);
        visitedPtr[tempNode] = 1;
        
        i++;

        for(j = 0; j < paraGraphPtr->numNodes; j++){
            if(visitedPtr[j])
                continue;

            if(paraGraphPtr->connections[tempNode][j] == 0)
                continue;
            
            //打印最近的几个元素
            printf("%dt", j);
            visitedPtr[j] = 1;
            enqueue(tempQueuePtr, j);
        }
    }
}

//测试
void testGraphTranverse(){
    
    int i, j;
    int myGraph[5][5] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1},
        {0, 1, 0, 1, 1},
        {1, 0, 1, 0, 0},
        {0, 1, 1, 0, 0}};
    int** tempPtr;
    printf("Preparing datarn");
        
    tempPtr = (int**) malloc (5 * sizeof(int*));
    for (i = 0; i < 5; i++){
        tempPtr[i] = (int*) malloc (5 * sizeof(int));
    }
     
    for (i = 0; i < 5; i++){
        for (j = 0; j < 5; j++){
            printf("i = %d, j = %d, ", i, j);
            printf("%drn", tempPtr[i][j]);
            tempPtr[i][j] = myGraph[i][j];
            printf("i = %d, j = %d, %drn", i, j, tempPtr[i][j]);
        }
    }
 
    printf("Data readyrn");
    
    GraphPtr tempGraphPtr = initGraph(5, tempPtr);
    printf("num nodes = %d rn", tempGraphPtr -> numNodes);
    printf("Graph initializedrn");

    printf("Depth first visit:rn");
    initTranverse(tempGraphPtr);
    depthFirstTranverse(tempGraphPtr, 4);

    printf("rnWidth first visit:rn");
    initTranverse(tempGraphPtr);
    widthFirstTranverse(tempGraphPtr, 4);
    
}

int main(){
    
    testGraphTranverse();
    return 0;
    
}

深度优先遍历

主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

广度优先遍历

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。