- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
• 首先访问出发顶点v0 • 选择一个与v0相邻接的且末访问过的顶点w访问 • 再从w开始,按深度优先搜索…..
• 每当到达一个其所相邻接的顶点都已被访问过的 顶点,则从最后所访问的顶点开始,依次退回到尚 有邻接顶点末曾访问过的顶点u,并从u开始进行 深序优先搜索…..
• 直到所有顶点都访问过或从任何一个已访问过的 顶点出发,再也无法到达末曾访问过的顶点
int ver2;} E_NODE; L_NODE *head[MAXN]; int visit[MAXN]; E_NODE e[MAXN]; int n,m,u;
void creat_adj_list(head,n,e,m) L_NODE *head[ ]; E_NODE e[ ]; int n,m; {int i,u,v; L_NODE *p; for (i=1;i<=n;i++) head[i]=NULL; for(i=0;i<m;i++) { u=e[i].ver1; v=e[i]=ver2; p=(L_NODE*)moalloc(sizeof(L_NODE)); p->ver=v; p->link=head[u];head[u]=p; p=(L_NODE*)moalloc(sizeof(L_NODE)); p->ver=u; p->link=head[v];head[v]=p;} }
}
求图的连通分量
• 对图的每一个顶点进行检验
– 若被访问过,则该顶点落在已被求出的连通分 量上
– 若末被访问过,则从该顶点出发遍历图,便可 求得图的另一个连通分量
生成树和最小生成树
• 生成树:
设G是一个连通无向图,若G’是包含G中所有 顶点的一个无回路的连通子图,则称G’是G的一棵 生成树
1
2
3
7
4 9
8
16 1
20 11
2 5
19
3
66
22
14
9
4
18
5
最小生成树
• 一个带权连通无向图G的最小生成树是G 的所有生成树中边上的权之和最小的一棵 生成树
• MST性质:
设G(V,E)是一个连通带权的无向图,T=(U,E*) 是正在构造的最小生成树.若边(u,v)的顶点 uU,vV-U,且(u,v)的代价最小,则(u,v)必然存在 于最小生成树
5
6
7
4 9
8
123来自461
2 45
3
86
7
5
9
7
9
8
生成树
• 从G中任一顶点出发,遍历图中的所有顶点,在遍 历过程中,将E分成两个集合T(G)和B(G),其中 T(G)是遍历时所通过的边集,B(G)是剩余的边集, 则G’=(V,T(G))是G的一棵生成树
– dfs生成树
1
– bfs生成树
2
3
5
6
所在的连通分量的所有顶点都有被访问到为止
1
2 5
4 8
3
6
7
9
1 3
4
广度优先搜索法
1 22
2
3
4^
1
3
5^
53 4 5
1
2
1
3
2
3
4
5^
5^
4^
广度优先搜索法
1. 把队列置空 2. 输出出发顶点,置该顶点已被访问的标志 3. 让出发顶点进队 4. 若队列不空,则
– 取出队首中的顶点V – 在邻接表中,依次取得与顶点V邻接的各个顶点 – 转(4)
图的遍历与求图的连通分量
• 图的遍历:
从给定图中任意指定的顶点出发,按照某 种方式系统地访问图中的顶点,使每个顶点仅被 访问一次,所得到的一个序列
• 访问标志位visit[ ]
– 遍历前置visit的各元素为0 – 若顶点vi被访问过,则置visit[i]为1
• 深度优先搜索 广度优先搜索
深度优先搜索
t=t->link;} }
广度优先搜索法
• 首先访问出发点v • 然后访问与顶点v邻接的全部顶点w1,w2,….,wt • 再依次访问与w1,w2,….,wt邻接的全部结点(已访问
过的顶点除外) • 再从这些已访问的顶点出发,依次访问与它们邻接
的全部顶点(已访问的顶点除外) • 依次类推,直到图中所有顶点都访问到或出发顶点V
• 若队列空,则处理过程结束
void bfs(u) int u; {struct queuetype {int qa;
int qe; int item[MAXN];} typedef struct queuetype QTYPE; int v,w; L_NODE *t; QTYPE queue; printf(“%4d”,u); visit[u]=1; queue.qa=0;queue.qe=0 queue.item[0]=u;
void init(n) int n; { int i;
for (i=1;i<=n;i++) visit[i]=0;
}
void dfs(u) int u; { L_NODE *t;
visit[u]=1; printf(“%d”,u); t=head[u]; while(t!=NULL)
{ if (visit[t->ver]= =0) dfs(t->ver);
while(queue.qa<=queue.qe) { v=queue.item[queue.qa++]; t=head[v]; while(t!=NULL) {w=t->ver; if(visit[w]==0) {printf(“%4d”,w); visit[w]=1; queue.item[++queue.qe]=w; } t=t->link; } }
1
2 5
4 8
3
6
7
9
1 3
4
深度优先搜索
1 22
2
3
1
3
53 4 5
1
2
1
3
2
3
4^ 5^
4
5^
5^
4^
#include <stdio.h> #define MAXN 50 #define MAXN 100 struct l_node {int ver;
struct l_node *link;}; typedef struct l_node L_NODE; typedef struct{int ver1;
Prim算法
• 已知G=(V,E)是一个带权连通无向图,顶点V={1,2,….n}, – U为V中构成最小生成树的顶点集合 初始时U={v0},v0是指定的某个顶点,v0V T为构成最小生成树的边的集合,初始时T为空 – 如果(u,v)具有最小代价,且u U,vV-U,则最小生成 树包含边(u,v),即把u加到U中,把(u,v)加入T中 – 这个过程一直进行下去,直到U=V时为止 – 这时T即为所求的最小生成树
