济南大学数据结构课件 第七章.pptVIP

数组表示法 typedef struct { VetexType vexs[MAX_VERTEX_NUM ];//顶点向量 AdjMatrix arc;//邻接矩阵 int vexnum, arcnum;//顶点数和弧数 GraphKind kind; }MGraph;//图的定义 For(I=0;IG.vexnum;++I) //初始化邻接矩阵 for (j=0;jG.vexnum; ++j) G.arcs[I][j]={INFINITY,NULL};//{adj,info} 邻接表--- 链式存储结构 typedef struct { AdjList verteces;//顶点信息向量，存放头结点 int vexnum, arcnum;//顶点数和弧数 int kind;//图的种类标志 }ALGraph;图（邻接表）的定义 边结点由 6 个域构成。其中标志域（mark）用以标记该条边是否被有哪些信誉好的足球投注网站过；ivex 和 jvex 分别指示该条边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边； jlink 指向下一条依附于顶点 jvex 的边；info 指向和边相关的各种信息。 顶点结点由 2 个域构成，数据域（data）存储和该顶点相关的信息；firstedge 指示第一条依附于该顶点的边。 完整的深度优先有哪些信誉好的足球投注网站算法 void DFS(Graph G, int v) { //从v顶点出发递归的深度优先有哪些信誉好的足球投注网站算法 visited[v] = 1; Visit (v); for(w=FirstAdjVex(G, v); w; w = NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); }// DFS 深度遍历图的过程是对每个顶点查找其邻接点的过程，所耗费的时间取决于所采用的存储结构。 当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2),其中n为图中顶点数。 当用邻接表作图的存储结构时，找邻接点所需时间为O(e),其中e为图中边的数目。当以邻接表作存储结构时，深度优先遍历图的时间复杂度为O(n+e)。 算法实现 附设一个辅助数组closedge以记录从U到V-U具有最小代价的边。 对每个顶点vi∈ V-U，在辅助数组中存在一个相应分量closedge[ i-1]，它包括两个域其中lowcost存储该边上的权值,,adjvex为顶点。 Closedge[ I-1].lowcost=Min{cost(u,vi)|u ∈U 算法的时间复杂度 为O（n2) 与网中的边数无关，因此，适用于求稠密的网的最小生成树。 Prim算法示意图 v1 v2 v3 v5 v4 v6 1 5 5 6 5 3 6 6 4 2 例， v1 v3 1 v2 5 v5 3 v6 4 v4 2 初始: U = { v1 } ，V-U = { v2 , v3 , v4 , v5 , v6 } TE = { } U = { v1 , v3 } ，V-U = { v2 , v4 , v5 , v6 } v1 , v3 v3 , v6 U = { v1 , v3 , v6 } ，V-U = { v2 , v4 , v5 } 重点: 边一定存在于 U 与 V-U 之间。 v6 , v4 U = { v1 , v3 , v4 , v6 } ，V-U = { v2 , v5 } v3 , v2 U = { v1 , v2 , v3 , v4 , v6 } ，V-U = { v5 } v2 , v5 U = { v1 , v2 , v3 , v4 , v5 , v6 } ，V-U = { } V1 V2 V4 V5 V3 V6 6 5 5 5 6 6 2 1 3 4 V1 V2 V4 V5 V3 V6 1 V1 V2 V4 V5 V3 V6 1 4 V1 V2 V4 V5 V3 V6 1 4 2 V1 V2 V4 V5 V3 V6 1 4 2 5 V1 V2 V4 V5 V3 V6 1 4 2 5 3 思想： 重复执行: N = ( V , E ) 是 n 顶点的连通网，设 E 是连通网中边的集合； 选取 E 中权值最小的边 ( u , v ) ， 否，将边 ( u , v ) 纳入 TE 中，并从 E 中删除边 ( u , v ) ； 判断边 ( u , v ) 与 TE 中的边是否构成回路 ？