如何用代码实现图的邻接矩阵与邻接表存储结构，并编写深度优先和广度优先遍历算法？

一、邻接矩阵存储结构

邻接矩阵使用二维数组 matrix[V][V] 表示图，其中 V 为顶点数。若顶点 i 与 j 之间存在边，则 matrix[i][j] = 1（带权图存权重），否则为 0 或无穷大。

#define MAXV 100
typedef struct {
    int matrix[MAXV][MAXV];
    int vexnum, edgenum;
} MGraph;

适用条件：适合稠密图，判断两顶点是否相邻的时间复杂度为 O(1)。

二、邻接表存储结构

邻接表为每个顶点维护一个单链表，链表节点存储与该顶点相邻的顶点编号及指向下一个邻接点的指针。

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct VNode {
    int data;
    ArcNode *firstarc;
} VNode, AdjList[MAXV];

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

适用条件：适合稀疏图，空间复杂度为 O(V+E)，优于邻接矩阵的 O(V²)。

三、深度优先遍历（DFS）

DFS 从起始顶点出发，沿一条路径尽可能深入访问，遇到死胡同则回溯。通常用递归实现，本质是隐式使用了系统栈。

int visited[MAXV] = {0};

void DFS(ALGraph *G, int v) {
    visited[v] = 1;
    // 处理顶点 v
    ArcNode *p = G->vertices[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->nextarc;
    }
}

四、广度优先遍历（BFS）

BFS 从起始顶点出发，先访问所有直接邻接点，再依次访问这些邻接点的邻接点。必须借助显式队列实现。

void BFS(ALGraph *G, int v) {
    int queue[MAXV], front = 0, rear = 0;
    visited[v] = 1;
    // 处理顶点 v
    queue[rear++] = v;
    while (front != rear) {
        int u = queue[front++];
        ArcNode *p = G->vertices[u].firstarc;
        while (p != NULL) {
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                // 处理顶点 p->adjvex
                queue[rear++] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}

五、常见误区

非连通图漏访：上述遍历仅覆盖起始顶点所在的连通分量。对于非连通图，需在外层增加循环，对所有未访问顶点调用 DFS 或 BFS。
状态未重置：多次遍历时未将 visited 数组重新初始化为 0，导致后续遍历结果错误。
有向图与无向图建边差异：无向图在邻接矩阵中需对称赋值（matrix[i][j] 与 matrix[j][i]），邻接表中需在两个顶点的链表中各插入一条边；有向图仅需单向操作。
BFS 标记时机：入队时即应标记为已访问，而非出队时标记，否则同一顶点可能被重复入队导致队列溢出或死循环。