四、图（11 题）

校订文本 · 对照材料 · 专题阅读 · 保留代码与校订注 · 本次导入快照

四、图（11 题）

默认结构

邻接表

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

typedef struct {
    char data;
    ArcNode *firstarc;
} VertexNode;

typedef struct {
    VertexNode adjList[MAXSIZE];
    int numVertices;
    int numEdges;
} Graph;

邻接矩阵

#define INF INT_MAX

typedef struct {
    char vertex[MAXSIZE];
    int edge[MAXSIZE][MAXSIZE];
    int numVertices;
    int numEdges;
} MatrixGraph;

除第 8 题 Floyd 算法外，本节邻接矩阵代码均按无权图处理，以 0 表示无边、非 0 表示有边。Floyd 题另按“无边为 INF、对角线为 0”解释矩阵。

1. 求无向连通图中距顶点 v 最远的一个结点

int farthestVertexByBFS(Graph G, int start) {
    bool visited[MAXSIZE] = {false};
    int queue[MAXSIZE];
    int front = 0, rear = 0;
    int last = start;

    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int v = queue[front++];
        last = v;

        for (ArcPtr p = G.adjList[v].firstarc;
             p != NULL; p = p->nextarc) {
            int w = p->adjvex;
            if (!visited[w]) {
                visited[w] = true;
                queue[rear++] = w;
            }
        }
    }

    return last;
}

复杂度： 时间 O(|V|+|E|)，额外空间 O(|V|)。

核心思路： BFS 按与起点的最短路径长度逐层访问；队列中最后出队的结点属于最远层，因此是一个最远结点。图连通是题设前提。

2. 判断有向图中从 Vi 到 Vj 是否存在路径

DFS

bool reachableDFSImpl(Graph G, int current, int target,
                      bool visited[]) {
    if (current == target)
        return true;

    visited[current] = true;
    for (ArcPtr p = G.adjList[current].firstarc;
         p != NULL; p = p->nextarc) {
        int next = p->adjvex;
        if (!visited[next] && reachableDFSImpl(G, next, target, visited))
            return true;
    }
    return false;
}

bool reachableDFS(Graph G, int start, int target) {
    bool visited[MAXSIZE] = {false};
    return reachableDFSImpl(G, start, target, visited);
}

BFS

bool reachableBFS(Graph G, int start, int target) {
    bool visited[MAXSIZE] = {false};
    int queue[MAXSIZE];
    int front = 0, rear = 0;

    queue[rear++] = start;
    visited[start] = true;

    while (front < rear) {
        int v = queue[front++];
        if (v == target)
            return true;

        for (ArcPtr p = G.adjList[v].firstarc;
             p != NULL; p = p->nextarc) {
            int w = p->adjvex;
            if (!visited[w]) {
                visited[w] = true;
                queue[rear++] = w;
            }
        }
    }

    return false;
}

复杂度： 两种方法时间均为 O(|V|+|E|)，额外空间均为 O(|V|)。

校订注：原稿 DFS 代码的 if (visit[p->adjvex] == 0)) 多出一个右括号；本版同时改成找到目标后立即返回，避免无意义搜索。

3. 输出有向图的所有根结点

若从顶点 r 能到达图中所有顶点，则称 r 为图的根结点。

void markReachable(Graph G, int v, bool visited[]) {
    visited[v] = true;
    for (ArcPtr p = G.adjList[v].firstarc;
         p != NULL; p = p->nextarc) {
        if (!visited[p->adjvex])
            markReachable(G, p->adjvex, visited);
    }
}

void printAllRootVertices(Graph G) {
    for (int start = 0; start < G.numVertices; start++) {
        bool visited[MAXSIZE] = {false};
        markReachable(G, start, visited);

        bool reachesAll = true;
        for (int v = 0; v < G.numVertices; v++) {
            if (!visited[v]) {
                reachesAll = false;
                break;
            }
        }

        if (reachesAll)
            printf("%d ", start);
    }
}

复杂度： 时间 O(|V|(|V|+|E|))，额外空间 O(|V|)。

4. 判断无向连通图是否存在 EL 路径（2021 年统考题）

题设给定图连通且 |E|>0。当奇度顶点数为 0 或 2 时，存在包含全部边的欧拉通路（EL 路径）。

int hasEulerTrail(MatrixGraph G) {
    int oddCount = 0;

    for (int i = 0; i < G.numVertices; i++) {
        int degree = 0;
        for (int j = 0; j < G.numVertices; j++) {
            if (G.edge[i][j] != 0)
                degree++;
        }
        if (degree % 2 != 0)
            oddCount++;
    }

    return oddCount == 0 || oddCount == 2;
}

复杂度： 时间 O(|V|²)，额外空间 O(1)。

若邻接矩阵明确是只含 0/1 的无权矩阵，也可直接对一行元素求和得到度数。若是带权矩阵，则必须统计“非零边数”，不能把权值之和当作度。

5. 输出有向图的所有 K 顶点（2023 年统考题）

出度大于入度的顶点称为 K 顶点；函数输出所有 K 顶点并返回其数量。

int printKVertices(MatrixGraph G) {
    int count = 0;

    for (int i = 0; i < G.numVertices; i++) {
        int indegree = 0;
        int outdegree = 0;

        for (int j = 0; j < G.numVertices; j++) {
            if (G.edge[i][j] != 0) outdegree++;
            if (G.edge[j][i] != 0) indegree++;
        }

        if (outdegree > indegree) {
            printf("%c ", G.vertex[i]);
            count++;
        }
    }

    return count;
}

复杂度： 时间 O(|V|²)，额外空间 O(1)。

6. 用邻接表统计有向图每个顶点的入度和出度

void calculateDegrees(Graph G, int indegree[], int outdegree[]) {
    for (int i = 0; i < G.numVertices; i++) {
        indegree[i] = 0;
        outdegree[i] = 0;
    }

    for (int v = 0; v < G.numVertices; v++) {
        for (ArcPtr p = G.adjList[v].firstarc;
             p != NULL; p = p->nextarc) {
            outdegree[v]++;
            indegree[p->adjvex]++;
        }
    }
}

复杂度： 时间 O(|V|+|E|)；除输出数组外，额外空间 O(1)。

7. 判断无向图是否为一棵树

void countReachableVertices(Graph G, int v,
                            bool visited[], int *count) {
    visited[v] = true;
    (*count)++;

    for (ArcPtr p = G.adjList[v].firstarc;
         p != NULL; p = p->nextarc) {
        if (!visited[p->adjvex])
            countReachableVertices(G, p->adjvex, visited, count);
    }
}

bool isTree(Graph G) {
    if (G.numVertices == 0)
        return false;

    bool visited[MAXSIZE] = {false};
    int reachableCount = 0;
    countReachableVertices(G, 0, visited, &reachableCount);

    return reachableCount == G.numVertices
        && G.numEdges == G.numVertices - 1;
}

复杂度： 时间 O(|V|+|E|)，额外空间 O(|V|)。

核心思路： 无向图是树，当且仅当它连通且边数为 |V|-1。

校订注：原稿在 DFS 内误调用了不存在的 func(...)，应递归调用 DFS 自身；本版重命名后已修正。

8. Floyd 算法求有向图或无向图的最短路径

假设 G.edge[i][j] 为边权；无边时为 INF，对角线为 0。

void floyd(MatrixGraph G,
           int dist[][MAXSIZE],
           int intermediate[][MAXSIZE]) {
    int n = G.numVertices;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = G.edge[i][j];
            intermediate[i][j] = -1;
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    long long candidate = (long long)dist[i][k] + dist[k][j];
                    if (candidate < dist[i][j]) {
                        dist[i][j] = (int)candidate;
                        intermediate[i][j] = k;
                    }
                }
            }
        }
    }
}

void printIntermediateVertices(int u, int v,
                               int intermediate[][MAXSIZE]) {
    int k = intermediate[u][v];
    if (k == -1)
        return;

    printIntermediateVertices(u, k, intermediate);
    printf("%d ", k);
    printIntermediateVertices(k, v, intermediate);
}

void printShortestPath(int u, int v,
                       int intermediate[][MAXSIZE]) {
    printf("%d ", u);
    printIntermediateVertices(u, v, intermediate);
    printf("%d\n", v);
}

复杂度： 时间 O(|V|³)，额外空间 O(|V|²)。

校订注：原稿写作 Floyed/floyed，规范名称为 Floyd；本版还补上了对 INF 的判断，避免“不可达距离相加”导致溢出或错误更新。

9. 用邻接表判断有向图是否有环（拓扑排序）

函数约定：有环返回 true，无环返回 false。

bool hasDirectedCycleList(Graph G) {
    int indegree[MAXSIZE] = {0};
    int stack[MAXSIZE];
    int top = -1;
    int visitedCount = 0;

    for (int v = 0; v < G.numVertices; v++) {
        for (ArcPtr p = G.adjList[v].firstarc;
             p != NULL; p = p->nextarc)
            indegree[p->adjvex]++;
    }

    for (int v = 0; v < G.numVertices; v++) {
        if (indegree[v] == 0)
            stack[++top] = v;
    }

    while (top != -1) {
        int v = stack[top--];
        visitedCount++;

        for (ArcPtr p = G.adjList[v].firstarc;
             p != NULL; p = p->nextarc) {
            if (--indegree[p->adjvex] == 0)
                stack[++top] = p->adjvex;
        }
    }

    return visitedCount != G.numVertices;
}

复杂度： 时间 O(|V|+|E|)，额外空间 O(|V|)。

校订注：原稿标题写“有/无向图”，并注释无向图使用度为 1 的结点。拓扑排序只定义在有向图上，不能据此一般性地判断无向图是否有环。无向图判环可使用带父结点参数的 DFS 或并查集。

10. 用邻接矩阵判断有向图是否有环（拓扑排序）

bool hasDirectedCycleMatrix(MatrixGraph G) {
    int indegree[MAXSIZE] = {0};
    int stack[MAXSIZE];
    int top = -1;
    int visitedCount = 0;

    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            if (G.edge[j][i] != 0)
                indegree[i]++;
        }
    }

    for (int v = 0; v < G.numVertices; v++) {
        if (indegree[v] == 0)
            stack[++top] = v;
    }

    while (top != -1) {
        int v = stack[top--];
        visitedCount++;

        for (int w = 0; w < G.numVertices; w++) {
            if (G.edge[v][w] != 0 && --indegree[w] == 0)
                stack[++top] = w;
        }
    }

    return visitedCount != G.numVertices;
}

复杂度： 时间 O(|V|²)，额外空间 O(|V|)。

11. 判断有向图的拓扑排序是否唯一（2024 年统考题）

bool hasUniqueTopologicalOrder(MatrixGraph G) {
    int indegree[MAXSIZE] = {0};
    int stack[MAXSIZE];
    int top = -1;
    int visitedCount = 0;

    for (int i = 0; i < G.numVertices; i++) {
        for (int j = 0; j < G.numVertices; j++) {
            if (G.edge[j][i] != 0)
                indegree[i]++;
        }
    }

    for (int v = 0; v < G.numVertices; v++) {
        if (indegree[v] == 0)
            stack[++top] = v;
    }

    if (top > 0)
        return false;

    while (top != -1) {
        int v = stack[top--];
        visitedCount++;

        for (int w = 0; w < G.numVertices; w++) {
            if (G.edge[v][w] != 0 && --indegree[w] == 0)
                stack[++top] = w;
        }

        if (top > 0)
            return false;
    }

    return visitedCount == G.numVertices;
}

复杂度： 时间 O(|V|²)，额外空间 O(|V|)。

核心思路： 拓扑排序的每一步都必须恰好只有一个入度为 0 的候选顶点；若某一步候选数大于 1，拓扑序不唯一；若最终未访问全部顶点，则图有环，也不存在拓扑序。

---