图的结构

发表于 分类于 本文字数： 6.7k
图的四种数据结构

邻接矩阵法

用一个一维数组存储图的顶点信息，用一个二维数组存储图的边信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 顶点最大个数
#define MAX_LENGTH 100

// 图的顶点，仅记录最基础的数据，顶点代号
typedef char VertexType;
// 图的边，仅记录最基础的数据，边的权值
typedef int EdgeType;

/*
 * 图的结构
 * 包括顶点表和边表
 * 以及顶点个数和边的条数
 */
typedef struct Graph {
    // 顶点表
    VertexType vertices[MAX_LENGTH];
    // 边表
    EdgeType edges[MAX_LENGTH][MAX_LENGTH];
    // 顶点个数和边的条数
    int vernum, arcnum;
} Graph;

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
typedef struct Queue {
    int front = 0, rear = 0;
    int queue[MAX_LENGTH];
} Queue;

/**
 * 广度优先遍历
 * @param graph 图
 */
void BFSTraverse(Graph graph) {
    // 标记顶点是否被访问
    bool isVisited[graph.vernum];
    for (int i = 0; i < graph.vernum; ++i)
        isVisited[i] = false;

    // 存储已被访问顶点的队列
    Queue Q = {.front = 0, .rear = 0};

    // 遍历图中每个顶点，防止有顶点未联通，导致遍历不完整
    for (int i = 0; i < graph.vernum; ++i)
        if (!isVisited[i])
            BFS(graph, i, &Q, isVisited);
}

/**
 * 对某个顶点进行广度优先遍历
 * @param graph     图
 * @param init_ver  起始顶点
 * @param Q         存储已被访问顶点的队列
 * @param isVisited 标记顶点是否被访问
 */
void BFS(Graph graph, int init_ver, Queue *Q, bool isVisited[]) {
    // 访问顶点
    printf("访问顶点: %d\n", init_ver);
    isVisited[init_ver] = true;

    // 访问后的顶点入队
    Q->queue[Q->rear++] = init_ver;

    // 队列不为空时，继续遍历
    while (Q->front != Q->rear) {
        // 将已经访问过的顶点出队，作为当前顶点
        int visited_ver = Q->queue[Q->front++];
        // 访问当前顶点的所有邻接顶点
        for (int w = 0; w < graph.vernum; w++) {
            // 如果当前顶点的邻接顶点未被访问，访问并入队
            if (graph.edges[visited_ver][w] != 0 && !isVisited[w]) {
                printf("访问顶点: %d\n", w);
                isVisited[w] = true;
                Q->queue[Q->rear++] = w;
            }
        }
    }
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 深度优先遍历
 * @param graph 图
 */
void DFSTraverse(Graph graph) {
    // 标记顶点是否被访问
    bool isVisited[graph.vernum];
    for (int i = 0; i < graph.vernum; ++i)
        isVisited[i] = false;

    // 遍历图中每个顶点，防止有顶点未联通，导致遍历不完整
    for (int i = 0; i < graph.vernum; ++i)
        if (!isVisited[i])
            DFS(graph, i, isVisited);
}

/**
 * 对某个顶点进行广度优先遍历
 * @param graph     图
 * @param init_ver  起始顶点
 * @param isVisited 标记顶点是否被访问
 */
void DFS(Graph graph, int init_ver, bool isVisited[]) {
    // 访问顶点
    printf("访问顶点: %d\n", init_ver);
    isVisited[init_ver] = true;

    // 递归访问当前顶点的所有邻接顶点
    for (int w = 0; w < graph.vernum; w++) {
        // 如果当前顶点的邻接顶点未被访问，递归访问
        if (graph.edges[init_ver][w] != 0 && !isVisited[w])
            DFS(graph, w, isVisited);
    }
}

邻接表法

可以简单理解为，用一个一维数组存储图的所有顶点信息（顶点表），每个顶点结点中包含一个链式结构的边表，边表由依附于该顶点的所有边的边结点组成。

顶点结点中包含了顶点的信息和指向第一条边的指针。边结点中包含了边的信息（边的权值）、边指向的顶点，和依附于同一个结点的下一条边的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 顶点最大个数
#define MAX_LENGTH 100

// 图的顶点，仅记录最基础的数据，顶点代号
typedef char VertexType;
// 图的边，仅记录最基础的数据，边的权值
typedef int EdgeType;

// 边结点
typedef struct EdgeNode {
    // 边结点数据
    EdgeType edge_data;
    // 该边指向的顶点，在顶点表中的下标位置
    int vertex_index;
    // 指向依附于同一个结点的下一条边
    // 通过该指针形成了一个链式结构的边表
    struct EdgeNode *next_edge_node;
} EdgeNode;

// 顶点结点
typedef struct VertexNode {
    // 顶点结点数据
    VertexType vertex_data;
    // 指向依附于该顶点的第一条边
    EdgeNode *first_edge_node;
} VertexNode, VertexTable[MAX_LENGTH]; // 顶点结点和顶点表

// 图结构
typedef struct Graph {
    // 在此处成为邻接表
    VertexTable table;
    // 顶点个数和边的条数
    int vernum, arcnum;
} Graph;

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
typedef struct Queue {
    int front = 0, rear = 0;
    int queue[MAX_LENGTH];
} Queue;

/**
 * 广度优先遍历
 * @param graph 图
 */
void BFSTraverse(Graph graph) {
    // 标记顶点是否被访问
    bool isVisited[graph.vernum];
    for (int i = 0; i < graph.vernum; ++i)
        isVisited[i] = false;

    // 存储已被访问顶点的队列
    Queue Q = {.front = 0, .rear = 0};

    // 遍历图中每个顶点，防止有顶点未联通，导致遍历不完整
    for (int i = 0; i < graph.vernum; ++i)
        if (!isVisited[i])
            BFS(graph, i, &Q, isVisited);
}

/**
 * 对某个顶点进行广度优先遍历
 * @param graph     图
 * @param init_ver  起始顶点
 * @param Q         存储已被访问顶点的队列
 * @param isVisited 标记顶点是否被访问
 */
void BFS(Graph graph, int init_ver, Queue *Q, bool isVisited[]) {
    printf("访问顶点%d\n", init_ver);
    isVisited[init_ver] = true;

    // 访问后的顶点入队
    Q->queue[Q->rear++] = init_ver;

    // 队列不为空时，继续遍历
    while (Q->front != Q->rear) {
        // 将已经访问过的顶点出队，作为当前顶点
        int visited_ver = Q->queue[Q->front++];

        // 依附于当前顶点的第一条边
        EdgeNode *edge_node = NULL;
        // 通过遍历当前顶点的所有边，访问当前顶点的所有邻接顶点
        for (edge_node = graph.table[visited_ver].first_edge_node;
             edge_node != NULL;
             edge_node = edge_node->next_edge_node) {
            // 边指向的当前顶点的邻接点
            int w = edge_node->vertex_index;
            // 如果当前顶点的邻接顶点未被访问，访问并入队
            if (!isVisited[w]) {
                printf("访问顶点%d\n", w);
                isVisited[w] = true;
                Q->queue[Q->rear++] = w;
            }
        }
    }
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 深度优先遍历
 * @param graph 图
 */
void DFSTraverse(Graph graph) {
    // 标记顶点是否被访问
    bool isVisited[graph.vernum];
    for (int i = 0; i < graph.vernum; ++i)
        isVisited[i] = false;

    // 遍历图中每个顶点，防止有顶点未联通，导致遍历不完整
    for (int i = 0; i < graph.vernum; ++i)
        if (!isVisited[i])
            DFS(graph, i, isVisited);
}

/**
 * 对某个顶点进行深度优先遍历
 * @param graph     图
 * @param init_ver  起始顶点
 * @param isVisited 标记顶点是否被访问
 */
void DFS(Graph graph, int init_ver, bool isVisited[]) {
    printf("访问顶点%d\n", init_ver);
    isVisited[init_ver] = true;

    // 依附于当前顶点的第一条边
    EdgeNode *edge_node = NULL;
    // 通过遍历当前顶点的所有边，访问当前顶点的所有邻接顶点
    for (edge_node = graph.table[init_ver].first_edge_node;
         edge_node != NULL;
         edge_node = edge_node->next_edge_node) {
        // 边指向的当前顶点的邻接点
        int w = edge_node->vertex_index;
        // 如果当前顶点的邻接顶点未被访问，访问并入队
        if (!isVisited[w])
            DFS(graph, w, isVisited);
    }
}

十字链表法

十字链表仅可存储有向图，用一个一维数组存储图的所有顶点信息（顶点表），每个顶点结点中包含两个链式结构的弧表（出弧和入弧），出弧由弧尾相同的弧结点组成，入弧由弧头相同的弧结点组成。

顶点结点中包含了顶点的信息、第一条入弧的指针和第一条出弧的指针。弧结点中包含了弧的信息（弧的权值）、弧尾依附的顶点、弧头指向的顶点，和弧尾弧头相同的下一条弧的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 顶点最大个数
#define MAX_LENGTH 100

// 图的顶点，仅记录最基础的数据，顶点代号
typedef char VertexType;
// 图的弧，仅记录最基础的数据，弧的权值
typedef int EdgeType;

// 弧结点
typedef struct EdgeNode {
    // 弧结点数据
    EdgeType edge_data;
    // 弧尾依附的顶点在顶点表中的下标
    int tail_vertex_index;
    // 弧头指向的顶点在顶点表中的下标
    int head_vertex_index;
    // 指向弧尾相同的下一条弧，通过该指针形成出弧表
    struct EdgeNode *tail_edge_node;
    // 指向弧头相同的下一条弧，通过该指针形成入弧表
    struct EdgeNode *head_edge_node;
} EdgeNode;

// 顶点结点
typedef struct VertexNode {
    // 顶点结点数据
    VertexType vertex_data;
    // 指向顶点的第一条入弧
    EdgeNode *firstIn;
    // 指向顶点的第一条出弧
    EdgeNode *firstOut;
} VertexNode, VertexTable[MAX_LENGTH]; // 顶点结点和顶点表

// 图结构
typedef struct Graph {
    // 在此处成为十字链表
    VertexTable table;
    // 顶点个数和边的条数
    int vernum, arcnum;
} Graph;

邻接多重表

十字链表仅可存储无向图，用一个一维数组存储图的所有顶点信息（顶点表），每个顶点结点中包含一个链式结构的边表，边表中边表结点的成分复杂，每个边结点中包含两个指针，指向两个顶点。

顶点结点中包含了顶点的信息和指向第一条边的指针。边结点中包含了边的信息、边依附的第一个顶点、同样依附的第一个顶点的下一条边指针、边依附的第二个顶点，同样依附的第而个顶点的下一条边指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 顶点最大个数
#define MAX_LENGTH 100

// 图的顶点，仅记录最基础的数据，顶点代号
typedef char VertexType;
// 图的边，仅记录最基础的数据，边的权值
typedef int EdgeType;

// 边结点
typedef struct EdgeNode {
    // 边结点数据
    EdgeType edge_data;
    // 边依附的第一个顶点，在顶点表中的下标
    int i_vertex_index;
    // 指向依附的第一个顶点的下一条边
    struct EdgeNode *i_edge_node;
    // 边依附的第二个顶点，在顶点表中的下标
    int j_vertex_index;
    // 指向依附的第二个顶点的下一条边
    struct EdgeNode *j_edge_node;
} EdgeNode;

// 顶点结点
typedef struct VertexNode {
    // 顶点结点数据
    VertexType vertex_data;
    // 指向依附于该顶点的第一条边
    EdgeNode *first_edge_node;
} VertexNode, VertexTable[MAX_LENGTH]; // 顶点结点和顶点表

typedef struct Graph {
    // 在此处成为邻接多重表
    VertexTable table;
    // 顶点个数和边的条数
    int vernum, arcnum;
} Graph;