【精品数据结构】图讲解.pptVIP

考虑顶点v0,A0[i][j]表示由vi到vj,经由顶点v0的最短路径。只有从v2到v1经过v0的路径和从v2到v3经过v0的路径,不影响v2到v1和v2到v3的路径长度,因此,有： 9.3.3 广度优先有哪些信誉好的足球投注网站遍历 广度优先有哪些信誉好的足球投注网站遍历的过程是：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。 以邻接表为存储结构,用广度优先有哪些信誉好的足球投注网站遍历图时,需要使用一个队列,以类似于按层次遍历二叉树遍历图。对应的算法如下(其中,v是初始顶点编号)： void BFS(ALGraph *G,int v) { ArcNode *p; int w,i; int queue[MAXV],front=0,rear=0; /*定义循环队列*/ int visited[MAXV]; /*定义存放结点的访问标志的数组*/ for (i=0;iG-n;i++) visited[i]=0; /*访问标志数组初始化*/ printf(%2d,v); /*输出被访问顶点的编号*/ visited[v]=1; /*置已访问标记*/ rear=(rear+1)%MAXV; queue[rear]=v; /*v进队*/ while (front!=rear) /*若队列不空时循环*/ { front=(front+1)%MAXV; w=queue[front]; /*出队并赋给w*/ p=G-adjlist[w].firstarc; /*找w的第一个的邻接点*/ while (p!=NULL) { if (visited[p-adjvex]==0) { printf(“%2d”,p-adjvex); /*访问之*/ visited[p-adjvex]=1; rear=(rear+1)%MAXV;/*该顶点进队*/ queue[rear]=p-adjvex; } p=p-nextarc; /*找下一个邻接顶点*/ } } printf(\n); } 例如,以上图的邻接表为例调用BFS()函数,假设初始顶点编号v=2,给出调用BFS()的执行过程。 9.3.4 非连通图的遍历 对于无向图来说,若无向图是连通图,则一次遍历能够访问到图中的所有顶点； 但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶点； 对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点；否则不能访问到所有顶点,为此同样需要再选初始点,继续进行遍历,直到图中的所有顶点都被访问过为止。 采用深度优先有哪些信誉好的足球投注网站遍历非连通无向图的算法如下： DFS1(ALGraph *g) { int i; for (i=0;ig-n;i+) if (visited[i]==0) DFS(g,i); } 采用广度优先有哪些信誉好的足球投注网站遍历非连通无向图的算法如下： BFS1(ALGraph *g) { int i; for (i=0;ig-n;i+) if (visited[i]==0) BFS(g,i); } 9.4 生成树和最小生成树 9.4.1 生成树的概念 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树的(n-1)条边。 如果在一棵生成树上添加一条边,必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边,如果一个图有n个顶点和小于(n