【数据结构】图基本概念

在计算机科学中，图（Graph）是一种非常重要的数据结构，用于描述各种复杂的关系和网络。本文将介绍图的基本概念，并通过C语言代码演示如何实现基本的图结构和相关操作。

图的基本概念：

图由节点（Vertex）和边（Edge）组成。节点表示图中的对象，边表示节点之间的关系。图可以分为有向图和无向图，区别在于边是否有方向性。

1. 顶点（Vertex）： 图中的节点，也称为顶点。每个顶点可能携带有关信息，如标签或权重。
2. 边（Edge）： 两个顶点之间的连接。如果边是有向的，则有一个起始顶点和一个终止顶点。如果是无向的，则两个顶点之间没有方向。
3. 路径（Path）： 由顶点和边构成的序列，表示从一个顶点到另一个顶点的连续路径。
4. 环（Cycle）： 如果路径的起点和终点是同一个顶点，则称该路径为环。

图的表示方法：

图可以用不同的方式表示，最常见的两种是邻接矩阵和邻接表。

1. 邻接矩阵（Adjacency Matrix）： 使用二维数组来表示图中的节点和边的关系。如果顶点 i 和顶点 j 之间有边相连，则矩阵中 (i, j) 和 (j, i) 的位置为 1，否则为 0。

2. 邻接表（Adjacency List）： 使用链表数组来表示图中的节点和边的关系。每个顶点都有一个链表，存储与其相连的所有顶点。

下面我们通过C语言来实现一个简单的邻接表表示的无向图，并实现一些基本操作：

#include <stdio.h>
#include <stdlib.h>

// 定义图的最大顶点数
#define MAX_VERTICES 100

// 定义邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 定义图结构
typedef struct Graph {
    int numVertices;
    Node* adjList[MAX_VERTICES];
} Graph;

// 初始化图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        graph->adjList[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

// 打印图的邻接表
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        Node* temp = graph->adjList[v];
        printf("顶点 %d 的邻接表：", v);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    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, 3, 4);
    printGraph(graph);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

在上述代码中，我们首先定义了一个结构体 Node 来表示邻接表中的节点，然后定义了一个 Graph 结构体来表示图。接着，我们实现了 createGraph 函数用于创建图，addEdge 函数用于添加边，以及 printGraph 函数用于打印图的邻接表。

通过上述C语言代码的实现，我们可以更深入地理解图这种数据结构的基本概念和表示方法，以及如何在程序中实现图的基本操作。