定义和操作

需熟练掌握图的定义以及邻接矩阵和邻接表的表示方式，常常在大题中考察。

图的定义

图是由顶点和边组成的非线性数据结构。顶点有时也被称为节点，而边是连接图中任意两个节点的线或弧。更正式地说，图是由一组顶点(V)和一组边(E)组成的。图用G(E, V)表示。

5
1
4
3
5
1
4
3
Undirected Graph
Directed Graph
  • 有向图（directed graph）：边是有方向的，从一个定点指向另一个定点
  • 无向图（undirected graph）：边是没有方向的
5
1
4
3
5
1
4
3
Connected Graph
Unconnected Graph
5
1
4
3
Complete Graph
  • 连通图（Connected Graph）：图中的每一对不同顶点都可以通过一条或多条边相互连接，也就是说，从图中的任意一个顶点出发，都可以到达图中的任意其他顶点。
  • 非连通图（Disconnected Graph）：图中存在两个或多个互不相连的子图，也就是说，其中至少存在一个顶点集合，无法通过边连接到图中的其他顶点集合。
  • 完全图（Complete Graph）：完全图是一种特殊的图，其中每一对不同的顶点都直接相连，也就是说，完全图中的任意两个顶点之间都存在一条边。如果一个完全图有n个顶点，那么它将有 $C(n, 2) = n(n-1)/2$ 条边，其中 $C(n, 2)$ 表示从n个顶点中选择2个顶点的组合数。
A
D
C
Undirected Graph G
E
B
I
J
F
G
H
A
D
C
E
B
I
J
F
G
H
Three Connected Components of G
  • 连通分量（Connected Components）：连通分量（Connected Components），也称为连通子图，是一个无向图中的一个重要概念。一个连通分量是指在无向图中，如果从其中一个顶点出发，可以通过边的路径到达该连通分量内的任何其他顶点，而无法通过图中的边到达其他连通分量内的顶点。
  • 顶点的度（Degree）：顶点的度是指与该顶点相邻的边的数量，也就是与该顶点直接相连的其他顶点的个数。对于有向图和无向图都适用。
    • 在无向图中，顶点的度就是与该顶点相邻的边的数量。
    • 在有向图中，顶点的度分为入度和出度，分别表示指向该顶点的边的数量和从该顶点出发的边的数量的总和。
  • 入度（In-Degree）：入度是指在有向图中指向某个顶点的边的数量，也就是与该顶点关联的边中以该顶点为终点的边的数量。
  • 出度（Out-Degree）：出度是指在有向图中从某个顶点出发的边的数量，也就是与该顶点关联的边中以该顶点为起点的边的数量。

树和图的区别？

树是受限制的图类型，只是有更多的规则。每棵树都是一个图，但不是所有的图都是树。链表、树和堆都是图的特殊情况。

Tree
Graph

表示方式

邻接矩阵（Adjacent Matrix）

图的邻接矩阵（Adjacency Matrix）是一种常用的图表示方法，特别适用于稠密图，它以矩阵的形式表示图的连接关系。在邻接矩阵中，行和列分别代表图的顶点，矩阵的元素表示顶点之间是否相邻或者边的权重。

v2
v4
v3
v1
Directed Graph G(V, E)
0
0
0
1
1
0
0
1
0
1
0
0
0
0
1
0
v1
v2
v3
v4
v1
v2
v3
v4
v2
v4
v3
v1
Undirected Graph G(V, E)
0
1
0
1
1
0
1
1
0
1
0
0
1
1
1
0
v1
v2
v3
v4
v1
v2
v3
v4
v2
v4
v3
v1
Weighted Undirected Graph G(V, E)
0
0.4
0
0.4
0.4
0
0.3
0.1
0
0.3
0
0.5
0.4
0.1
0.5
0
v1
v2
v3
v4
v1
v2
v3
v4
0.4
0.4
0.3
0.5
0.1
  1. 对于无向图：
    • 如果顶点 $i$ 和顶点 $j$ 之间存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $1$ （或者表示边的权重）。
    • 如果顶点 $i$ 和顶点 $j$ 之间不存在边，则邻接矩阵中 $(i, j)$ 和 $(j, i)$ 位置的元素都被标记为 $0$ 。
  2. 对于有向图：
    • 如果有一条从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $1$ （或者表示边的权重）。
    • 如果没有从顶点 $i$ 到顶点 $j$ 的有向边，则邻接矩阵中 $(i, j)$ 位置的元素被标记为 $0$ 。

邻接表

图的邻接表（Adjacency List）是一种常见的图表示方法，特别适用于稀疏图，它使用链表或数组的形式来表示图的连接关系。每个顶点都对应一个链表，链表中存储与该顶点相邻的其他顶点。

邻接表的主要思想是为每个顶点创建一个链表，链表中的每个节点表示与该顶点相邻的另一个顶点。对于无向图，通常需要为每一条边创建两个链表节点，分别表示两个相邻的顶点。

v2
v4
v3
v1
Directed Graph G(V, E)
v2
v4
v3
v1
Undirected Graph G(V, E)
v1
v4
v2
v1
v3
v4
v1
v4
v3
v1
v2
v4
v2
v1
v3
v4
v3
v2
v4
v4
v1
v2
v3

代码实现

#define MAX_VERTICES 100

int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵

void initializeMatrix(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0; // 初始化所有元素为0
        }
    }
}

void addEdge(int start, int end) {
    adjMatrix[start][end] = 1; // 添加边，将对应位置的元素设为1
    adjMatrix[end][start] = 1; // 无向图需要将对称位置的元素也设为1
}
// 邻接表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 图的结构
struct Graph {
    int vertices;
    struct Node** adjacencyList;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->vertices = vertices;
    graph->adjacencyList = (struct Node**)malloc(vertices * sizeof(struct Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjacencyList[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int start, int end) {
    // 添加边到起始顶点的链表
    struct Node* newNode = createNode(end);
    newNode->next = graph->adjacencyList[start];
    graph->adjacencyList[start] = newNode;

    // 对于无向图，需要添加一条反向边
    newNode = createNode(start);
    newNode->next = graph->adjacencyList[end];
    graph->adjacencyList[end] = newNode;
}