没有合适的资源?快使用搜索试试~ 我知道了~
数据结构图算法笔记
资源详情
资源评论
资源推荐
算法设计—图
目录
1. 图的存储结构 .......................................................................................................................................1
2. 图的遍历 ................................................................................................................................................1
3. MST 最小生成树算法 .........................................................................................................................3
4. 最短路径算法 .......................................................................................................................................4
5. 有向图,是否存在以 V0 为起点的包含所有顶点的简单路径。 .............................................5
6. 求距离定点 V0 的最短路径为 K 的所有顶点。 ...........................................................................5
7. 无向图,邻接表,求 Vi 与 Vj 之间是否存在一条长度为 K 的简单路径。 ...........................6
8. 邻接矩阵,有向图,是否存在简单有向回路,并输出。 ........................................................7
9. 有向无环图,邻接表,非递归,权值均为 1,求每个定点出发的最长路径的长度。 .....8
10. 邻接表,有向图,输出 ViVj 的所有简单路径 .....................................................................8
11. 邻接矩阵,有向图,BFS,是否存在 ViVj 的路径 ..............................................................8
12. 邻接表,有向图,是否存在回路。 ...........................................................................................9
13. 邻接矩阵,有向无环图,求图中的最长路径长度 .................................................................9
14. 求自由树(无环连通图)的直径(最短距离中最长的) ....................................................9
15. 求图的关节结点(割点),邻接表,链接表,联通有向图 ..................................................9
16. 无向连通图,求半径最小的生成树。(根到叶子的最大距离,称为树的半径) ....... 10
17. 求图的连通分量数 ....................................................................................................................... 11
18. 删除边,无向图,邻接表 .......................................................................................................... 11
19. 删除顶点,邻接表,有向图(邻接矩阵,无向图) .......................................................... 11
20. 判断给定序列书否是一个图的拓扑排序序列,邻接表 ..................................................... 11
21. 邻接表存储->邻接矩阵存储 | 邻接矩阵存储->邻接表存储.................................... 12
22. 判断一个图是否是一棵树(王道-5.3.4-2) ............................................................................... 12
23. 用 DFS 得到图的一个拓扑序列(王道-5.4.5-9) ............................................................... 12
1
1. 图的存储结构
邻接表
typedef struct ArcNode{ // 边表结点
int adjvex; // 该弧所指向的顶点的位置
int weight; // 弧的权值
struct ArcNode *next; // 指向下一条弧的指针
}ArcNode;
typedef struct VNode{ // 顶点表结点
VertexType data; // 顶点信息
ArcNode *first; // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct{
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和弧数
}AALGraph; // ALGraph 是以邻接表存储的图类型
邻接矩阵
typedef struct{
VertexType Vex[MaxVertexNum]; // 顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵,边表
int vexnum, arcnum; // 图的当前顶点数和边数
}MGraph;
2. 图的遍历
BFS(邻接表存储)
时间复杂度
邻接表存储
邻接矩阵存储
空间复杂度
【注】:(1)BFS 可以用来解决单源最短路径问题,但要求所有边的权值相等。
(2)可以用 BFS 或 DFS 来求无向图的连通分量。
bool visited[MaxVertexNum]; // 访问标记数组
void BFSTraverse(Graph G){
memset(visited, 0, sizeof(visited));
InitQueue(Q);
for (i = 0; i < G.vexnum; i++){ // 对每个连通分量调用一次 BFS
if (!visited[i])
BFS(G, i);
}
}
// 从顶点 V 出发,BFS 遍历图 G
2
void BFS(Graph G, int v){
visit(v);
visited[v] = true;
EnQueue(Q, v); // 顶点入队
while (!IsEmpty(Q)){
DeQueue(Q, v);
// 检测 v 的所有邻接点
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
if (!visited[w]){
visit(w);
visited[w] = true; // 访问标记
EnQueue(Q, w);
}
}// while
}
DFS 递归(邻接表存储):
【注】复杂度同 BFS
bool visited[MaxVertexNum];
void DFSTraverse(Graph G){
memset(visited, 0, sizeof(visited));
for (v = 0; v < G.vexnum; v++)
if (!visited[v])
DFS(G, v);
}
void DFS(Graph G, int v){
visit(v);
visited[v] = true;
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
if (!visited[w])
DFS(G, w);
}
DFS 非递归(邻接表存储):
void DFS(Graph &G, int v){
int w; // 顶点序号
InitStack(S);
memset(visited, 0, sizeof(visited));
Push(S, v);
visited[v] = true;
while (!IsEmpty(S)){
k = Pop(s);
visit(k);
for (w = FirstNeighbor(G, k); w >= 0; w = NextNeighbor(G, k, w))
剩余12页未读,继续阅读
smallworldxyl
- 粉丝: 45
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0