跳转至

数据结构第七章作业

第一题

试证明：对于一个无向图 $ G = (V, E) $，若 $ G $ 中各顶点的度均大于或等于 2，则 $ G $ 中必有回路。

解：

假设 \(H=(V_H,E_H)\) 为 \(G\) 的一个极大连通块，\(V_H = \set{a_1,a_2,...,a_n}\)，则必存在简单路径 \(P=({a_{k_1},a_{k_2},...,a_{k_n}})\) 。

由于 \(G\) 中各顶点度数大于等于2，存在点 \(a_{k_i}\) 使得 \(a_{k_1}\) 与 \(a_{k_i}\) 之间有一条边。

从而 \((a_{k_1}, a_{k_2}, ... a_{k_i}, a_{k_1})\) 为一条简单回路。

因此 \(G\) 中必有回路。

第二题

已知某图的邻接表如下图所示

(1) 写出此邻接表对应的邻接矩阵； (2) 写出由v1开始的深度优先遍历的序列； (3) 写出由v1开始的深度优先的生成树； (4) 写出由v1开始的广度优先遍历的序列； (5) 写出由v1开始的广度优先的生成树； (6) 写出将无向图的邻接矩阵转换成邻接表的算法。

解：

(1) $$ \begin{array}{c|cccccc} & v_1 & v_2 & v_3 & v_4 & v_5 & v_6 \ \hline v_1 & 0 & 1 & 1 & 1 & 0 & 0 \ v_2 & 1 & 0 & 0 & 0 & 1 & 0 \ v_3 & 1 & 0 & 0 & 0 & 1 & 0 \ v_4 & 1 & 0 & 0 & 0 & 0 & 1 \ v_5 & 0 & 1 & 1 & 0 & 0 & 0 \ v_6 & 0 & 0 & 0 & 1 & 0 & 0 \end{array} $$ (2)

v1,v2,v5,v3,v4,v6

(3)

image-20250606102103073

(4)

v1,v2,v3,v4,v5,v6

(5)

image-20250606102944079

(6)

void convert(Mgraph g, Agraph *G) {
    G->n = g.n, G->e = g.e;
    for (int i = 1; i <= g.n; i++) {
        G->adjlist[i].data = g.vexs[i].data;
        G->adjlist[i].firstarc = NULL;
        ArcNode **last = &G->adjlist[i].firstarc;
        for (int j = 1; j <= g.n; j++) {
            if (g.edges[i][j]) {
                ArcNode* tmp = (ArcNode*)malloc(sizeof(ArcNode));
                tmp->adjvex = j;
                tmp->weight = g.edges[i][j];
                *last = tmp;
                last = &tmp->nextarc;
            }
        }
    }
}

第三题

已知一图如下图所示： (1) 写出全部拓扑排序； (2) 以v1为源点，以v8为汇点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； (3) 利用Dijkstra算法求V1结点到各点的最短距离。

image-20250606112127571

解：

(1)

v1,v2,v3,v4,v6,v5,v7,v8

v1,v3,v2,v4,v6,v5,v7,v8

(2)

最早时间 最晚时间
v1 0 0
v2 2 2
v3 3 3
v4 7 7
v5 13 13
v6 11 11
v7 16 16
v8 17 17

（3）

v1,v2,v4,v6,v5,v7,v8

v1,v2,v4,v6,v8

v1,v3,v5,v7,v8

第四题

有一图的邻接矩阵如下，试给出用Floyd算法求各点间最短距离的矩阵序列 \(A^1\)，\(A^2\)，\(A^3\)，\(A^4\)。

\[ A = \begin{bmatrix} 0 & 2 & \infty & \infty \\ \infty & 0 & 1 & 6 \\ 5 & \infty & 0 & 4 \\ 3 & \infty & \infty & 0 \end{bmatrix} \]

解： $$ A^1 = \begin{bmatrix} 0 & 2 & \infty & \infty \ \infty & 0 & 1 & 6 \ 5 & 7 & 0 & 4 \ 3 & 5 & \infty & 0 \end{bmatrix} $$

\[ A^2 = \begin{bmatrix} 0 & 2 & 3 & 8 \\ \infty & 0 & 1 & 6 \\ 5 & 7 & 0 & 4 \\ 3 & 5 & 6 & 0 \end{bmatrix} \]
\[ A^3 = \begin{bmatrix} 0 & 2 & 3 & 7 \\ 6 & 0 & 1 & 5 \\ 5 & 7 & 0 & 4 \\ 3 & 5 & 6 & 0 \end{bmatrix} \]
\[ A^3 = \begin{bmatrix} 0 & 2 & 3 & 7 \\ 6 & 0 & 1 & 5 \\ 5 & 7 & 0 & 4 \\ 3 & 5 & 6 & 0 \end{bmatrix} \]
\[ A^4 = \begin{bmatrix} 0 & 2 & 3 & 7 \\ 6 & 0 & 1 & 5 \\ 5 & 7 & 0 & 4 \\ 3 & 5 & 6 & 0 \end{bmatrix} \]

第五题

已知某图的邻接矩阵为A，即若从i到j有边，则A[i, j]=1，否则A[i, j]=0。试编写一算法求矩阵A的传递闭包C：使得若从i到j有一条或多条路径，则C[i, j]=1，否则C[i, j]=0。

解：

经典的Warshell-Floyd算法求传递闭包，这是“离散数学（上）”这门课的大作业。

typedef int adjmatrix[MAXV][MAXV];
void change(adjmatrix A, adjmatrix C, int n) {
    // C = A^0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            C[i][j] = A[i][j];
        }
    }
    // C^{k-1} -> C^k
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                C[i][j] |= C[i][k] & C[k][j];
            }
        }
    }
}