数据结构篇--DFS树-EW帮帮网

强化版为基础版引入了外部节点等内容，将DFS递归过程遇到的图边分为四类：

树链接
父链接
后向链接
前向链接

注意：除了 pre 数组外，不需要引入额外数据结构，就可以判断出parent link、back link、down link。

示例

示例1 根据如下所示图，编程实现dfsR函数。
图18.5
图18.5对应的边集合

0-2 0-5 0-7
1-7
2-6
3-4 3-5
4-5 4-6 4-7

实现

下面将以邻接矩阵实现为例进行介绍。

/**
 * FileName: TestDFSTrace.c
 * ----------------------------------------------------------------------------------------------------
 * 以图的邻接矩阵表示为例，依次介绍：
 * - 图的DFS递归树基础版
 * - 图的DFS递归树强化版
 *
 * 强化版为基础版引入了外部节点等内容，将DFS递归过程遇到的图边分为四类：
 * - 树链接
 * - 父链接
 * - 后向链接
 * - 前向链接
 *
 * 注意：非必要不引入额外数据结构，所以这个版本中取消了st数组
 *
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

//边相关
typedef struct {
    int v;
    int w;
}
Edge;

//图相关
typedef struct graph *Graph;
struct graph {
    int V;
    int E;
    int** adj;
};

#define dfsR search
#define maxV 8

static int cnt;
static int pre[maxV];
static int indent = 0; // 全局变量表示当前缩进层数
// static int st[maxV];

//辅助函数声明
int** MATRIXinit(int, int, int);
Edge EDGE(int, int);
void GRAPHshow(Graph);
void dfsR(Graph, Edge);
void printIndent();
void dfsR2(Graph, Edge);
void dfsR3(Graph, Edge);

//图操作声明
Graph GRAPHinit(int);
void GRAPHinsertE(Graph, Edge);
void GRAPHremoveE(Graph, Edge);
int GRAPHedges(Edge [], Graph);
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

//辅助函数实现
int** MATRIXinit(int r, int c, int val) {
    int i;
    int j;
    int** t = malloc(r * sizeof(int*));
    for (i = 0; i < r; i++) {
        t[i] = malloc(c * sizeof(int));
    }
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            t[i][j] = val;
        }
    }
    return t;
}

Edge EDGE(int v, int w) {
    Edge edge;
    edge.v = v;
    edge.w = w;
    return edge;
}

void GRAPHshow(Graph G) {
    int i;
    int j;
    printf("%d vertices, %d edges\n", G->V, G->E);

    //邻接列表
    for (i = 0; i < G->V; i++) {
        printf("%2d:", i);
        for (j = 0; j < G->V; j++) {
            if (G->adj[i][j] == 1) {
                printf(" %2d", j);
            }
        }
        printf("\n");
    }
    // //邻接矩阵
    // for (i = 0; i < G->V; i++) {
    //     printf("%2d:", i);
    //     for (j = 0; j < G->V; j++) {
    //         printf(" %2d", G->adj[i][j]);
    //     }
    //     printf("\n");
    // }
}

/**
 * Program 18.1 Depth-first search (adjacency-matrix)
 * --------------------------------------------------------------------------------------------------------------------
 * This code is intended for use with a generic graph-search ADT function that
 * - initializes a counter `cnt` to 0 and all of the entries in the vertex-indexed array `pre` to -1,
 * - then calls search once for each connected component (see Program 18.3),
 * assuming that the call `search(G, EDGE(v, v))` marks all vertices in the same connected component as `v`
 * (by setting their `pre` entries to be nonnegative).
 *
 * Here, we implement `search` with a recursive function `dfsR` that visits all the vertices connected to `e.w`
 * by scanning through its row in the adjacency matrix and
 * calling itself for each edge that leads to an unmarked vertex.
 * --------------------------------------------------------------------------------------------------------------------
 * 递归版dfs
 * @param G
 * @param e
 */
void dfsR(Graph G, Edge e) {
    int t;
    int w = e.w;
    pre[w] = cnt++;
    for (t = 0; t < G->V; t++) {
        if (G->adj[w][t] != 0) {
            if (pre[t] == -1) {
                dfsR(G, EDGE(w, t));
            }
        }
    }

}

void printIndent() {
    int i;
    for (i = 0; i < indent; i++) {
        printf("  "); // 每层缩进2个空格
    }
}

void dfsR2(Graph G, Edge e) {
    int t;
    int w = e.w;

    pre[w] = cnt++;

    for (t = 0; t < G->V; t++) {
        if (G->adj[w][t] != 0) {
            printIndent();  // 输出缩进
            printf("%d-%d\n", w, t); // 打印边 w-t

            if (pre[t] == -1) {
                indent++; // 进入下一层递归，增加缩进
                dfsR2(G, EDGE(w, t)); // 递归处理下一个顶点
            }
        }
    }
    indent--; // 退出递归，恢复缩进
}

void dfsR3(Graph G, Edge e) {
    int t;
    int w = e.w;
    int v = e.v;
    // st[w] = v;

    pre[w] = cnt++;

    for (t = 0; t < G->V; t++) {
        // if (G->adj[w][t] != 0) {
        //     if (pre[t] == -1) {
        //         indent++; // 进入下一层递归，增加缩进
        //         printIndent();  // 输出缩进
        //         printf("%d-%d tree\n", w, t); // 打印边 w-t 树链接
        //         dfsR3(G, EDGE(w, t)); // 递归处理下一个顶点
        //     }else if (st[w] == t) {
        //         printIndent();  // 输出缩进
        //         printf("%d-%d parent\n", w, t); // 打印边 w-t 父链接
        //     }else if (pre[t] < pre[w]) {
        //         printIndent();  // 输出缩进
        //         printf("%d-%d back\n", w, t); // 打印边 w-t 后向链接
        //     }else if (pre[t] > pre[w]) {
        //         printIndent();  // 输出缩进
        //         printf("%d-%d down\n", w, t); // 打印边 w-t 前向链接
        //     }
        // }
        if (G->adj[w][t] != 0) {
            if (pre[t] == -1) {
                indent++; // 进入下一层递归，增加缩进
                printIndent();  // 输出缩进
                printf("%d-%d tree\n", w, t); // 打印边 w-t 树链接
                dfsR3(G, EDGE(w, t)); // 递归处理下一个顶点
            }else if (v == t) {
                printIndent();  // 输出缩进
                printf("%d-%d parent\n", w, t); // 打印边 w-t 父链接
            }else if (pre[t] < pre[w]) {
                printIndent();  // 输出缩进
                printf("%d-%d back\n", w, t); // 打印边 w-t 后向链接
            }else if (pre[t] > pre[w]) {
                printIndent();  // 输出缩进
                printf("%d-%d down\n", w, t); // 打印边 w-t 前向链接
            }
        }
    }
    indent--; // 退出递归，恢复缩进
}

//图操作函数实现
Graph GRAPHinit(int V) {
    Graph G = malloc(sizeof(*G));
    G->V = V;
    G->E = 0;
    G->adj = MATRIXinit(V, V, 0);
    cnt = 0;
    int v;
    for (v = 0; v < maxV; v++) {
        pre[v] = -1;
    }
    indent = 0;
    // for (v = 0; v < maxV; v++) {
    //     st[v] = -1;
    // }
    return G;
}

void GRAPHinsertE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 0) {
        G->E++;
    }
    G->adj[v][w] = 1;
    G->adj[w][v] = 1;
}

void GRAPHremoveE(Graph G, Edge e) {
    int v = e.v;
    int w = e.w;
    if (G->adj[v][w] == 1) {
        G->E--;
    }
    G->adj[v][w] = 0;
    G->adj[w][v] = 0;
}
int GRAPHedges(Edge a[], Graph G) {
    int v;
    int w;
    int E = 0;
    for (v = 0; v < G->V; v++) {
        for (w = v+1; w < G->V; w++) {
            if (G->adj[v][w] == 1) {
                a[E++] = EDGE(v, w);
            }
        }
    }
    return E;
}
Graph GRAPHcopy(Graph);
void GRAPHdestroy(Graph);

//测试函数声明
void test_dfs_trace();

int main(int argc, char *argv[]) {
    test_dfs_trace();
    return 0;
}

//测试函数实现
void test_dfs_trace() {
    int V = 8;
    Graph G = GRAPHinit(V);
    Edge edge1 = EDGE(0, 2);
    Edge edge2 = EDGE(0, 5);
    Edge edge3 = EDGE(0, 7);
    Edge edge4 = EDGE(1, 7);
    Edge edge5 = EDGE(2, 6);
    Edge edge6 = EDGE(3, 4);
    Edge edge7 = EDGE(3, 5);
    Edge edge8 = EDGE(4, 5);
    Edge edge9 = EDGE(4, 6);
    Edge edge10 = EDGE(4, 7);

    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);

    // GRAPHshow(G);
    printf("DFS Trace base version:\n");
    printf("--------------------------------------------------------------\n");
    printf("0-0\n");
    indent++;
    dfsR2(G, EDGE(0,0));
    printf("--------------------------------------------------------------\n");

    G = GRAPHinit(V);
    GRAPHinsertE(G, edge1);
    GRAPHinsertE(G, edge2);
    GRAPHinsertE(G, edge3);
    GRAPHinsertE(G, edge4);
    GRAPHinsertE(G, edge5);
    GRAPHinsertE(G, edge6);
    GRAPHinsertE(G, edge7);
    GRAPHinsertE(G, edge8);
    GRAPHinsertE(G, edge9);
    GRAPHinsertE(G, edge10);

    printf("DFS Trace improve version:\n");
    printf("--------------------------------------------------------------\n");
    printf("0-0 tree\n");
    indent++;
    dfsR3(G, EDGE(0,0));
    printf("--------------------------------------------------------------\n");
}

TestDFSTrace.c

结果

DFS递归树追踪基础版的运行输出为：

以此形成的DFS递归树基础版长这样：

DFS递归树追踪强化版的运行输出为：

0-0 tree
    0-2 tree
    2-0 parent
      2-6 tree
      6-2 parent
        6-4 tree
          4-3 tree
          3-4 parent
            3-5 tree
            5-0 back
            5-3 parent
            5-4 back
        4-5 down
        4-6 parent
          4-7 tree
          7-0 back
            7-1 tree
            1-7 parent
          7-4 parent
  0-5 down
  0-7 down

以此为基础的DFS递归树强化版长这样：

tree links point to unshaded circles, and
parent links point to shaded circles, and
back links point to unshaded squares, and
down links point to shaded squares.

数据结构篇--DFS树

示例

实现

结果

应用

网站公告

今日签到

热门文章

最新发布