前面我们介绍了图的一些基本概念，我们接着来看如何在程序中对图结构进行表示，这一部分可能会涉及到某些在《线性代数》这门课程中出现的概念。

邻接矩阵

有向图邻接矩阵

邻接矩阵实际上就是用矩阵去表示图中各顶点之间的邻接关系和权值。假设有一个图 $G=(V,E)$，其中有N个顶点，那么我们就可以使用一个N×N的矩阵来表示，比如下面有A、B、C、D四个顶点的图：
示意图
此时我们需要使用邻接矩阵来表示它，就像下面这样：
示意图
对于一个不带权值的图来说：

$$G_{ij} = \begin{cases} 1, & \text{无向图的 } (v_i, v_j) \text{ 或有向图的 } <v_i, v_j> \text{ 是图中的边} \\ 0, & \text{无向图的 } (v_i, v_j) \text{ 或有向图的 } <v_i, v_j> \text{ 不是图中的边} \end{cases} $$

对于一个带权值的图来说，如果有边，则直接填写对应边的权值，如果没有，那么就填写0或是∞（因为某些图会认为0也是权值，所以说可以用∞，它可以是一个计算机允许的最大值大于所有边的权值的数）来进行表示：

$$G_{ij} = \begin{cases} w_{ij}, & \text{无向图的 } (v_i, v_j) \text{ 或有向图的 } <v_i, v_j> \text{ 是图中的边} \\ 0 \text{ 或 } \infty, & \text{无向图的 } (v_i, v_j) \text{ 或有向图的 } <v_i, v_j> \text{ 不是图中的边} \end{cases} $$

所以说，对于上面的有向图，我们应该像这样填写：
示意图

无向图邻接矩阵

那么我们来看看无向图的邻接矩阵呢？比如下面的这个图：
示意图
对于无向图来说，一条边两边是相互连接的，所以说，A连接B，那么B也连接A，所以说就像这样：
示意图
所以说无向图的邻接矩阵必定是一个对称矩阵。

性质

我们可以来总结一下性质：

  • 无向图的邻接矩阵一定是一个对称矩阵，因此，有时为了节省时间，我们可以只存放上半部分。
  • 对于无向图，邻接矩阵的第i行非0（或非∞）的个数就是第i个顶点的度。
  • 对于有向图，邻接矩阵的第i行非0（或非∞）的个数就是第i个顶点的出度（纵向就是入度了）

代码实现

结构体定义

首先我们需要对结构体进行一下定义，这里我们以有向图为例：

1
2
3
4
5
6
7
8
9
10
#define MaxVertex 5

typedef char E;   //顶点存放的数据类型，这个不用我多说了吧

typedef struct MatrixGraph {
    int vertexCount;   //顶点数
    int edgeCount;     //边数
    int matrix[MaxVertex][MaxVertex];   //邻接矩阵
    E data[MaxVertex];    //各个顶点对应的数据
} * Graph;

接着我们可以对其进行一下初始化创建后返回：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Graph create(){   //创建时，我们可以指定图中初始有多少个结点
    Graph graph = malloc(sizeof(struct MatrixGraph));
    graph->vertexCount = 0;    //顶点和边数肯定一开始是0
    graph->edgeCount = 0;
    for (int i = 0; i < MaxVertex; ++i)    //记得把矩阵每个位置都置为0
        for (int j = 0; j < MaxVertex; ++j)
            graph->matrix[i][j] = 0;
    return graph;
}

int main(){
    Graph graph = create();   //这里咱们就搞一个
    
}

添加操作

接着我们就可以编写一下添加顶点和添加边的函数了：

1
2
3
4
5
6
7
8
9
10
11
void addVertex(Graph graph, E element){   //添加顶点
    if(graph->vertexCount >= MaxVertex) return;
    graph->data[graph->vertexCount++] = element;   //添加新元素
}

void addEdge(Graph graph, int a, int b){   //添加几号顶点到几号顶点的边
    if(graph->matrix[a][b] == 0) {
        graph->matrix[a][b] = 1;  //注意如果是无向图的话，需要[a][b]和[b][a]都置为1
        graph->edgeCount++;
    }
}

案例

我们来尝试构建一下这个有向图：
示意图

1
2
3
4
5
6
7
8
Graph graph = create();
for (int c = 'A'; c <= 'D' ; ++c) 
    addVertex(graph, (char) c);
addEdge(graph, 0, 1);   //A -> B
addEdge(graph, 1, 2);   //B -> C
addEdge(graph, 2, 3);   //C -> D
addEdge(graph, 3, 0);   //D -> A
addEdge(graph, 2, 0);   //C -> A

接着我们打印此领接矩阵，看看是否变成了我们预想中的那样：

1
2
3
4
5
6
7
8
9
10
11
12
13
void printGraph(Graph graph){
    for (int i = -1; i < graph->vertexCount; ++i) {
        for (int j = -1; j < graph->vertexCount; ++j) {
            if(j == -1)
                printf("%c", 'A' + i);
            else if(i == -1)
                printf("%3c", 'A' + j);
            else
                printf("%3d", graph->matrix[i][j]);
        }
        putchar('\n');
    }
}

最后得到：
答案
可以看到结果跟我们上面推导得出的邻接矩阵一模一样，当然这里仅仅是演示了普通的有向图，我们也可以稍微将代码进行修改，将其变成一个无向图或是带权有向图

邻接表

什么是邻接表

前面我们介绍了领接矩阵，我们可以使用邻接矩阵在程序中保存一个图的边相关信息，它采用二维数组的形式，将对应边的连接关系进行存储，但是我们知道，数组存在容量上的局限性（学了这么多节课了，应该能体会到，数组需要一段连续空间，无论是申请还是用起来都很麻烦）同时，我们创建邻接矩阵后，如果图的边数较多（稠密图）利用率还是挺高的，但是一旦遇到边数很少的图（稀疏图）那么表中大量的位置实际上都是0，根本没有被利用起来，是很浪费的。

此时，我们可以考虑使用链式结构来解决这种问题，就像下面这样：
示意图
对于图中的每个顶点，建立一个数组，存放一个头结点，我们将与其邻接的顶点，通过一个链表进行记录（看着挺像前面讲的哈希表）这样，也可以表示一个图的连接关系，并且内存空间能够得到更加有效的利用。当然，对于无向图来说，跟之前一样，两边都需要进行保存：
示意图

代码操作

初始化

我们来尝试编写一下代码实现，首先还是定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define MaxVertex 5

typedef char E;

typedef struct Node {   //结点和头结点分开定义，普通结点记录邻接顶点信息
    int nextVertex;
    struct Node * next;
} * Node;

struct HeadNode {   //头结点记录元素
    E element;
    struct Node * next;
};

typedef struct AdjacencyGraph {
    int vertexCount;   //顶点数
    int edgeCount;     //边数
    struct HeadNode vertex[MaxVertex];
} * Graph;

接着是对其进行初始化：

1
2
3
4
5
Graph create(){   //创建时，我们可以指定图中初始有多少个结点
    Graph graph = malloc(sizeof(struct AdjacencyGraph));
    graph->vertexCount = graph->edgeCount = 0;
    return 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
void addVertex(Graph graph, E element){
    if(graph->vertexCount >= MaxVertex) return;   //跟之前一样
    graph->vertex[graph->vertexCount].element = element;   //添加新结点时，再来修改也行
    graph->vertex[graph->vertexCount].next = NULL;
  	graph->vertexCount++;
}

void addEdge(Graph graph, int a, int b){
    Node node = graph->vertex[a].next;
    Node newNode = malloc(sizeof(struct Node));
    newNode->next = NULL;
    newNode->nextVertex = b;
    if(!node) {    //如果头结点下一个都没有，那么直接连上去
        graph->vertex[a].next = newNode;
    } else {   //否则说明当前顶点已经连接了至少一个其他顶点了，有可能会出现已经连接过的情况，所以说要特别处理一下
        do {
            if(node->nextVertex == b) return;   //如果已经连接了对应的顶点，那么直接返回
            if(node->next) node = node->next;   //否则继续向后遍历
            else break;   //如果没有下一个了，那就找到最后一个结点了，直接结束
        } while (1);
        node->next = newNode;
    }
  	graph->edgeCount++;   //边数计数+1
}

案例

我们来将其构建一下吧，还是以上面的图为例：
示意图

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
    Graph graph = create();
    for (int c = 'A'; c <= 'D' ; ++c)
        addVertex(graph, (char) c);
    addEdge(graph, 0, 1);   //A -> B
    addEdge(graph, 1, 2);   //B -> C
    addEdge(graph, 2, 3);   //C -> D
    addEdge(graph, 3, 0);   //D -> A
    addEdge(graph, 2, 0);   //C -> A

    printGraph(graph);
}

我们来打印看看效果：

1
2
3
4
5
6
7
8
9
10
11
void printGraph(Graph graph){
    for (int i = 0; i < graph->vertexCount; ++i) {
        printf("%d | %c", i, graph->vertex[i].element);
        Node node = graph->vertex[i].next;
        while (node) {
            printf(" -> %d", node->nextVertex);
            node = node->next;
        }
        putchar('\n');
    }
}

得到结果如下：
答案

逆邻接表

虽然邻接表的方式看上去更加的简单高效，但是会给我们带来一些不必要的麻烦，比如上面创建的领接表，我们只能快速得到某个顶点指向了哪些顶点，也就是只能计算到顶点的出度，但是无法快速计算顶点的入度，只能将所有结点统计之后才能得到入度。所以说在表示有向图时，查找上并没有邻接矩阵来的方便。

为了解决这种问题，我们可以建立一个逆领接表，来表示所有指向当前顶点的顶点列表：
示意图
实际上就是反着来而已，通过建立这两个领接表，就能在一定程度上缓解不方便的情况。

说些什么吧！

twikoo