《图论基础算法》PPT课件.ppt
图论的基础算法DFS与BFS,图的存储方式两种,邻接矩阵：就是用一个矩阵表示一个图，用二维数组来实现mapNNmapij=1表示i到j有边mapij=0表示不存在边，一般它的实现会在O(n2)的时间复杂度内查边,邻接矩阵表示,图的存储邻接矩阵,邻接矩阵mapij 表示顶点i和顶点j的边关系是否有边相连 0,1表示边权值mapij=w;空间复杂度：O(n2)访问速度快、直观、适合稠密,图的存储方式邻接矩阵,邻接矩阵使用场合数据规模不大n=1000，m越大越好稠密图最好用邻接矩阵图中不能有多重边出现,图的存储方式邻接表边表,结构：struct node int u,v,w;int next;gM;/作为静态内存来使用，速度快int headN,t=0;,初始化,void init()t=0;memset(head,-1,sizeof(head);,加边查找操作,void add(int u,int v,int w)/添加边 gt.u=u;gt.v=v;gt.w=w;gt.next=headu;headu=t;t+;/为下一次做准备/使用的时候，找u的邻接点,/循环查遍for(int=headu;i!=-1;i=gi.next)int v=gi.v;/然后处理：,邻接表链表,结构：struct node int v;/边的结束顶点 int w;/边的长度 node*next;/指向以同一起点的下一条边的指针*firstN;/firstu指向以u为起始点的第一条边,初始化及加边操作,void init()memset(first,NULL,sizeof(first);void add(int u,int v,int w)/添加边 node*p=new node;/node*p=(node*)malloc(sizeof(node);p-v=v;p-w=w;p-next=fisrtu;firstu=p;/传说中的挂链,遍历图的边,/使用的时候，找u的邻接点for(node*p=firstu;p!=NULL;p=p-next)int v=p-v;/在这里作相应的处理,深度优先遍历(Depth-First Traversal)DFS,深度优先遍历(Depth-First Traversal)假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。,图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。,对已访问过的点标记操作,图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited0n-1，其初值为假，一旦访问了顶点Vi之后，便将visitedi置为真。,搜索过程,设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。,#include#include#include#define maxn 107char mapmaxnmaxn;/邻接矩阵存图int visitmaxnmaxn;/标记节点是否被访问过0表示未被访问过1表示访问过int dir82=0,1,1,1,-1,0,0,-1,1,0,-1,-1,1,-1,-1,1;/八个方向int m,n;,void dfs(int x,int y)int i;for(i=0;i=0,int main()/freopen(d.txt,r,stdin);int i,j;while(scanf(%d%d,广度优先遍历(Breadth-FirstTraversal),设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，wt，然后再依次访问与wl，w2，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。,2、广度优先搜索过程,在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，xs和y1，y2，yt。为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，xs和y1，y2，yt，对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队，故保证了每个顶点至多只有一次人队。,#include#include#include#define maxn 107struct node int x,y;char mapmaxnmaxn;/邻接矩阵存图int visitmaxnmaxn;/标记节点是否被访问过0表示未被访问过1表示访问过int dir82=0,1,1,1,-1,0,0,-1,1,0,-1,-1,1,-1,-1,1;node qmaxn*maxn;/八个方向int m,n,l,r;void bfs()int i;while(l=0/入队列,int main()/freopen(d.txt,r,stdin);int i,j;while(scanf(%d%d,
