data-structure-c/Graph/AdjacencyMatrixGraph/AdjacencyMatrixGraph.h at master · lizexinxin/data-structure-c · GitHub

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//
// Created by Vincent on 2021/5/9.
//

#ifndef INC_ADJACENCYMATRIXGRAPH_H
#define INC_ADJACENCYMATRIXGRAPH_H

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

#include "SinglyLinkedList.h"
#include "ArrayList.h"

/**
 * 边结构体
 */
typedef struct {
    /**
     * from顶点
     */
    void *from;
    /**
     * to顶点
     */
    void *to;
    /**
     * 边的权重
     */
    double weight;
} AdjacencyMatrixEdge;

/**
 * 图结构体
 */
typedef struct {
    /**
     * 当前Graph可以容纳的最大顶点数量
     */
    int vertexCapacity;
    /**
     * 当前Graph已经容纳的顶点数量
     */
    int vertexCount;
    /**
     * 顶点数据大小
     */
    int vertexDataSize;
    /**
     * 所有的顶点
     */
    ArrayList *vertexList;
    /**
     * 邻接矩阵；二维表示；二维压缩成一维用
     */
    double *matrix;
    /**
     * 是否有向
     */
    bool direction;

    /**
     * 比较顶点的函数指针
     */
    bool (*equalsVertex)(void *, void *);

    /**
     * toString元素的函数指针
     */
    char *(*toStringElement)(void *);
} AdjacencyMatrixGraph;

/**
 * 遍历类型
 */
typedef enum {
    /**
     * 深度优先遍历
     */
    DFS = 0,
    /**
     * 广度优先遍历
     */
    BFS = 1
} AdjacencyMatrixGraphTraversalType;


/**
 * 打印Graph
 *
 * @param graph
 */
void adjacencyMatrixGraphPrintf(AdjacencyMatrixGraph *graph);

/**
 * 初始化一个图
 *
 * @param initCapacity 初始容量
 * @param direction 是否有向
 * @param equalsVertex 比较顶点，相通时返回true，否则返回false
 * @return 图指针
 */
AdjacencyMatrixGraph *adjacencyMatrixGraphInitiate(int initCapacity, bool direction,
                                                   bool (equalsVertex)(void *, void *),
                                                   char *(*toStringElement)(void *));

/**
 * 插入边
 *
 * @param graph 图指针
 * @param edge 边
 */
void adjacencyMatrixGraphInsertEdge(AdjacencyMatrixGraph *graph, AdjacencyMatrixEdge edge);

/**
 * 删除边
 *
 * @param graph 图指针
 * @param from from顶点
 * @param to to顶点
 */
void adjacencyMatrixGraphDeleteEdge(AdjacencyMatrixGraph *graph, void *from, void *to);

/**
 * 深度优先遍历
 *
 * @param graph
 * @param traversalResult
 */
void adjacencyMatrixGraphDFS(AdjacencyMatrixGraph *graph, SinglyLinkedList *traversalResult);

/**
 * 广度优先遍历
 *
 * @param graph
 * @param traversalResult
 */
void adjacencyMatrixGraphBFS(AdjacencyMatrixGraph *graph, SinglyLinkedList *traversalResult);

/**
 * 检查是否为连通图
 *
 * @param graph
 * @return
 */
bool adjacencyMatrixGraphIsConnected(AdjacencyMatrixGraph *graph);

/**
 * Prim算法获取最小生成树
 *
 * @param graph
 * @return 最小生成树 LinkList<Edge>
 */
SinglyLinkedList *adjacencyMatrixGraphPrim(AdjacencyMatrixGraph *graph);

/**
 * 拓扑排序并按层级打印
 *
 * @param graph
 */
void adjacencyMatrixGraphTopologicalSortingLevelPrintf(AdjacencyMatrixGraph *graph);

#endif  // INC_ADJACENCYMATRIXGRAPH_H