图的遍历

结构

//顶点结构
typedef struct Vnode
{
    Vertex data; //顶点信息
    ArcNode *firstarc; //指向第一条边
} VNode;

//边头结点结构
typedef struct ANode
{
    int adjvex; //该边的终点编号
    struct ANode *nextarc; //指向下一条边的指针
    InfoType info; //该边的权值等信息
} ArcNode;

//图结构
typedef struct
{
    VNode adjlist[MAXV]; //邻接表
    int n, e; //图中顶点数n和边数e
} ALGraph;
int Visited[MAXV] = {0};

深度优先搜索

void DFS(ALGraph *G,int v)
{
    printf("%d", v);//访问该节点
    Visited[v] = 1;//标记该节点被访问
    ArcNode* p_EdgeNode = G->adjlist[v].firstarc;//v的第条一相邻边的边头节点
    while (p_EdgeNode != NULL)//v访问所有的相邻边
    {
        int w = p_EdgeNode->adjvex;//v相邻边的定点下标
        if (Visited[w] == 0)//w尚未本被访问,递归遍历以w起始部分
            DFS(G,w);
        p_EdgeNode = p_EdgeNode->nextarc;//指向顶点v的下一条边的边头节点
    }
}

广度优先搜索

void BFS(ALGraph *G, int v)
{
    ArcNode *p; int w, i;
    int queue[MAXV], front = 0, rear = 0; //定义循环队列
    int visited[MAXV];
    for (int i = 0; i < MAXV; i++)//初始化
        visited[i] = 0;
    //访问第一个节点
    printf("%d\n",v);
    visited[v] = 1;
    //v进队列
    rear = (rear + 1) % MAXV;
    queue[rear] = v;
    while (rear != front)//queue不空
    {
        //队头节点出队
        front = (front + 1) % MAXV;
        w = queue[front];
        ArcNode* p = G->adjlist[w].firstarc;//w的相邻节点
        while (p != NULL)//层序
        {
            if (visited[p->adjvex] == 0)//尚未访问
            {
                //访问
                printf("%d\n",p->adjvex);
                visited[p->adjvex] = 1;
                //入队
                rear = (rear + 1) % MAXV; 
                queue[rear] = p->adjvex;
            }
            p = p->nextarc; //找下一个邻接顶点
        }
    }
}