概念
图的定义
图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组成，通常
表示为： G(V,E)。其中，G 表示一个图，V 是图 G 中顶点的集合，E 是
图 G 中边的集合。
需要注意：
图中数据元素叫做顶点（Vertext）。
在图中，不允许没有顶点。若 V 是图的顶点的集合，那么，V 是非空
有穷集合。图的任意两个顶点之间都可能有关系，它们的关系用边来表示。边集可
以是空的。
其他概念
无向边
若顶点 $V_i$ 到 $V_j$ 之间的边没有方向，这条边就叫做无向边（Edge）,
用无序偶对 ($V_iV_j$) 来表示。
无向图
如果图中任意两个顶点之间的边都是无向边，则称该图为无项图（Undirected graphs）。
有向边
若从顶点 $V_i$ 到 $V_j$ 的边有方向，则称这条边为有向边，也称为弧 (Arc)。
这条有向边用有序偶 $<V_i,V_j>来表示，$V_j是弧尾(Tail)，$V_j$是弧头(Head)。
有向图
如果图中任意两个顶点之间的边都是有向边，这个图就是有向图。
无向边用小括号 “（）”表示，有向边用尖括号“<>”表示。
简单图
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，这样的图就是简单图。
数据结构_图_简单图
无向完全图
在无向图中，如何任意两点之间都存在边，这个图就是无向完全图。
n 个顶点的无向完全图有 ${n(n-1)} \over 2$ 条边。
有向完全图
在有向图中，如果任意两点之间都存在方向互为相反的两条弧，这个图就是有向完全图。
n个顶点的有向完全图有 $n(n-1) \over 2$ 条边。
稠密图和稀疏图
边或弧很少的图是稀疏图；边或弧很多的图是稠密图。
它们都是相对概念。
权、网
与图的边或弧相关的数字叫做权（Weight）。
权可以表示一个顶点到另一个顶点的距离或耗费。
带权的图叫做网（Network）。
子图
假设有两个图 $G = (V,\lbrace E \rbrace)$，$G' = (V',\lbrace E' \rbrace)$，$V' \subseteq V$，$E' \subseteq E$，那么，
G' 是 G 的子图。
图的顶点与边间的关系（暂时不做笔记，有空再补充）
概念太多，记录太麻烦，暂时不做笔记，有空再补充。
连通图
连通图
图7-2-13图2根据定义，我认为它不是强连通图。
数据结构_图_连通图
数据结构_图_连通图_2
数据结构_图_连通图_3
数据结构_图_连通图_4
生成树
不理解。
数据结构_图_生成树_1
数据结构_图_生成树_2
有向树
不理解。
数据结构_图_有向树_1
数据结构_图_有向树_2
图的抽象数据类型
ADT 图(Graph)
Data
顶点的有穷非空集合和边的集合
Operation
CreateGraph(*G, V, VR)：按照顶点集 V 和 边弧集 VR 的定义构造图 G。
DestroyGraph(*G)：图G存在则销毁它。
LocateVex(G, u)：若图 G 中存在顶点 u，则返回它在图中的位置。
GetVex(G, v)：返回图 G 中顶点 v 的值。
PutVex(G, v, value)：将图 G 中顶点 v 赋值 value。
FirstAdjVex(G, *v)：返回顶点 v 的一个邻接顶点，若顶点在 G 中无邻接顶点则返回空。
NextAdjVex(G, v, *w)：返回顶点 v 相对于顶点 w 的下一个邻接顶点，若 w 是 v 的最后
一个邻接点则返回“空”。
InsertVex(*G, v)：在图 G 中增添新顶点 v。
DeleteVex(*G, v): 删除图 G 中顶点 v 及其相关的弧。
InsertArc(*G, v, w)：在图中增添弧 <v,w>，若 G 是无向图，还要增加对称弧 <w,v>。
DeleteArc(*G, v, w)：在图中删除弧 <v,w>，若 G 是无向图，还需要删除对称弧 <w,v>。
DFSTraverse(G)：对图 G 深度优先遍历，在遍历过程中对每个顶点调用。
HFSTraverse(G):对图 G 广度优先遍历，在遍历过程中对每个顶点调用。
endADT
图的存储结构（难理解）
邻接矩阵
定义
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组表示图。一个一维数组存储图中顶点信息，一个
二维数组（称为邻接矩阵）存储图中的边或弧信息。
数据结构_图_邻接矩阵_定义
无向图实例
数据结构_图_邻接矩阵_解释
有向图实例
数据结构_图_邻接矩阵_有向图
网图
数据结构_图_邻接矩阵_网图定义
数据结构_图_邻接矩阵_网图
邻接矩阵存储结构
邻接矩阵存储结构代码：
备注：用65536代替 $\infty$
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100; // 最大顶点数
#define INFINITY 65535;
typedef struct
{
VertexType vexs[MAXVEX]; // 顶点表
EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看作边表
int numVertexes, numEdges; // 图中当前顶点数和边数
}MGraph;
创建无向网图代码：
void CreateGraph(MGraph *G)
{
int i, j, k, w;
printf("%s", "输入顶点数和边数:\n");
scanf("%d, %d", &G->numVertexes, &G->numEdges); // 输入顶点数和边数
for(i = 0; i < G->numVertexes; i++){
scanf(&G->vexs[i]);
}
for(i = 0; i < G->numVertexes; i++){
for(j = 0; j < G->numVertexes; j++){
G->arc[i][j] = INFINITY; // 邻接矩阵初始化
}
}
for(k = 0; k < G->numEdges; k++){ // 读入numEdges条边，建立邻接矩阵
printf("输入边(vi,vj)上的下标i、下标j和权w:\n");
scanf("%d, %d, %d", &i, &j, &w); // 输入边（vi,vj）上的权w
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j]; // 因为是无向图，矩阵对称
}
}
邻接表
概念
定义
数组与链表相结合的方法称为邻接表（Adjacency List）。
思路
图中顶点用一个一维数组存储。该数组存储两部分内容：顶点信息和指针。
该指针指向该顶点的第一个邻接点。图中的每个顶点 $v_i$ 的所有邻接点构成一个线性表，用单链表存储。
这个线性表可能叫 边表，也可能叫 出边表。
当图为无向图的时候，这个线性表叫做顶点 $v_i$ 的边表。
当图为有向图的时候，这个线性表叫做顶点 $v_i$ 作为弧尾的出边表。
摘抄书本
无向图的邻接表结构
数据结构_图_邻接表_无向图的邻接表结构
$v_0$ 的邻接点是 $v_1，v_2，v_3$，$v_0$的 firstEdge 存储的指针指向它的第一个邻接点 $v_1$。
$v_1$ 的 adjvex 存储的是 该顶点在顶点表中的下标，next 存储的指针指向 $v_0$ 的第二个邻接点 $v_2$。
有向图的邻接表结构
数据结构_图_邻接表_有向图的邻接表结构_1
数据结构_图_邻接表_有向图的邻接表结构_2
网图的邻接表结构
数据结构_图_邻接表_网图
邻接表存储结构（看不懂）
结点定义代码
typedef char VertexType;
typedef int EdgeType;
typedef struct EdgeNode // 边表结点
{
int adjvex; // 邻接点域，存储该顶点对应的下标
EdgeType weight; // 权值
struct EdgeNode *next; // 链域，指向下一个连接点
}EdgeNode;
typedef struct VertexNode // 顶点表结点
{
VertexType data; // 顶点域，存储顶点信息
EdgeNode *firstEdge; // 边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes, numEdges; // 图中当前顶点数和边数
}GraphAdjList;
边表结点 EdgeNode 为什么如此定义？
无向图的邻接表创建代码
void CreateALGraph(GraphAdjList *G)
{
int i, j, k;
EdgeNode *e;
printf("输入顶点数和边数：\n");
scanf("%d, %d", &G->numVertexes, &G->numEdges); // 输入顶点数和边数
for(i = 0; i < G->numVertexes; i++){
scanf(&G->adjList[i].data); // 输入顶点信息。这种写法，有问题吗？
G->adjList[i].firstEdge = NULL; // 将边表置为空表。为什么？
}
for(k = 0; k < G->numVertexes; i++){ // 建立边表
printf("输入边(Vi,Vj)上的顶点序号：\n");
scanf("%d, %d", &i, &j); // 输入边(Vi,Vj)上的顶点序号
e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 申请内存空间，创建边表结点
e->adjvex = j; // 邻接序号为j
e->next = G->adjList[i].firstEdge; // 将e指针指向当前顶点指向的结点 ？
G->adjList[i].firstEdge = e; // 将当前顶点的指针指向e
e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 申请内存空间，创建边表结点
e->adjvex = i; // 邻接序号为i
e->next = G->adjList[j].firstEdge; // 将e指针指向当前顶点指向的结点
G->adjList[j].firstEdge = e; // 将当前顶点的指针指向e
}
}
十字链表（看不懂）
摘抄
数据结构_图_十字链表_1
数据结构_图_十字链表_2
数据结构_图_十字链表_3
数据结构_图_十字链表_4
邻接多重表（看不懂）
摘抄
数据结构_图_邻接多重表_1
数据结构_图_邻接多重表_2
数据结构_图_邻接多重表_3
数据结构_图_邻接多重表_4
数据结构_图_邻接多重表_5
边集数组
摘抄
数据结构_图_边集数组_1
数据结构_图_边集数组_2
图的遍历
定义
从图中某一个顶点出发遍访图的其余所有顶点，且使所有顶点被访问且只访问一次。
这个过程，就叫做图的遍历（Traversing Graph）。
深度优先遍历(Depth_First_Search)
摘抄
数据结构_图_深度优先遍历_摘抄_1
虚线表示已经遍历过的点，实线表示未遍历过的点。
数据结构_图_深度优先遍历_摘抄_2
数据结构_图_深度优先遍历_摘抄_3
代码
邻接矩阵代码
typedef int Boolean; // Boolean是布尔类型，其值是TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组
void DFS(MGraph G, int i)
{
int j;
visited[i] = TRUE;
printf("%c", G.vexs[i]);
/*2*/for(j = 0; j < G.numVertexes; j++){
/*1*/if(G.arc[i][j] == 1 && !visited[j] ){
DFS(G, j); // 对未访问的顶点递归调用
}
}
}
void DFSTraverse(MGraph G)
{
int i;
for(i = 0; i < G.numVertexes; i++){
visited[i] = FALSE; // 初始所有顶点状态都是未访问过状态
}
for(i = 0; i < G.numVertexes; i++){
if(!visited[i]){
DFS(G, i);
}
}
}
第1行，G.arc[i][j] == 1 表明 $v_iv_j$ 边存在，这是根据邻接图矩阵定义得出的
结果。
第1行，visited[j] 不能理解这句。
第2行的循环里面的递归，什么时候终止？
邻接表代码（不懂）
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c", GL->adjList[i].data);
p = GL->adjList[i].firstEdge;
while(p){
if(!visited[p->adjvex]){
DFS(GL, p->adjvex);
}
p = p->next;
}
}
void DFSTraverse(GraphAdjList GL)
{
int i;
for(i = 0; i < GL->numVertexes; i++){
visited[i] = FALSE;
}
for(i = 0; i < GL->numVertexes; i++){
if(!visited[i]){
DFS(GL, i);
}
}
}
广度优先遍历(Breadth_First_Search)
摘抄
数据结构_图_广度优先遍历_摘抄_1
数据结构_图_广度优先遍历_摘抄_2
不明白如何得到这张图。
代码
邻接矩阵代码（不懂）
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for(i = 0; i < G.numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q); // 初始化一个辅助用的队列
for(i = 0; i < G.numVertexes; i++){ // 对每一个顶点做循环
if(!visited[i]){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
EnQueue(&Q, i); // 将此顶点入队列
while(!QueueEmpty(Q)){
DeQueue(&Q, &i); // 将队列中元素出队列，赋值给i
for(j = 0; j < G.numVertexes; j++){
if(G.arc[i][j] == 1 && !visited[j]){
visited[j] = TRUE;
printf("%c", G.vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
邻接表代码（不懂）
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue Q;
for(i = 0; i < GL->numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q);
for(i = 0; i < GL->numVertexes; i++){
if(!visited[i]){
visited[i] = TRUE;
printf("%c", GL->adjList[i].data);
EnQueue(&Q, i);
while(!QueueEmpty(Q)){
DeQueue(&Q, &i);
p = GL->adjList[i].firstEdge; // 找到当前顶点边表链表头指针
while(p){
if(!visited[p->adjvex]){
visited[p->adjvex] = TRUE;
printf("%c", GL->adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
}
p = p->next; // 指针指向下一个邻接点
}
}
}
}
最小生成树
定义（不懂）
把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）。
普里姆(Prim)算法（不懂）
代码
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex[MAXVEX]; // 保存相关顶点下标
int lowcost[MAXVEX]; // 保存相关顶点间边的权值
// 初始化第一个权值为0，即v0加入生成树
// lowcost的值为0，在这里就是此下标的顶点已经加入生成树
lowcost[0] = 0;
adjvex[0] = 0; // 初始化第一个顶点下标为0
for(i = 1; i < G.numVertexes; i++){
lowcost[i] = G.arc[0][i]; // 将v0顶点与之有边的权值存入数组
adjvex[i] = 0; // 初始化都为v0的下标
}
for(i = 1; i < G.numVertexes; i++){
min = INFINITY; // 初始化最小权值为 INFINITY
j = 1; k = 0;
while(j < G.numVertexes){
if(lowcost[j] != 0 && lowcost[j] < min){
min = lowcost[j]; // 让当前权值成为最小值
k = j; // 将当前最小值的下标存入k
}
j++;
}
printf("(%d, %d)", adjvex[k], k); //打印当前顶点边中权值最小的边
lowcost[k] = 0; // 将当前顶点的权值设置为0，表示此顶点已经完成任务
for(j = 1; j < G.numVertexes; j++){
if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
lowcost[j] = G.arc[k][j]; // 将较小权值存入lowcost
adjvex[j] = k; // 将下标为k的顶点存入adjvex
}
}
}
}
代码解释
数据结构_图_普里姆算法_代码解释_8
数据结构_图_普里姆算法_代码解释_1
数据结构_图_普里姆算法_代码解释_2
数据结构_图_普里姆算法_代码解释_3
数据结构_图_普里姆算法_代码解释_4
数据结构_图_普里姆算法_代码解释_5
数据结构_图_普里姆算法_代码解释_6
数据结构_图_普里姆算法_代码解释_7
克鲁斯卡尔（Kruskal）算法
代码
typedef struct
{
int begin;
int end;
int weight;
}Edge;
void MiniSpanTree_Kruskal(MGraph G)
{
int i, n, m;
Edge edges[MAXEDGE]; // 定义边集数组
int parent[MAXVEX]; // 定义一数组用来判断边与边是否形成环路
for(i = 0; i < G.numVertexes; i++){
parent[i] = 0; // 初始化数组值为0
}
for(i = 0; i < G.numVertexes; i++){
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if(n != m){ // 假如n与m不等，说明此边没有与现有生成树形成环路
// 将此边的结尾顶点放入下标为起点的parent中
// 表示此顶点已经在生成树集合中
parent[n] = m;
printf("(%d, %d) %d", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int Find(int *parent, int f) // 查找连线顶点的尾部下标
{
while(parent[f] > 0){
f = parent[f];
}
return f;
}
代码解释
数据结构_图_克鲁斯卡尔算法_代码解释_1
数据结构_图_克鲁斯卡尔算法_代码解释_2
数据结构_图_克鲁斯卡尔算法_代码解释_3
数据结构_图_克鲁斯卡尔算法_代码解释_4
数据结构_图_克鲁斯卡尔算法_代码解释_5
数据结构_图_克鲁斯卡尔算法_代码解释_6
数据结构_图_克鲁斯卡尔算法_代码解释_7
数据结构_图_克鲁斯卡尔算法_代码解释_8
数据结构_图_克鲁斯卡尔算法_代码解释_9
数据结构_图_克鲁斯卡尔算法_代码解释_10
数据结构_图_克鲁斯卡尔算法_代码解释_11
数据结构_图_克鲁斯卡尔算法_代码解释_12
最短路径（看不懂）
暂时放弃
定义
非网图的最短路径，是指两顶点之间经过的边数最少的路径。
网图的最短路径，是指两顶点之间经过的边上的权值之和最小的路径。
路径上的第一个源点，最后一个顶点是终点。
