图存储结构详解与C代码实现
- 算法
- 2024-06-02
- 506热度
- 0评论
图是由节点(或称为顶点)和连接这些节点的线(或称为边)组成的。这些节点和边可以有不同的表示方法,从而形成了不同的存储结构。
邻接矩阵
认识邻接矩阵
邻接矩阵就像一个巨大的表格,表的行和列都代表图中的节点。如果节点A和节点B之间有边相连,那么在这个表格中,A行B列(或B行A列,对于无向图来说)的位置上就会标记为1(或者其它表示“有连接”的值)。如果它们之间没有边相连,那么这个位置就标记为0(或其它表示“无连接”的值)。
图 1-28图的邻接矩阵
以图1-28为例,我们来理解图的邻接矩阵。
在无向图中,边是双向的,即如果顶点i与顶点j之间存在一条边,那么从i到j和从j到i都是可达的。因此,在邻接矩阵中,A[i][j]和A[j][i]都会被标记为1,表示这两个顶点之间存在连接。这种表示方式使得我们可以快速判断任意两个顶点之间是否存在边,通过简单地检查对应位置的矩阵元素即可。
对于有向图,情况稍有不同。在有向图中,边是单向的,即存在从顶点i指向顶点j的边并不意味着从j到i也存在边。因此,在邻接矩阵中,我们只在A[i][j]处标记为1,表示存在从i到j的边,而A[j][i]则保持为0或其他默认值,表示不存在从j到i的边。这种表示方式能够准确地反映有向图的特性,使得我们可以轻松地识别出边的方向性。
除了表示图的结构外,邻接矩阵还可以用于表示带权图。在带权图中,每条边都有一个权重,表示两个顶点之间的某种度量或成本。在邻接矩阵中,我们可以将A[i][j]的值设置为边(i, j)的权重,如果i和j之间没有边,则可以将A[i][j]设置为一个特殊值(如无穷大或-1),表示这两个顶点之间不可达。这种表示方式使得我们可以方便地进行基于权重的图算法操作,如最短路径算法等。
邻接矩阵的优点在于其直观性和易于操作性。通过简单的数组索引操作,可以快速访问和修改图的结构信息。此外,邻接矩阵还支持快速的矩阵运算,使得某些图算法(如邻接矩阵的幂运算用于计算可达性)变得简单高效。
邻接矩阵也存在一些缺点。对于稀疏图(即边数相对于顶点数较少的图),邻接矩阵可能会浪费大量的存储空间,因为大部分矩阵元素都是0或默认值。其次,对于大规模的图,邻接矩阵的存储和操作可能会变得非常耗时和内存消耗大。
在选择使用邻接矩阵表示图时,我们需要根据具体的应用场景和需求进行权衡。对于稠密图或需要频繁进行矩阵运算的场景,邻接矩阵可能是一个合适的选择。而对于稀疏图或需要节省存储空间的场景,其他表示方法(如邻接表)可能更为合适。
C语言实现邻接矩阵
下面是一个简单的C语言程序,用于创建和打印图的邻接矩阵表示。
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100 // 定义最大顶点数
// 定义图的邻接矩阵表示
typedef struct {
int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int numVertices; // 顶点数
} Graph;
// 初始化图的邻接矩阵表示
void initializeGraph(Graph *graph, int numVertices) {
graph->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
graph->matrix[i][j] = 0; // 初始化为0,表示没有边相连
}
}
}
// 添加边到图的邻接矩阵表示中
void addEdge(Graph *graph, int from, int to, int weight) {
if (from >= graph->numVertices || to >= graph->numVertices) {
printf("Invalid vertex index!\n");
return;
}
graph->matrix[from][to] = weight; // 设置边的权重
graph->matrix[to][from] = weight; // 对于无向图,需要设置对称位置的权重
}
// 打印图的邻接矩阵表示
void printGraph(Graph *graph) {
for (int i = 0; i < graph->numVertices; i++) {
for (int j = 0; j < graph->numVertices; j++) {
printf("%d ", graph->matrix[i][j]);
}
printf("\n");
}
}
int main() {
Graph graph;
int numVertices, numEdges, from, to, weight;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
initializeGraph(&graph, numVertices);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);
for (int i = 0; i < numEdges; i++) {
printf("Enter edge %d (from, to, weight): ", i + 1);
scanf("%d %d %d", &from, &to, &weight);
addEdge(&graph, from, to, weight);
}
printf("Adjacency matrix:\n");
printGraph(&graph);
return 0;
}
上述程序中,首先定义了一个Graph结构体,用于存储邻接矩阵和顶点数。然后实现了三个函数:initializeGraph用于初始化图的邻接矩阵表示,addEdge用于向图中添加边,并设置相应的权重,printGraph用于打印图的邻接矩阵表示。在main函数中,读取用户输入的顶点数和边数,以及每条边的起点、终点和权重,并使用这些信息创建和打印图的邻接矩阵表示。
领接表
认识邻接表
邻接表是另一种存储图的方式。它对于每个节点都建立一个列表,这个列表里存着和这个节点直接相连的其它节点。这样,我们只需要查看某个节点的列表,就可以知道它连接了哪些节点。
图 1-29图的邻接表
以图1-29为例,我们来理解图的邻接表。
在有向图中,每条边都有明确的起点和终点。邻接表为每个顶点维护了一个链表,链表中存储的是从这个顶点出发可以到达的其他顶点。换句话说,每个顶点对应的链表实际上是一个出边列表,记录了从这个顶点出发的所有边的终点。
这种存储方式非常适合处理有向图的遍历和搜索操作。例如,在深度优先搜索(DFS)或广度优先搜索(BFS)中,可以根据当前顶点的邻接表快速找到所有相邻的顶点,并继续搜索过程。此外,邻接表还可以方便地添加或删除边,因为每个顶点的链表都是独立的,修改一个顶点的邻接表不会影响到其他顶点。
对于无向图来说,邻接表的存储方式也类似。但是由于无向图中每条边都是双向的,因此每个顶点的链表中需要存储与该顶点有边相连的所有顶点。换句话说,无向图的邻接表实际上是双向的,每个顶点的链表既包含了指向它的顶点,也包含了从它出发可以到达的顶点。
虽然无向图的邻接表在表示上稍微复杂一些,但它仍然具有许多优点。与有向图一样,无向图的邻接表也支持高效的遍历和搜索操作。此外,由于邻接表使用了链表来存储边信息,因此它可以有效地处理稀疏图(即边数相对较少的图),避免了使用二维数组等数据结构时可能产生的空间浪费。
C语言实现邻接表
下面是一个简单的C语言实现邻接表的例子。
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中边的结构体
typedef struct Edge {
int dest; // 边的目标顶点
struct Edge* next; // 指向下一条边的指针
} Edge;
// 定义邻接表中顶点的结构体
typedef struct Vertex {
int data; // 顶点的数据
Edge* firstEdge; // 指向第一条边的指针
} Vertex;
// 定义图的结构体
typedef struct Graph {
int numVertices; // 顶点的数量
Vertex* vertices; // 顶点数组
} Graph;
// 创建新的边
Edge* createEdge(int dest) {
Edge* newEdge = (Edge*)malloc(sizeof(Edge));
newEdge->dest = dest;
newEdge->next = NULL;
return newEdge;
}
// 创建新的顶点
Vertex* createVertex(int data) {
Vertex* newVertex = (Vertex*)malloc(sizeof(Vertex));
newVertex->data = data;
newVertex->firstEdge = NULL;
return newVertex;
}
// 创建新的图
Graph* createGraph(int numVertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = numVertices;
graph->vertices = (Vertex*)malloc(numVertices * sizeof(Vertex));
for (int i = 0; i < numVertices; i++) {
graph->vertices[i] = *createVertex(i);
}
return graph;
}
// 在图中添加边
void addEdge(Graph* graph, int src, int dest) {
Edge* newEdge = createEdge(dest);
newEdge->next = graph->vertices[src].firstEdge;
graph->vertices[src].firstEdge = newEdge;
// 如果是无向图,还需要添加反向边
// newEdge = createEdge(src);
// newEdge->next = graph->vertices[dest].firstEdge;
// graph->vertices[dest].firstEdge = newEdge;
}
// 打印图的邻接表表示
void printGraph(Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
printf("Vertex %d: ", graph->vertices[i].data);
Edge* currentEdge = graph->vertices[i].firstEdge;
while (currentEdge != NULL) {
printf("%d ", currentEdge->dest);
currentEdge = currentEdge->next;
}
printf("\n");
}
}
// 释放图的内存
void freeGraph(Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
Edge* currentEdge = graph->vertices[i].firstEdge;
Edge* nextEdge;
while (currentEdge != NULL) {
nextEdge = currentEdge->next;
free(currentEdge);
currentEdge = nextEdge;
}
}
free(graph->vertices);
free(graph);
}
int main() {
// 创建一个包含5个顶点的图
Graph* graph = createGraph(5);
// 添加边
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
// 打印邻接表
printGraph(graph);
// 释放内存
freeGraph(graph);
return 0;
}
示例代码展示了如何使用C语言实现邻接表。createGraph 函数创建一个新的图,createEdge 和 createVertex 函数分别创建新的边和顶点。addEdge 函数用于在图中添加边。printGraph 函数用于打印图的邻接表表示。最后调用freeGraph函数释放内存。
十字链表
认识十字链表
十字链表结合了前面的方法,并加入了对有向图和有向图中边的权值等特殊情况的处理。十字链表可以方便地找到节点的入边和出边。
图 1-30图的十字链表
以图1-30为例,我们来理解图的邻接表。
图1-30是一个有向图,包含A、B、C、D顶点,这些顶点之间存在有向的边,例如A到B、从B到C、从C到D以及可能的反向边或其他边。为了使用十字链表来表示这个有向图,们需要为每个顶点创建一个节点,并在这些节点之间建立相应的链接。
以顶点B为例,可以创建一个包含B信息的节点。然后检查所有从B出发的边。如果B有一条边指向A,那么就需要在B的出边链表中添加一个指向A的节点。同样地,如果B有其他出边,也需要将它们添加到B的出边链表中。类似地,还需要检查所有指向B的边,并在B的入边链表中添加相应的节点。
对于顶点A、C和D,也需要执行相同的操作。最终将得到一个由十字链表表示的有向图,其中每个顶点都与其入弧和出弧相关联。
十字链表在有向图中的应用具有许多优点。它能高效地查找一个顶点的所有入边和出边,这对于许多图算法(如深度优先搜索、广度优先搜索等)来说是非常有用的。由于十字链表采用链式存储结构,它可以灵活地处理稀疏图(即边数相对较少的图),而不会浪费大量的存储空间。
总的来说,选择哪种存储方式主要取决于图的特性和你的需求。如果图很稠密,或者你需要快速判断两个节点是否有边相连,那么邻接矩阵可能更合适。如果图很稀疏,或者你只需要知道每个节点的邻居有哪些,那么邻接表可能更合适。而更复杂的图结构,则可能需要用到十字链表或邻接多重表等更高级的存储方式。
C语言实现十字链表
一个十字链表节点通常包含四个部分:行索引、列索引、值,以及指向同行和同列下一个元素的指针。
下面是一个使用C语言实现的十字链表的基本案例。
#include <stdio.h>
#include <stdlib.h>
// 定义十字链表节点
typedef struct OLNode {
int row; // 行索引
int col; // 列索引
int value; // 元素值
struct OLNode *right; // 同行下一个元素
struct OLNode *down; // 同列下一个元素
} OLNode, *OLink;
// 定义行指针和列指针
typedef struct {
OLink *rhead; // 行头指针数组
OLink *chead; // 列头指针数组
int rows; // 行数
int cols; // 列数
int nums; // 非零元素个数
} CrossList;
// 创建十字链表
CrossList* CreateCrossList(int rows, int cols, int nums) {
CrossList *list = (CrossList*)malloc(sizeof(CrossList));
list->rhead = (OLink*)malloc(rows * sizeof(OLink));
list->chead = (OLink*)malloc(cols * sizeof(OLink));
list->rows = rows;
list->cols = cols;
list->nums = nums;
for (int i = 0; i < rows; i++) {
list->rhead[i] = NULL;
}
for (int j = 0; j < cols; j++) {
list->chead[j] = NULL;
}
return list;
}
// 向十字链表中插入元素
void InsertOL(CrossList *list, int row, int col, int value) {
OLink p, q, s;
// 创建新节点
s = (OLink)malloc(sizeof(OLNode));
s->row = row;
s->col = col;
s->value = value;
s->right = NULL;
s->down = NULL;
// 插入到行链表中
p = list->rhead[row];
if (p == NULL || p->col > col) {
s->right = p;
list->rhead[row] = s;
} else {
while (p->right != NULL && p->right->col < col) {
p = p->right;
}
if (p->col == col) { // 重复元素,不插入
free(s);
return;
}
s->right = p->right;
p->right = s;
}
// 插入到列链表中
q = list->chead[col];
if (q == NULL || q->row > row) {
s->down = q;
list->chead[col] = s;
} else {
while (q->down != NULL && q->down->row < row) {
q = q->down;
}
if (q->row == row) { // 重复元素,不插入
free(s);
return;
}
s->down = q->down;
q->down = s;
}
}
// 主函数,用于测试
int main() {
int rows = 5, cols = 5, nums = 6;
int data[6][3] = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}, {1, 5, 5}, {5, 1, 6}};
CrossList *list = CreateCrossList(rows, cols, nums);
for (int i = 0; i < nums; i++) {
InsertOL(list, data[i][0] - 1, data[i][1] - 1, data[i][2]);
}
// TODO: 实现十字链表的遍历、查找、删除等操作
return 0;
}
这个示例代码展示了如何创建十字链表以及向其中插入元素。在实际应用中,可能还需要实现遍历、查找、删除。