图论是数据结构与算法中必须逾越的一座大山，适用范围非常广泛，当然也具有一定的难度，本人也是今年第一次学习图论的知识点，不能说掌握的很好，但我会尽可能的把我学会的知识点分享给大家，在写这篇博客之前我也查阅了很多大牛的图论分享，也算基本上涵盖了图论的重要知识点，如有错误还望各路大神斧正。另外以下程序都是由
C语言
编写的，海域。
首先我们简单认识一下图论，我举一个最简单的例子，就是我们常用的百度或者高德地图，我们在导航时，背后的本质就是图论的各种算法，例如是否有通路可以抵达，或者最短路径是哪条线路等，所以图论的应用是非常广泛的，包括全市公交线路，如何帮我我们快速找到最快抵达的路线，这都是图论的功劳。另外值得注意的是，在计算图论的复杂度的时候，我们不再用n进行计算了，而是要以图的顶点个数V和边的个数E进行计算。那么接下来我们就开始正式讲解。
图论主要有三种表现形式，分别是边的数组（Array of edges），临接矩阵（Adjacency matrix）和临接链表（Adjacency list）。其中临接矩阵是最好理解，也是大家一定要掌握的，而我个人比较喜欢临接链表，三种形式主要是数据储存的方式不同，但背后的理论是相似的，学会一个另外的都会变得很好理解。当然这三种我都会给大家一一介绍的，各位看官可以根据自己的需求选择相应的方法。
1. Array-of-edges
边的数组主要是以数组的形式去储存顶点和边的信息，具体说应该是二维数组。具体的程序细节都在注释里面，大家可以结合代码去理解。
typedef int Vertex;
typedef struct Edge* edge;
struct Edge {
Vertex v; // 每条边的起点编号
Vertex w; // 每条边的终点编号
};
typedef struct graph* Graph;
struct graph {
edge **edges; //指向结构体指针的指针
int numberOfV; //顶点的个数
int numberOfE; //边的个数
};
graph* newGraph(int numberOfV) { //创建一个新的图
graph* newGraph = malloc(sizeof (struct graph));
newGraph->edges = malloc(sizeof (edge*) * 100); //构建二维数组（这是二维数组的第一层，定义大小）
//初始化顶点和边的数量，边的数量要根据插入函数来决定
newGraph->numberOfE = 0;
newGraph->numberOfV = numberOfV;
return newGraph;
}
//添加一条边
void append_edge(graph *g, int v, int w){ // 输入每条边起点和终点的编号
edge *newEdge = malloc(sizeof (struct Edge));
newEdge->v = v;
newEdge->w = w;
g->edges[g->numberOfE] = newEdge; //由创建街道可知，Graph->edges是一个可以存储100个边的数组，这一步的意思是从第0个开始存储边,起点和终点都同时存入了
g->numberOfE++;
}
void showGraph (graph* g){
printf("number of vertex: %d\n", g->numberOfV);
printf("number of edges: %d\n", g->numberOfE);
for (int i = 0; i < g->numberOfE; i++) {
printf("edge[%d] v:%d - w:%d\n", i+1, g->edges[i]->v, g->edges[i]->w);
}
}
void freeGraph(graph* g){
for (int i = 0; i < g->numberOfE; i++)
free(g->edges[i]);
free(g->edges);
free(g);
}
int main(void){
graph *g = newGraph(6);
append_edge(g, 1, 2);
append_edge(g, 1, 3);
append_edge(g, 1, 4);
showGraph(g);
freeGraph(g);
}2. Adjacency matrix
矩阵相信大家都不陌生了，矩阵可以非常简单的让我们画出一个图，具体操作其实很简单，就是两个点若没有边则填0，若有边则填1.本质上也是二维数组，但是边的数组是有边才输入顶点编号，而矩阵是所有顶点都要写出来，然后两两不断的做对比。
//插入/删除一条边的算法法度是O(1)，直接找到改为1/0即可，查找是O(E)
//创建（初始化，存储）一个矩阵的算法法度是O(v^2),
typedef int Vertex;
typedef struct edge { //类似于一个房屋
Vertex v; // 每条边的起点编号
Vertex w; // 每条边的终点编号
}Edge;
typedef struct graph{ //类似于一个街道
int **matrix; //定义为二维数组
int number_of_v; //顶点的数量
int number_of_e; //边的数量
}Graph;
Graph *new_graph(int number_of_v){ //创建一个矩阵并将其初始化
Graph *new_graph = malloc(sizeof(struct graph));
new_graph->matrix = malloc(sizeof (int *) * number_of_v);
for (int i = 0; i < number_of_v; i++) { //二维数组的初始化和赋值必须用两个for循环
new_graph->matrix[i] = malloc(sizeof (int) * number_of_v); //这两个malloc就是建立矩阵的过程。00，01，02...53, 54, 55
for (int j = 0; j < number_of_v; j++) {
new_graph->matrix[i][j] = 0; //给每个点进行初始化，默认都是0，构成一个5*5的矩阵
}
}
new_graph->number_of_e = 0;
new_graph->number_of_v = number_of_v;
return new_graph;
}
void insert_edge(Graph* g, Edge e){
g->matrix[e.v][e.w] = 1;
g->matrix[e.w][e.v] = 1; //这一步是考虑了无向图，若是有向图则不用加
g->number_of_e++;
}
void showGraph(Graph* g){
printf("number of vertices: %d\n", g->number_of_v);
printf("number of edges: %d\n", g->number_of_e);
for (Vertex i = 0; i < g->number_of_v; i++) {
for (Vertex j = 0; j < g->number_of_v; j++) {
if (g->matrix[i][j] == 1){
printf("edge v:%d - w:%d\n", i, j);
}
}
}
}
void freeGraph(Graph* g){
for (int i = 0; i < g->number_of_v; i++) {
free(g->matrix[i]);
}
free(g->matrix);
free(g);
}3. Adjacency linked list
临接链表要略微复杂一点，它储存数据的原理是，先建立一个链表用于储存顶点的信息。若两个顶点之间有边，则在该顶点的node下插入相应编号的子节点。如下图所示：
接下来我就用临接链表的方式来做一个综合练习，以讲解图论的相关操作。具体操作内容有以下13个：
1.图的建立
2.图的消除
3.图的展示
但注意show的形式是：
vertex1 vertex2 vertex3 ... vertexN vertex1 vertex2 weight vertex2 vertex4 weight vertexN vertex4 weight
4.增加一个顶点
5.是否有目标顶点
6.删除一个目标顶点
7.返回顶点个数
8.判断两个点之间是否有边
9.删除一条边
10.改变目标边的权重
11.显示目标边的权重
12.返回边的个数
13.插入一条边
首先是结构体的建立，这里比起一般的链表多了第三个结构体,专门用于方便链表的综合操作（母子节点操作）：
typedef char* string
typedef struct house* Node;
typedef struct linked_list* List;
typedef struct Graph_Repr* g;
struct house{ //普通节点
string data;
size_t weight;
Node next;
Node prev;
List children; //子节点
};
struct linked_list{ //一条链表
Node head;
Node tail;
int length; //记录链表长度
};
struct Graph_Repr{
List vertex; //代表每个顶点，每个顶点上还有子节点，子节点的编号就是边
};
在进行实际操作前要提前写好节点建立和链表建立这两个操作函数，这都是最基本的链表操作，就不过多解释了，如果看不懂可以看一下我之前写的单双链表的讲解：
Node create_node(string data){
Node new_node = malloc(sizeof(struct house));
new_node->data = malloc(sizeof(char) * (strlen(data) + 1));
strcpy(new_node->data, data);
new_node->data[strlen(data)] = '\0'; //强制加终止字符，避免不必要的bug
new_node->next = new_node->prev = NULL;
new_node->children = NULL;
new_node->weight = 0;
return new_node;
}
List g_list_create (void) {
List new_list = malloc(sizeof(struct linked_list));
new_list->tail = new_list->head = NULL;
new_list->length = 0;
return new_list;
}
现在正式开始操作讲解，首先是
图的建立和destroy
graph graph_create (void){
g new_graph = malloc(sizeof(struct Graph_Repr));
new_graph->vertex = g_list_create();
new_graph->vertex->head =new_graph->vertex->tail = NULL; //再次强调必须要初始化
return new_graph;
}
void graph_destroy (graph G){
Node temp = G->vertex->head;
Node next;
while (temp != NULL) {
next = temp->next;
free(temp->data);
free(temp);
temp = next;
}
free(G->vertex);
free(G);
}
首先是顶点的相关操作
增加一个顶点：
在这相信大家就能理解刚刚多建立的第三个结构体的作用了，它是指向链表结构体的指针，帮助我们在使用临接链表时定位不同的顶点，也可以方便我们在后续添加子节点。
void graph_add_vertex (graph G, string vertex){
if (G->vertex->head == NULL) {
G->vertex = g_list_create(); //在vertex里初始化一个链表空间
G->vertex->head = G->vertex->tail = create_node(vertex);
} else {
Node new_v = create_node(vertex);
G->vertex->tail->next = new_v;
new_v->prev = G->vertex->tail;
G->vertex->tail = new_v;
}
G->vertex->length++;
}
判断是否有目标顶点：
很简单，就是用strcmp函数，之前在链表的讲解也有介绍过，就不过多赘述了。
bool graph_has_vertex (graph G, string vertex) {
bool result = false;
Node temp = G->vertex->head;
while (temp != NULL) {
if (strcmp(vertex, temp->data) == 0) {
result = true;
}
temp = temp->next;
}
return result;
}
删除目标链表：
虽然感觉很简单，但这个函数要复杂一点，因为要考虑四种可能的情况：只有一个节点，且是目标节点，头是目标节点，尾是目标节点以及中间是目标节点。其实本质上和双链表的操作是一样的，所以大家一定要掌握好链表和指针的基础知识。
void graph_remove_vertex (graph G, string vertex) {
if (graph_has_vertex(G, vertex) == true) {
if (G->vertex->head == G->vertex->tail) { //只有一个节点
G->vertex->length--;
G->vertex->head = G->vertex->tail = NULL;
free(G->vertex->tail->data);
free(G->vertex->tail);
} else if (strcmp(vertex, G->vertex->tail->data) == 0) { //删尾节点
Node delete_node = G->vertex->tail;
G->vertex->length--;
G->vertex->tail->prev->next = NULL;
G->vertex->tail = G->vertex->tail->prev;
free(delete_node->data);
free(delete_node);
} else if (strcmp(vertex, G->vertex->head->data) == 0) { //删头节点
Node delete_node = G->vertex->head;
G->vertex->length--;
G->vertex->head->next->prev = NULL;
G->vertex->head = G->vertex->head->next;
free(delete_node->data);
free(delete_node);
} else { //删除的是中间节点
Node temp = G->vertex->head;
G->vertex->length--;
while (temp != NULL) {
if (strcmp(vertex, temp->data) == 0) {
break;
}
temp = temp->next;
}
temp->next->prev = temp->prev;
temp->prev->next = temp->next;
free(temp->data);
free(temp);
}
}
}
返回顶点的个数：
记得要先用if判断链表不为空，且有节点，不然遇到这样的特殊case程序会报错。
size_t graph_vertices_count (graph G) {
size_t result = 0;
if (G->vertex != NULL && G->vertex->head != NULL) {
result = G->vertex->length;
}
return result;
}
接下来都是边的操作
首先是3个工具函数的封装，这样写出来的具体操作更整洁
1.
找到目标vertex并返回其结果（值）：
Node find_parent (graph G, string vertex) {
Node result = NULL;
if (G->vertex != NULL && G->vertex->head != NULL) {
Node temp = G->vertex->head;
while (temp != NULL) {
if (strcmp(vertex, temp->data) == 0) { // 找到目标parent
result = temp;
break;
}
temp = temp->next;
}
}
return result;
}
2.在目标母节点下找到目标子节点并返回其结果：
Node find_child (graph G, string vertex1, string vertex2) {
Node result = NULL;
Node target_parent = find_parent(G, vertex1); //找到目标母节点
Node temp = target_parent->children->head; //定位到目标母节点子链表的head
while (temp != NULL) {
if (strcmp(vertex2, temp->data) == 0) { //判断是否是目标子节点
result = temp;
break;
}
temp = temp->next;
}
return result;
}
3.边的插入：
void edge_insert(List child, string vertex, size_t weight) {
if (child->head == NULL) {
child->head = child->tail = create_node(vertex);
child->head->weight = weight;
} else {
Node new_node = create_node(vertex);
new_node->weight = weight;
child->tail->next = new_node;
new_node->prev= child->tail;
child->tail = new_node;
}
child->length++; //不要忘了这一步，方便记录总的边数
}
接下来开始正式操作。
添加一条边：
void graph_add_edge (graph G, string vertex1, string vertex2, size_t weight) {
Node temp = find_parent(G, vertex1);//先找到目标母节点
Node need_insert_v = find_parent(G, vertex2); //待插入的字节点
if (temp != NULL && need_insert_v != NULL && G->vertex != NULL && G->vertex->head != NULL) {
if (temp->children == NULL) { //这一步不能忘，如果是空的要先开辟一个子链表的空间
temp->children = g_list_create();
}
edge_insert(temp->children, vertex2, weight);//用刚刚写的函数进行插入
}
}
判断两个点之间是否有边：
bool graph_has_edge (graph G, string vertex1, string vertex2) {
bool result = false;
Node target_parent = find_parent(G, vertex1);
if (target_parent != NULL && target_parent->children != NULL && target_parent->children->head != NULL) {
Node target_child = target_parent->children->head;
while (target_child != NULL) {
if (strcmp(vertex2, target_child->data) == 0) {
result = true;
}
target_child = target_child->next;
}
}
return result;
}
删除特定的一条边：
同样的要考虑四种情况，看上去复杂，其实还是很好理解的。
size_t graph_remove_edge (graph G, string vertex1, string vertex2) {
size_t result = 0;
if (graph_has_edge(G, vertex1, vertex2) == true) {
Node target_parent = find_parent(G, vertex1);
if (target_parent->children->head == target_parent->children->tail) { //只有一个节点
target_parent->children->length--;
target_parent->children->head = target_parent->children->tail = NULL;
result = target_parent->children->head->weight;
free(target_parent->children->head->data);
free(target_parent->children->head);
} else if (strcmp(vertex2, target_parent->children->tail->data) == 0) { //删除的是尾节点
Node delete_node = target_parent->children->tail;
target_parent->children->length--;
target_parent->children->tail->prev->next = NULL;
target_parent->children->tail = delete_node->prev;
result = delete_node->weight;
free(delete_node->data);
free(delete_node);
} else if (strcmp(vertex2, target_parent->children->head->data) == 0) { //删除的是头节点
target_parent->children->length--;
Node delete_node = target_parent->children->head;
target_parent->children->head->next->prev = NULL;
target_parent->children->head = delete_node->next;
result = delete_node->weight;
free(delete_node->data);
free(delete_node);
} else { //删除的是中间节点
Node temp = find_child(G, vertex1, vertex2);
temp->next->prev = temp->prev;
temp->prev->next = temp->next;
result = temp->weight;
free(temp->data);
free(temp);
}
}
return result;
}
改变某一条边的权重：
void graph_set_edge (graph G, string vertex1, string vertex2, size_t weight) {
if (graph_has_edge(G, vertex1, vertex2) == true) {
Node target_child = find_child(G, vertex1, vertex2);
target_child->weight = weight;
}
}
返回某一条边的权重：
size_t graph_get_edge (graph G, string vertex1, string vertex2) {
size_t result = 0;
if (graph_has_edge(G, vertex1, vertex2) == true) {
Node target_child = find_child(G, vertex1, vertex2);
result = target_child->weight;
}
return result;
}
返回边的数量：
size_t graph_edges_count (graph G, string vertex) {
size_t result = 0;
Node find_vertex = find_parent(G, vertex);
if (find_vertex != NULL && find_vertex->children != NULL && find_vertex->children->head) {
result = find_vertex->children->length;
}
return result;
}
以上所有就是图论的一些基本操作，欢迎大家在评论区讨论，接下来几天我会找时间总结关于图的最短路径、是否有通路等重要算法，希望大家多多支持！