文章目录
逻辑结构——基本概念图的存储邻接矩阵邻接表十字链表邻接多重表
图的遍历广度优先搜索深度优先搜索
逻辑结构——基本概念
线性表、树可以为空，但是图不能为空简单图：无重复边，不存在节点到自身的边；反之就是多重图无向完全图：任意两个顶点之间都存在边有向完全图：任意两个顶点之间都存在方向相反的弧生成子图：子图含有原图的所有顶点无向图——连通——顶点之间存在路径——连通图——最少n-1条边有向图——强连通——两个顶点之间同时存在双向的路径——强连通图——最少n条边连通分量（极大连通子图）：连通子图，不存在别的连通子图包含它（尽可能包含顶点和边）强连通分量（极大强连通子图）：强连通子图，不存在别的强连通子图包含它（尽可能包含顶点和边）极小连通子图：连通子图且包含的边最少生成树：连通图包含全部顶点的一个极小连通子图（不唯一）生成森林：非连通图所有连通分量的生成树组成生成森林无向图顶点的度：顶点相邻的边有向图顶点的度：顶点出度和入度之和网：边有权重的图有向树：一个顶点的入度为零，其余顶点入度为1的有向图路径：顶点序列路径长度：路径上边的个数回路：第一个和最后一个顶点相同
图的存储
邻接矩阵
n个顶点的图的矩阵是nxn的，每一维对应一个顶点。行号表示起始端点，列号表示终止端点。
适用于稠密图，空间复杂度为
O
(
n
2
)
O(n^{2})
O(n2)。对于稀疏图空间浪费严重。
邻接表
邻接表法：为每一个顶点建立一个单链表存放与它相邻的边
顶点表：采用顺序存储, 每个数组元素存放顶点的数据和边表的头指针边表（出边表）：采用链式存储, 单链表中存放与一个顶点相邻的所有边, 一个链表结点表示一条从该顶点到链表结点顶点的边
适用于稀疏图
适用性存储方式判断两顶点之间是否存在边找出某顶点相邻的边
邻接矩阵稠密图顺序存储效率高效率低邻接表稀疏图顺序存储+链式存储效率低效率高
十字链表
针对有向图邻接表寻找出边简单，寻找入边难，十字链表是对邻接表的改进十字链表基本结构：
邻接多重表
针对无向图基本结构：
图的遍历
广度优先搜索
类似于树的层次遍历队列+辅助标记数组
bool visited
[MAX_TREE_SIZE
];
void BFSTraverse(Graph G
){
for(int i
=0; i
<G
.vexnum
; i
++)
visited
[i
]=FALSE
;
InitQueue(Q
);
for(int i
; i
<G
.vexnum
; i
++)
if(!visited
[i
])
BFS(G
, i
);
}
void BFS(Graph G
, int v
){
visit(v
);
visited
[v
]=TRUE
;
EnQueue(Q
);
while(!isEmpty(Q
)){
DeQueue(Q
, v
);
for(w
=FirstNeighbor(G
, v
); w
>0; w
=NextNeighbor(G
, v
, w
))
if(!visited
[w
]){
visit
[w
];
visited
[w
]=TRUE
;
EnQueue(Q
, w
);
}
}
}
应用——无权图单源最短路径问题 最短路径是从顶点u到顶点v的路径中经历的边的个数最少的路径
void BFS_MIN_Distance(Graph G
, int u
){
for(int i
=0; i
<G
.vexnum
; ++i
)
d
[i
]=MAX
;
visited
[u
]=TRUE
;
d
[u
]=0;
EnQueue(Q
, u
);
while(!isEmpty(Q
)){
DeQueue(Q
, u
);
for(w
=FirstNeighbor(G
, u
); w
>0; w
=NextNeighbor(G
, u
, w
))
if(!visit
[w
]){
visited
[w
]=TRUE
;
d
[w
]=d
[u
]+1;
EnQueue(Q
, w
);
}
}
}
广度优先生成树：广度遍历过程中，可以得到一颗遍历树，称为广度优先生成树（生成森林）邻接矩阵法的广度优先生成树唯一（邻接矩阵唯一），邻接表法不唯一（邻接表不唯一）。
深度优先搜索
类似于树的先序遍历栈（或递归）+标记数组
bool visited
[MAX_TREE_SIZE
];
void DFSTraverse(Graph G
){
for(int i
=0; i
<G
.vexnum
; ++i
)
visited
[i
]=FALSE
;
for(int i
=0; i
<G
.vexnum
; ++I
)
if(!visited
[i
])
DFS(G
, i
);
}
void DFS(Graph G
, int v
){
visit(v
);
viaited
[v
]=TRUE
;
for(w
=FirstNeighbor(G
, v
); w
>=0; w
=NextNeighbor(G
, v
, w
))
if(!visited
[w
])
DFS(G
, w
);
}
深度优先生成树：深度遍历过程中，可以得到一颗遍历树，称为深度优先生成树（生成森林）邻接矩阵法的深度优先生成树唯一（邻接矩阵唯一），邻接表法不唯一（邻接表不唯一）。无向图中，调用遍历函数（BFS、DFS）的次数为连通分量的个数；有向图中，不存在该结论
内容来源：王道考研——数据结构
