1
// 创建图邻接矩阵
2
/*
3
g：初始矩阵
4
arr：n%3=0表示起点，n%3=1表示终点，n%3=2表示权值
5
arrLen：表示arr的长度
6
haveDi：0 表示无向，非0 表示有向
7
*/
8
void graph_createAdjacencyMatrixByArrWithWeight(int **g, int* arr, int arrLen, int haveDi)
9
{
10
    for(int i = 0; i < arrLen; i += 3)
11
    {
12
        g[arr[i]][arr[i+1]] = arr[i+2];
13
        if(!haveDi)
14
        {
15
            g[arr[i+1]][arr[i]] = arr[i+2];
16
        }
17
    }
18
}
19

20
// 创建nxn的二维数组，并全部初始化为value
21
int** graph_createArrInValue(int n, int value)
22
{
23
    int **arr = (int **)malloc(sizeof(int *) * n);
24
    for(int i = 0; i < n; i ++)
25
    {
26
        arr[i] = (int *)malloc(sizeof(int) * n);
27
        for(int j = 0; j < n; j ++)
28
        {
29
            arr[i][j] = value;
30
        }
31
    }
32
    return arr;
33
}
34

35
// 打印矩阵
36
/*
37
g：表示邻接矩阵
38
n：表示结点个数
39
*/
40
void graph_print(int **g, int n, char* pattern)
41
{
42
    for(int i = 0; i < n; i ++)
43
    {
44
        for(int j = 0; j < n; j++)
45
        {
46
            printf(pattern, g[i][j]);
47
        }
48
        printf("\n");
49

50
    }
51
}

1
// 边结点
2
typedef struct
3
{
4
    int adjvex; // 另一个结点的索引
5
    struct ArcNode* nextarc; // 下一个边结点
6
    int value; // 权值
7
}ArcNode;
8

9
// 头节点
10
typedef struct
11
{
12
    struct ArcNode* firstarc; // 第一个边结点
13
}VertexNode;
14

15
// 创建边结点
16
ArcNode* graph_list_createArcNode(int adjvex, int value)
17
{
18
    ArcNode* node = (ArcNode*)malloc(sizeof(ArcNode));
19
    node->nextarc = NULL;
20
    node->adjvex = adjvex;
21
    node->value = value;
22
    return node;
23
}
24

25
// 创建头节点
26
VertexNode* graph_list_createVertexNode()
27
{
28
    VertexNode* node = (VertexNode* )malloc(sizeof(VertexNode));
29
    node->firstarc = NULL;
30
    return node;
31
}
32

33
// 创建头节点数组
34
VertexNode* graph_list_VerArr(int n)
35
{
36
    VertexNode** arr = (VertexNode** )malloc(sizeof(VertexNode*) * n);
37
    for(int i = 0; i < n; i ++)
38
    {
39
        arr[i] = graph_list_createVertexNode();
40
    }
41
    return arr;
42
}
43

44

45
// 向头节点后添加边结点
46
void graph_list_addArc(VertexNode* ver, ArcNode* arc)
47
{
48
    arc->nextarc = ver->firstarc;
49
    ver->firstarc = arc;
50
}
51

52
// 创建无向图邻接表
53
/*
54
vers：头节点数组
55
arr：n%3=0表示起点，n%3=1表示终点，n%3=2表示权值
56
arrLen：表示arr的长度
57
haveDi：0 表示无向，非0 表示有向
58
*/
59
void graph_list_createAdjacencyMatrixByArrWithWeight(VertexNode** vers, int* arr, int arrLen, int haveDi)
60
{
61
    for(int i = 0; i < arrLen; i += 3)
62
    {
63
        graph_list_addArc(vers[arr[i]], graph_list_createArcNode(arr[i+1], arr[i+2]));
64
        if(!haveDi)
65
        {
66
            graph_list_addArc(vers[arr[i+1]], graph_list_createArcNode(arr[i], arr[i+2]));
67
        }
68
    }
69
}
70

71
// 打印邻接表
72
void graph_list_print(VertexNode** vers, int len, char* pattern_ver, char* pattern_arc)
73
{
74
    for(int i = 0; i < len; i ++)
75
    {
76
        ArcNode* arc = vers[i]->firstarc;
77
        printf(pattern_ver, i);
78
        while(arc)
79
        {
80
            printf(pattern_arc, arc->adjvex, arc->value);
81
            arc = arc->nextarc;
82
        }
83
        printf("\n");
84
    }
85
}