图的广度优先遍历和深度优先遍历

图的邻接矩阵存储结构

#define MaxVertexNum 100
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权边上权值的数据类型
typedef struct{
    VertexType vex[MaxVertexNum];//顶点表
    EdgeType edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
    int vexnum,arcnum;//图当前的顶点数，弧数
}MGraph;

图的邻接表存储结构

#define MaxVertexNum 100

//边表结点
typedef struct ArcNode{
    int adjvex;//该弧顶点的位置
    struct ArcNode *next;//指向下一个结点
}ArcNode;

//顶点表结点
typedef struct VexNode{
    VextexType data;//顶点信息
    ArcNode *first;//指向第一条依附该顶点的弧的指针
}VexNode，AdjList[MaxVertexNum];

typedef struct{
    AdjList adjlist;//邻接表
    int vexnum,arcnum;
}AlGraph;

广度优先遍历(以邻接表为例)
借助队列来实现

#define Maxsize 100
bool visit[Maxsize];
void BFSTraver(AlGraph G){
    
    //初始化数组
    for(int i=0;i<G.vexnum;i++){
        visit[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visit[i])
            BFS(G,i);
    }
}

void BFS(AlGraph G,int v){
    ArcNode *p;
    InitQueue(Q);//初始化队列，这里写的是伪代码
    visit(v);//访问结点，可以改成打印结点的操作
    visit[v] = true;
    Enqueue(Q,v);
    while(!QueueEmpty(Q)){
        Dequeue(Q,v);
        p = G->adjlist[v].first;
        while(p){
            if(!visit[p-adjvex]){
                visit[p->adjvex] = true;
                Enqueue(Q,p->adjvex);
            }
            p = p->next;
        }
    }
}

深度优先遍历(以邻接表为例)

递归遍历

#define Maxsize 100
bool visit[Maxsize];
void DFSTraver(AlGraph G){
    
    //初始化数组
    for(int i=0;i<G.vexnum;i++){
        visit[i] = false;
    }
    for(int i=0;i<G.vexnum;i++){
        if(!visit[i])
            DFS(G,i);
    }
}

void BFS(AlGraph G,int v){
    ArcNode *p;
    visit(v);
    visit[v] = true;
    p = G->adjlist[v].first;
    while(p){
        if(!visit[p->adjvex]){
            DFS(G,p->adjvex);//递归遍历
        }
        p = p->next;
    }
}