### 图论模型及其算法
图论是离散数学的一个分支，主要研究图形的性质和结构。在信息学竞赛中，图论算法占据了重要的地位。曹立国老师的这份资料重点介绍了图论的基本概念、数据结构存储方式及一些常用的图论算法。
#### 图结构基本概念
- **图**：由一组点（顶点）和一组连接这些点的线（边）组成的数据结构。
- **点（顶点）**：图中的基本单位，可以代表各种实体。
- **边**：连接两点的线，表示两点之间的关系或路径。
- **图的相关概念**：
- **边的权**：边上的数值，用于表示边的某种属性，如距离、成本等。
- **点的度**：对于无向图来说，一个顶点的度是指与其相连的边的数量；对于有向图，则分为出度（出边数量）和入度（入边数量）。
#### 图的存储结构
- **矩阵**：使用二维数组来表示图。对于无向图，矩阵是对称的；对于有向图，则不一定对称。适合于稠密图。
- **邻接表**：一种链式存储方法，用于表示图。对于每个顶点，都维护一个链表来存储与该顶点相邻的所有顶点。适用于稀疏图。
- **邻接表示例**：
```
1 -> (5) -> (4) -> (3) -> null
2 -> (5) -> (1) -> null
3 -> (2) -> null
4 -> null
5 -> null
```
- **邻接多重表**：在邻接表的基础上增加了更多的信息，可以用来存储边的额外信息，如边的权值等。
- **十字链表**：适用于平面图，可以有效地表示图中的边和面。
#### 邻接表的实现
- **使用指针实现邻接表**：
- **Pascal语言**：
```pascal
type Tnode = record
c: integer; // 顶点编号
next: ^Tnode; // 此点的邻接链表
end;
procedure ins(x: integer; var p: Tnode);
begin
new(t); t^.c := x;
t^.next := p.next;
p.next := t;
end;
```
- **C++语言**：
```cpp
#include <iostream>
struct Tnode {
int c; // 顶点编号
Tnode* next; // 此点的邻接链表
};
void ins(int x, Tnode& p)
{
Tnode* t = new Tnode; t->c = x;
t->next = p.next;
p.next = t;
}
```
- **使用数组实现邻接表**：
- **Pascal语言**：
```pascal
const maxV = 1000; // 最多顶点数
maxE = 10000; // 最多边数
type Tnode = record
c: integer; // 节点编号
next: integer; // 此节点的邻接链表
end;
var
e: array[1..maxE] of Tnode;
g: array[1..maxV] of Tnode;
n, m, efree, i, a, b, t: integer;
procedure ins(x: integer; var p: Tnode);
begin
e[efree].c := x; e[efree].next := p.next;
p.next := efree;
efree := efree + 1; // 新空元素下标
end;
```
- **C++语言**：
```cpp
const int maxV = 1000, // 最多顶点数
maxE = 10000; // 最多边数
struct Tnode {
int c; // 顶点编号
int next; // 此点的邻接链表
};
void ins(int x, Tnode& p)
{
e[efree].c = x;
e[efree].next = p.next;
p.next = efree;
efree++; // 新空元素下标
}
```
### 贪心算法
贪心算法是一种在每一步选择中都采取当前看起来最好的选择的策略，希望通过这种局部最优的选择达到全局最优解的目的。贪心算法并不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
#### 应用场景
- 在图论中，贪心算法经常被用来解决最短路径问题、最小生成树等问题。
- 最典型的例子之一就是克鲁斯卡尔算法和普里姆算法，它们都是用来求解最小生成树问题的。
#### 总结
通过对图论模型及其算法的学习，我们可以更好地理解和应用图论相关的知识来解决实际问题。无论是邻接表的实现还是贪心算法的应用，都为信息学竞赛提供了强有力的工具。希望这份资料能够帮助读者更深入地了解图论及其算法。
