系列文章目录
第一章 ❤️ 学前知识
第二章 ❤️ 单向链表
第三章 ❤️ 递归
…
前言
什么是图？
在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
顶点有时也称为节点或者交点，边有时也称为链接
图有各种形状和大小。边可以有权重（weight），即每一条边会被分配一个正数或者负数值。
图的分类
图按照无方向和有方向分为：无向图和有向图。
图按照边分为：稀疏图和稠密图
这是个模糊的概念，同样是相对的概念。
完全图
没有重复的边或者到自身的边（简单图），右图则有
网
这种边带权值的图叫网
顶点与边
顶点与边的关系
- 顶点的度：顶点关联边的数目。有向图图中有，入度：方向指向顶点的边；出度：方向背向顶点的边。在有向图中顶点的度就是两者之和。
- 路径长度：路径上边或者弧的数目。
图的存储结构
理论上，图就是一堆顶点和边对象而已，那我们又如何用代码来实现它呢？
通常我们有两种选择：邻接列表和邻接矩阵。
邻接列表
顶点表的各个结点由data（数据域）和Firstedge（指针域）两个域表示，data是数据域，指针域指向边表的第一个结点，即顶点的第一个邻接点。边表结点由adjvex（邻接点域）和next两个域组成。
邻接点域存储某顶点的邻接点在顶点表中坐标，next存储边表中下一个结点指针。
如图中v1顶点与v2、v0互为邻接点，则在v1边表中，adjvex分别为0和2。
有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表。
#include <stdio.h>
#include <stdlib.h>
// 邻接表中每个节点的结构体
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// 邻接表的结构体
struct AdjList {
struct AdjListNode *head;
};
// 图的结构体
struct Graph {
int V;
struct AdjList* array;
};
// 创建一个新的邻接表节点
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建一个具有V个顶点的新图
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
// 创建邻接表数组
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
// 初始化链表头为空
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// 添加一个边到无向图
void addEdge(struct Graph* graph, int src, int dest) {
// 添加一条从src到dest的边
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// 添加一条从dest到src的边，因为是无向图
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// 打印邻接列表表示的图
void printGraph(struct Graph* graph) {
for (int v = 0; v < graph->V; ++v) {
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n 邻接列表%d: ", v);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main() {
// 创建一个具有5个顶点的新图
struct Graph* graph = createGraph(5);
// 添加边
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
// 打印邻接列表表示的图
printGraph(graph);
return 0;
}
邻接矩阵
邻接矩阵(Adjacency Matrix):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:
#include <stdio.h>
#define MAX_NODES 100
int adj_matrix[MAX_NODES][MAX_NODES];
void add_edge(int start, int end) {
adj_matrix[start][end] = 1;
adj_matrix[end][start] = 1; // 无向图需要将两个方向都标记为已连接
}
int main() {
// 添加边
add_edge(0, 1);
add_edge(0, 2);
add_edge(1, 2);
add_edge(2, 3);
// 输出邻接矩阵
printf("邻接矩阵：\n");
for (int i = 0; i < MAX_NODES; i++) {
for (int j = 0; j < MAX_NODES; j++) {
printf("%d ", adj_matrix[i][j]);
}
printf("\n");
}
return 0;
}