福大真题数据结构课件graph

1线性表、堆栈、队1线性表、堆栈、队图本课件部分资源引自互联⽹和相关书籍⽂2，不便⼀⼀列出来源，在此⼀并图本课件部分资源引自互联⽹和相关书籍⽂2，不便⼀⼀列出来源，在此⼀并图的定义和表示7.1-7.6-图的定义和表示7.1-7.6-344566定比层次结构定比层次结构更加复杂的非线性结层次关系中（树），每个结点只有一个父本质上是一种多对多的关顶点的非空有限集合V和边（顶点对）的有限集(可为空)E所组成的二元组G，记为G=(V,7衍生概有衍生概有向(u,v)中u为起点，v为终点，(v,u)中v无向(u,v)和(v,u)是同一条8简单简单图中的每条边均带有一个赋权有向图和赋权无向图统称为网9完全完全无向图：0<=e<=n(n-1)/2有向图：0<=e<=n(n-完全无向完全有向其它术其它术关无向边(u,v)中，顶点u和v互为邻接点/相邻接，(u,v)关联于顶点u和有向边(u,v)中，终点v是起点u的邻接顶点(u,v)关联于顶点u和顶点的无向图中顶点v的度就是关联于该顶点的边的数有向图以顶点v为终点的边的数目称为v的入度以顶点v为起点的边的数目称为v的出度顶点数n，边数e和度数之间的关系例 例 顶点2例 顶点4入度 出度子G=(V,E)，G’=(V’,E’)，V’是V子G=(V,E)，G’=(V’,E’)，V’是V路顶点序列u(1),u(2),…,u(m)，使有向图中路径也是有向简单路简单路除了起点和终点可能相同外，其余顶点均不相同起点和终点相同的简单路径称为简单回连通图和连通分顶点u和v之间存在一条路径，称u和v是连通的∀u和v，两者都是连通的，则称无向图通图无向图G的极大连通子图称为G的连通分任何连通图只有自身一个连通分非连通图有多个连通分强连通图强连通图和强连通分有向图中∀u和v，存在着从u到v和任何强连通图只有自身一个强连通分非强连通有向图有多个强连通分有根顶点v即为该有根图的ADTADTADT基本运ADT基本运GraphAdd(i,j,G)GraphDelete(i,j,G)Degree(i,G)OutDegree(i,G)InDegree(i,G)备以有向图为基本无向图中的一条边(u,v)用两条有向边(u,v)和(v,u)代结点集合：一般可以用1...n来进行编号结点集合：一般可以用1...n来进行编号12例34例12^345^^^^^^12例34例12^345^^^^^^i,j,wi为两条有向加权边i－>j和j->i，权重均为w空间耗有向图空间耗有向图无向图利用无向图邻接矩阵对称性，仅保存上三角或下三角部分，从而节省一半时间耗费：输入和查看n思类似树的思类似树的儿子链表表示稀疏型图用邻接表表示比邻接矩阵表示有 有向 有向 ⽆向typedefstructgraphstructtypedefstructgraphstructn;//WItem//ᴣ҅i,jڞز//਋(i,j)ӧ਋਋҅ڞ਋ଫහᕟزܔ创建一个有n个孤创建一个有n个孤立顶点的赋权有向图二维矩阵中每个元素初始化为无边标记GraphGraphinit(intn,WItemGraphG=malloc(sizeof*G);G->a=Make2DArray(G->n+1,G-//图的顶点编号为1-n，因此开辟二维数组return{}GraphVertices(G)ғ਋਋ᩙࢧ਋ํGraphVertices(G)ғ਋਋ᩙࢧ਋ํintGraphVertices(GraphG){returnG-GraphEdges(G)ғ਋਋ᩙࢧ਋ํintGraphEdges(GraphG){returnG-GraphExist(i,j,G)ғڣෙ਋(i,j)ฎވintGraphExist(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]==G->NoEdge)return0;} voidGraphAdd(inti,intj, voidGraphAdd(inti,intj,WItemw,Graph{if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]!==G-rrr("dG-}voidGraphDelete(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]==G-/਋,rrr("dG->a[i][j]=G-}҅ ҅ intOutDegree(inti,Graph{intif(i<1||i>G->n)Error("BadInput");for(j=1;j<G->n);j++)if(G->a[i][j]!=G->NoEdge)sum++;returnsum;}҅ intInDegree(inti,Graph{intif(i<1||i>G->n)Error("BadInput");for(j=1;j<G->n);j++)if(G->a[j][i]!=G->NoEdge)sum++;returnsum;}voidGraphOut(GraphG{intfor(i=1;i<=G->n;{for(j=1;j<=G->n;j++)WItemShow(G-printf("\n}扩展将无向扩展将无向图视为有向图来GraphAdd(i,j,w,G)在图G中加入一条权重为w的GraphDelete(i,j,G)在图中删除边(i,j)的同时还应G->e--ಘ਋ෙጱಘ਋ෙጱԅ҅਋ԅ0ጱ਋ײᐏ෫਋ ғಅํᩙ਋਋ํݻਫሿӾ਋ጱGraph{GraphG=malloc(sizeof*G);G-G->a=Make2DArray(G->n+1,G-return扩展每条边的权重扩展每条边的权重为1,无边时边权为无向图中的一条边(u,v)用两条有向边(u,v)和(v,u)代替直观体所有赋权无向图实现中取消权重的概念w出现处均直接置为1NoEdge出现处均直接置为0GraphAdd(i,j,G)在图G中加入边(i,j)的同时还应加入G-(i,j,G)在图中删除边(i,j)的同时还应删除G->e--有向图和无向图邻接表结点结构有向图和无向图邻接表结点结构typedefstructlnodestruct//਋Ӟ਋}glinkNewLNode(intv,glink{glinkx=malloc(sizeofx->v=v;x->next=next;returnx;}邻接表实邻接表实现下有向图和无向图的结构定typedefstructgraphgraph{int/හGraphintGraphG=malloc(sizeof*G);G-for(i=0;i<=n;i++)returnG;{}在结点在结点i的邻接表中线性扫描是否包含intGraphExist(inti,intj,Graph{glinkif(i<1||j<1||i>G->n||j>G->n)return0;while(p&&p->v!=j)p=p->next;if(p)return1;elsereturn}在结点i的邻在结点i的邻接表中增加一个结点包含voidGraphAdd(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||i==j||GraphExist(i,j,G))Error("BadInput");//ڣෙ਋فฎݳވဩғฎވ૪ํ਋(i,j)G->adj[i]=NewLNode(j,G-}在结点i的邻接表中在结点i的邻接表中删除包含j的结voidGraphDelete(inti,intj,Graph{if(i<1||j<1||i>G->n||j>G->n||!GraphExist(i,j,G))Error("BadInput");//ڣෙ਋فฎݳވဩғฎވ਋ဌํ਋(i,j)p=G->adj[i];//ಚൈ(p-{G->adj[i]=p-{while(p&&p->next->v!=j)p=p-if(p){q=p->next;p->next=q->next;}}intOutDegree(inti,Graph{glinkp;intif(i<1i>G->n)Error("Badp=G-while(p){j++;p=p->next;}returnj;}对于j=1,…,n，计算边(j,i)存在的条intInDegree(inti,Graph{intj,if(i<1i>G->n)Error("Badfor(j=1;j<=G->n;if(GraphExist(j,i,G))sum++;returnsum;}输出有向图G的邻接void输出有向图G的邻接voidGraphOut(Graph{glinkp;inti;for(i=1;i<=G->n;{while(p){printf("%d",p-printf("\np=p-}}ಘ਋ෙಘ਋ෙ ํG->adj[i]=NewLNode(j,G- ํG->adj[j]=NewLNode(i,G-G->e++;if(p->v==i){G->adj[j]=p->next;free(p);}else{while(p&&p->net->v!=i)p=p->next;if(p){q=p->next;p->next=q->next;要求：每个顶点对应的邻接表要求：每个顶点对应的邻接表结点中除了存储和该顶点相邻接的顶点以方法:修订邻接表结点类型与赋权有向图要求相适typedefstructlnode*glink;structlnode{intv;//边的另一个顶WItemw;//边next;//邻接表指针，指向邻接表的下一个}glinkNewLWNode(intv,WItemw,glink//创建一个新的邻接表结点并插入至next{glinkx=malloc(sizeofx->v=v;x->w=w;x->next=next;returnx;}邻接表下赋权有向图的结构定义和有向图的结构定义一致成员函成员函数的实GraphGraphinit(int{intGraphG=malloc(sizeo*G);G-for(i=0;i<=n;i++)G->adj[i]=0;returnG;}GraphAdd(i,j,w,G)在图GraphAdd(i,j,w,G)在图中加入一条权G->adj[i]=NewLWNode(j,w,G-if(p){q=p->next;p->next=q->next;if(p){q=p->next;p->next=q->next;}ಘ਋ෙᩙ਋਋෫ݻࢶӾጱӞ਋਋਋ԅw਋(i,j)አӷ਋਋਋ԅwጱํ ํݻ਋(i,j) ํݻ਋(j,i) p=G->adj[j];//ڢᴻ਋(j,i)if(p->v==i){G->adj[j]=p->next;11掌握无圈有向图DAG的拓扑排序及其应用关键路掌握构造最小支撑树的Prim算法——贪心算法策例广度例广度遍历V2⇒V3⇒V4⇒V5⇒V6⇒V7深度遍历V2⇒V4⇒V8⇒V5⇒V3⇒V6基本基本在依次访问v的每一个未被访问过的邻接顶点之后，分别从这些邻接顶点出发，递归地以广度优先方式搜索图以广度优先搜索策略遍历图的过程是以一个顶点v为起始顶点，由近及远，依次访问和v有路相通，且路径长度为1,2,…,的顶点——类似于树的层序遍历标记顶点v//从顶点v开始，广度优先遍历图的算法标记顶点v//从顶点v开始，广度优先遍历图的算法设u是wwhileQ}u=w}}具体实现的时候可以用一个数组pre来记录顶点被访问的先后次序，同时防止顶点被重复访问初始化时所有顶点v有录途中顶点的访问次序，每访问一个顶点，即pre[v]=cnt++，算法结邻接矩阵下无向图的广度优先搜索邻接矩阵下无向图的广度优先搜索算法bfsvoidbfs(GraphG,int{intQueueq=QueueInit();whileif{for(j=1;j<=G->n;if(G->a[i][j])if(pre[j]==0)}例}缺如何改进voidbfs(GraphG,int{intj;Queueq=QueueInit();(!QueueEmpty(q)){i=Deletfor(j=1;j<=G->n;if((G->a[i][j])&&{EnterQueue(j,q);}时间复杂时间复杂nbfssBSO(s*n)O(∑OD())思考题：邻接表下的BFS如何实现BFS下图的遍BFS下图的遍历算调用一次BS可以访问图中起始顶点所在连通分支中的所有顶点，但不能访问图中和连通的其它顶点调用一次BFS只能遍历图G的一个连通分支图为连通图——一次BFS可以遍历图G的所有顶点图G为非连通图——包含多个连通分一次BS只能访问一个连通分支，剩余连通对每一个连通分支调用一次for(i=1;i<G->n;i++)for(i=1;i<=G->n;if(pre[i]==0)例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^广度遍历vexdata例adjvex1234567837^2^88^6^74^1234567^8^2^广度遍历vexdata例adjvex1234567837^2^88^6^74^1234567^8^2^⇒广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7⇒V6广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7⇒V6广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7⇒V6⇒V4广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^⇒V2⇒V7⇒V6⇒V4广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7⇒V6⇒V4⇒V8广度遍历例vexdataadjvex1234567837^2^88^6^74^1234⇒V2⇒V7⇒V6⇒V4⇒V8广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^⇒V2⇒V7⇒V6⇒V4⇒V8⇒广度遍历例vexdataadjvex1234567837^2^88^6^74^12⇒V2⇒V7⇒V6⇒V4⇒V8⇒广度遍历例vexdataadjvex1234567837^2^88^6^74^1234567^8^2^图的广度图的广度优先遍历时间复杂邻接表表示法下，广度优先遍历所需时为基本思基本思将V中的每一个顶点都标记为未被选取一个顶点v∈V，开始搜索，标记v为已访递归调用深度优先搜索方法，依次搜索v的每一个访问过的邻接顶直至从v出发有路径可达的顶点都已经被访问过尽可能地先对纵深方向进行搜当前访问顶点为x，下一步选择x的邻接顶点y进访问，紧接着由顶点y出发，选择y的邻接顶点z行访问，形成68点x出发的一个纵深搜索序 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历 vexdata adjvex 32 456782834567^8^7^2^ 深度遍历 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3 vexdata adjvex 32 456782834567^8^7 深度遍历：V1⇒V3 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3⇒V7 vexdata adjvex 32 456782834567 深度遍历：V1⇒V3⇒V7 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3⇒V7⇒V6 vexdata adjvex 32 456782834 深度遍历：V1⇒V3⇒V7⇒V6 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3⇒V7⇒V6⇒V2 vexdata adjvex 32 45678 深度遍历：V1⇒V3⇒V7⇒V6⇒V2 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3⇒V7⇒V6⇒V2⇒V4 vexdata adjvex 32 4 深度遍历：V1⇒V3⇒V7⇒V6⇒V2⇒V4 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3⇒V7⇒V6⇒V2⇒V4⇒V8 vexdata adjvex 32 深度遍历：V1⇒V3⇒V7⇒V6⇒V2⇒V4⇒V8 vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^ 深度遍历：V1⇒V3⇒V7⇒V6⇒V2⇒V4⇒V8⇒ vexdata adjvex 32 深度遍历：V1⇒V3⇒V7⇒V6⇒V2⇒V4⇒V8⇒ vexdata adjvex 32 456782834567^8^7^2^8^6^74^2^算法描递归实邻接矩算法描递归实邻接矩阵下无向图G中深度优先搜索算法voiddfs(GraphG,int{intj;for(j=1;j<=G->n;if(G-if(pre[j]==0)}邻接表下有向图G中深度优先搜索算法voiddfs(GraphG,int{glinkp;for(p=G->adj[i];p;p=p-if(pre[p->v]==0)dfs(G,p-}一次递归搜索找到一个连通分支，时间复杂性同广 先搜索时间复杂 深度优先搜索方式下的图的遍历voidGraphSearch(Graph{intfor深度优先搜索方式下的图的遍历voidGraphSearch(Graph{intfor(i=1;i<G->n;i++)for(i=1;i<=G->n;if(pre[i]==0)}Floyd问题问题给定V中的一个顶点，称为常用Dijkstra荷兰计算机科学家艾兹赫尔·戴克斯特（EdsgerWybeDijkstra）（1972年图灵奖获得者）算法策略——贪心重点——贪心策略的应用和边的源点：1，最短路径估计源点：1，最短路径估计011-22有两条出边：2-3和2-123456顶点ڡ01∞∞∞ᒫӞྯຂ014∞∞ᒫԫྯຂ0184ᒫӣྯຂ123456顶点ڡ01∞∞∞ᒫӞྯຂ014∞∞ᒫԫྯຂ0184ᒫӣྯຂ0184ᒫྯଢ଼0184ᒫԲྯຂ0184Dijkstra算Dijkstra算顶点集合V-特殊路径：设u是V-S中的某一个顶点，把从源顶点s到u且中间只经过S中顶点的路径称为123456ڡ01∞∞∞ᒫӞྯຂ014∞∞ᒫԫྯ0184算法前算法前设置一个顶点集合重点：一个顶点属于集合S当且仅当从源算法步骤：贪心选择与边的松弛交替使用初始时，中仅含有源顶点s,V-余的所有顶点初始化数组每次从V-S中取出具有最短特殊路径长度的顶点u（贪心策略的应用），将u添加到S中，同时对数组dist做必要的修改(边42422213164233542422213164233542422012136423354242201213642335224422012136423352244220121364233522442201213642334522442201213642334522∞442201213642334522∞442201213642334522∞442201213642334522∞4422012136423345∞22∞442201213∞642334522∞442201213∞6423345∞22∞442201213∞642334522∞442201213∞6423345∞∞4422201213∞642335∞∞4422201213∞642335∞∞4422201213∞642335∞∞4422201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞642335∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞22∞442201213∞6423345∞Ꭸᇙྯ22∞442201213∞6423345∞贪⼼选22∞442201213∞6423345∞贪⼼选22∞442201213∞6423345∞贪⼼选22∞442201213∞6423345∞贪⼼选22∞442201213∞6423345∞贪⼼选ᕮᅩ222∞442201213∞6423345∞贪⼼选ᕮᅩ2ฎٍ๋๋ྯ22∞442201213∞6423345∞边的松22∞442201213∞6423345∞边的松22∞442201213∞6423345∞边的松22∞442201213∞6423345∞边的松22∞442201213∞6423345∞边的松22∞442201213∞6423345∞边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松22∞442201213∞6423345∞3边的松6∞22442201213∞6423345∞3边的松6∞22442201213∞6423345∞3边的松6∞22442201213∞6423345∞3边的松6∞22442201213∞6423345∞3边的松6∞22442201213∞6423345∞3边的松6∞22442201213∞6423345∞3边的松6∞22442201213∞6423345∞43边的松6∞22442201213∞6423345∞43边的松6∞22442201213∞6423345∞43ဳᜋᕮᅩ3̵4̵56∞22442201213∞6423345∞43ဳᜋᕮᅩ3̵4̵5ጱ๋ྯ4޾ᕮᅩ5ฎኧӧਂᜋᇙྯᜋஆᜋᇙྯ边的松ฎෛਂӞᜋๅᎨጱᇙྯ226442201213∞64233354贪⼼选226442201213∞64233354贪⼼选226442201213∞64233354贪⼼选226442201213∞64233354贪⼼选226442201213∞64233354边的松226442201213∞64233354边的松226442201213∞64233354边的松226442201213∞64233354边的松226442201213∞64233354 dist(5)没有变 边的226442201213∞64233354 dist(5)没有变 边的松226442201213∞64233354贪⼼选226442201213∞64233354贪⼼选226442201213∞64233354贪⼼选226442201213∞64233354贪⼼选226442201213∞64233354边的松226442201213∞64233354边的松226442201213∞64233354边的松226442201213∞64233354边的松226442201213∞64233354 dist(4)没有变 边的226442201213∞64233354 dist(4)没有变 边的松226442201213∞64233354 dist(4)没有变 边的226442201213∞64233354 dist(4)没有变 边的松226442201213∞64233354 dist(4)没有变 边的松226442201213∞64233354 dist(4)没有变 边的松2264422016∞21364233354 dist(4)没有变 边的2264422016∞21364233354 dist(4)没有变 边的松226442201213664233354贪⼼选226442201213664233354贪⼼选226442201213664233354贪⼼选226442201213664233354贪⼼选226442201213664233354边的松226442201213664233354边的松226442201213664233354边的松226442201213664233354边的松226442201213664233354 dist(6)没有改 边226442201213664233354 dist(6)没有改 边的松226442201213664233354贪⼼选226442201213664233354贪⼼选226442201213664233354贪⼼选226442201213664233354贪⼼选226442201213664233354226442201213664233354226442201213664233354 226442201213664233354 226442201213664233354 226442201213664233354 226442201213664233354226442201213664233354Dijkstra算法描਋فጱᩙ਋਋Dijkstra算法描਋فጱᩙ਋਋ํdist[v]਋ᐏ୮ڹ਋რsکᶮᅩvጱํᎨ਋ஆᳩଶprev[v]਋ᐏ਋რsکᶮᅩvጱํᎨ਋ஆӤᶮᅩvጱڹḝᶮᅩ਋LSӾಅํ਋਋s਋তጱ਋ஆጱᶮᅩڡত۸dist[v]=a[s][v],਋ԭಅํୌᒈ਋Lތ۱ಅํጱprev[v]<>0ጱᶮᅩv//ᇙ਋ஆ҅ Ṉ3Step2: ҅਋ྯfor(i=1;i<=G->n;i++){dist[i]=a[s][i];if(dist[i]for(i=1;i<=G->n;i++){dist[i]=a[s][i];if(dist[i]==G->NoEdge)prev[i]={prev[i]=s;} ץst޾re(!ListEmpty())๋๋//ਖ਼ᶮᅩvᜋᜋLӾڢᴻ҅ଚץදdistጱ؀intiListDelMin(L,dist);//P.154for(intj=1;j<=G->n;j++)if(G->a[i][j]!=G-&&(!prev[j]||dist[j]>dist[i]+G-//dist[j]dist[j]=dist[i]+G-if(!prev[j]){//LጱᶮᅩjL}}数据结构数据结构说dist数组的作prev数组的作实现最短路径的回计算结束后可以根据数组prev找到从源s到v的最短路径上的每个顶点的前一个顶点，从而找到从源s到v时间复杂性：邻接矩阵实现下dist[x]<=d(s,x)d(x,u)>=0—dist[i新的特殊路径先经过老的S到达顶点u新的特殊路径先经过老的S到达顶点uu经过一条边直接到达顶点FORDFORDBellman-Ford算法——Dijkstrafor(k=1;k<=n-1k++)//进⾏n-1轮松弛for(i=1;i<=e;i++)//枚举每⼀条边{时间复杂}}基本思基本思动态规划dist2[u],…distn-1[u]当s到u存在一条边(s,u)时当k>1时，distk[u]如何求解当前问题：当k>1时，需要求解tkik[]为从s到u的最多经过G中k条边的最短从s到u的最多经过G中k条边的路径满足三个条件最后一条边一定是一条和顶点u关联的边从s到v最多经过G中k-1条3.对于任何一条从s到u最多经过G中k条边的路径而言，其长度pahku=pthk-v+ev,)要求解ditk[u]，即要求解最小的path[k,u]=min{path[k-1,v]+e(v,u)|(v,u)∈=min{min(path[k-1,v])+e(v,u)|(v,u)∈=min{distk-1[v]+e(v,u)|(v,u)∈b5-3a0cd4Bellman-b5-3a0cd4Bellman-5b53ac40d4Bellman-15b53ac40d4Bellman-15b53ac30d74Bellman-25b53ac30d74Bellman-25 5 43Bellman- <dist1҂5b53ac30d64Bellman-35b53ac30d64Bellman-35b53ac30d64Bellman-3ဳ5b53ac30d64Bellman-3ဳ5b530ac3d64Bellman-5b530ac3d64Bellman-2d:0d:∞AB-d:∞21-42d:0d:∞AB-d:∞21-4C51-DE4d:∞d:∞d:0d:∞-2AB-π:nilCd:∞221-4C51d:0d:∞-2AB-π:nilCd:∞221-4C51-DE4d:∞4d:∞d:0d:∞-2AB-π:nilCBd:∞2021-4C51-d:0d:∞-2AB-π:nilCBd:∞2021-4C51-DE4d:∞4π:nild:∞Cd:0d:∞-2AB-π:nilCBd:∞2021-4C51-DEd:0d:∞-2AB-π:nilCBd:∞2021-4C51-DE4d:∞4π:Cd:∞3d:0π:nilAEd:∞-1-2AB-π:nilCBBd:∞20-121-4C51-d:0π:nilAEd:∞-1-2AB-π:nilCBBd:∞20-121-4C51-DE4d:∞4π:Cd:∞3核心问如何按照递核心问如何按照递推公式计算任意一个顶点tk由递推公式distk[u]=min{distk-∈E}分析，可以得知，只有某一个顶点vdistk-1[v]比distk-2[v]更短时，需要重新计算邻接顶点u的记录顶点的最短路径更新次数，如存在一个从源可达的负权圈，相应顶点的最短路径将会不断更新，否则因为从源到任何一个顶点的最短路径最多只有n-1条边，因此，其更新算法依次从队列qu中取出更新过最短路径长度的顶点j，对其邻接顶点k按照计算i[]代码实代码实初始化工递推计算while负权圈的判if(count[k]>n)printf("cycleofnegativeweightexists!\n");return0;}递推计p=G-递推计p=G-if(dist[j]>dist[k]+p-{(!ub[j]){ue(j,qu);}}}时间复杂性：最坏情况下问题问题解决方时间复杂性为O(3)解决方Floyd-Warshall算1962年，RobertW.Floyd(1978年图灵奖获得同年，Setphen首先考虑路径（i,1j）是否存在（（i,1）和(1,j)是否存在）。如果存在，则比较（i,j）和（i,1,j）的路径长度取长度较短者为从ij1的最短是说，如果（i,1,2）和（2,1,j）分于1的最短路径，计算（i,1,2)+(2,1,j），将它和已经得到的从i到j中间顶再增加一个顶点3，继续进行试依次类推,…直至增加顶点结在一结在一般情况下，若（i,…,k）（k,…,j）分别是从i到k和从k到j路径，则将（i,…,k,…,j）和已经经过n-2次比较，最后求得的必是i到j的最短路特每一次的试探都是前一次试探结上的一次迭代求教材P.158边权为负时，Floyd解决方解决方n*n的耗费矩阵初始时，0j第k次迭代前，当前k[ij]的值表大于k-1的顶点的最短路径长度，k[,]+k[kj]表示从顶点i到顶点k，再从k到j，且中间不经过编号大于k的顶点的最短路径长度k,jmk[,j],ck-经过第k次迭代之后，k的值是点的最短路径长Floyd算法for(inti=1;i<=G->n;Floyd算法for(inti=1;i<=G->n;for(intj=1;j<=G->n;{}c[i][j]=path[i][j]=for(inti=1;i<=G->n;i++)for(intk=1;k<=n;k++)for(inti=1;i<=n;for(intj=1;j<=n;{t1=t2=t3=c[i][i]=if(t1!=G->NoEdge&&t2!=G-(t3==G-{c[i][j]=t1+ץcij]޾jt[i][j] }二维数组path的作用：帮助记录(i,j)点对间最短路径的走向3 时间复杂性：O(n 设G=(V,E)是一个无向连通赋权图，E设G=(V,E)是一个无向连通赋权图，E中每条边棵包含G的所有顶点的树，则称G’为G的支撑在G最小生成树并§最小生成树的表示和存储§最小生成树的表示和存储实•–最小生成树是由边ጱᵞݳ所构成的如何合理而有效地表示和存储，•树？方法 ੪ݢզ表示和存储最小生•借助边结点结构Edge实现边的表示typedefstructedge{intu;intv;WItemw;}//边的构造函数EdgeEDGE（intu,intv,WItem{Edgee.u=u;e.v=v;e.w=w;returne;}借助于边结点的数组存放最小生成树边的集合TEdget[maxE]–构造常见的最小生成树构造算Prim算Kruskal算最小生成树性质（MST性质反证法证PRIMPRIMPRIMS存放GT存放GPRIMS存放GT存放G初始条初始条方所有的顶点集合被分为两个集合S（已被选入生成树的顶点）和V-S（未被选入生成树的顶MT性质，从所有i∈∈-的边中，选取具有最小权值的边i，加入中，将边（i）加入集合T中，如此不＝T中恰好包含了最小支撑树的所有边起点为顶点起点为顶点Prim算法描{whilePrim算法描{whileS=S∈V-SጱํԭӞj∈SӾ҅ๅෛํੜ਋਋(i,j)=//ই֜ᖌಷᚆड़ෙ޾ๅෛԞᚆड़ள਋ತکํ}}结T中所有的边构成G的一棵最小支撑树设置两个数组closest和对于每一个设置两个数组closest和对于每一个j∈V-S，lowcost[j]用来保存顶点jclosest[j]是依附于该边的在集合S--12---11-----12---11---Prim算法实Prim算法实for(i=1;i<G->n;i++){min=G->NoEdge;j=1;for(k=2;k<=G->n;if{j=k;}//找到符合条件的t[kk].weight=t[kk].u=t[kk++].v=closest[j];//边加入到最小生成树存放的数组t中for(k=2;k<=n;if((G- }//修正V-S集合中顶点对应的lowcost和closest数组单}时间复杂性：KRUSKALKRUSKALKRUSKALKRUSKAL当查看到第k当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶连通分支组成一个集合，借助并查集的基本运算连通分支组成一个集合，借助并查集的基本运算顺序查看操作即为pop实inte,i,k,s,t;Edge实inte,i,k,s,t;Edgea[maxE];UFsetU;for(i=0,k=0;i<e&&k<G->n-i++){s=UFfind(a[i].u,U);//查找顶点u包含在哪个连通分支中t=UFfind(a[i].v,u);//查找顶点v包含在哪个连通分支中if(s!=t){//u和v分属于两个不同的连通分支}}预处理（P.167-168）边结构edge的定义加权边数组的抽Kruskal算法时Kruskal算法时间复杂性——当e=Ω(n2)时，Kruskal算法比Prim算当e=O(n2)时，Kruskal算法比Prim法好（稀疏型图二分设G=(V,E)是一二分设G=(V,E)是一个无向图，如果顶点集合可以分割为两个互不相交的子集，并且图中每条边(i,j)所关匹最大匹配——G的边数最多的匹完全匹配一定是一个最大匹所得到的边集合记为M⊕所得到的边集合记为M⊕P，则M⊕P是一个解决树的构适用范围：图G为二方取G的一个方取G的一个未匹配顶点作为树根结点，位于树的第层点而且不属于M的边，连同这条边关联的另外点而且属于M的边，连同这条边关联的另外一偏序关满足以偏序关满足以下两个条件的二元关系反自反性：对于所有的a∈S,aRa不成应用实例——学生选课问课程与课程之间存在着偏序关例课程代课程名先修程序设计基无离散数数据结汇编语语言的设计和分例课程代课程名先修程序设计基无离散数数据结汇编语语言的设计和分计算机原编译原操作系高等数无线性代普通物数值分思思课程之间存在偏序关系，所有课程形成的偏合可以用一个DAG加以表示(将偏序集合图的顶点，元素间的偏序关系作为顶点间的有边，即可用DAG表示该偏序集)，要顺序学习这对于一个DAG中所有的顶点确定ord:V->{0,1,2,…,n-ֵ਋਋ԭಅํጱ਋(u,v)∈E਋ํ—਋ಏഭଧጱ୵或或反拓扑排反拓扑排DAG的邻接表实现下反拓DAG的邻接表实现下反拓扑排序算voidRevTopSort(GraphD,int{intv;for(v=0;v<=D->n;v++)for(v=1;v<=D->n;v++)if(pre[v])TSdfs(D,v,}voidTSdfs(GraphD,intv,int{glinkt;for(t=D->adj[v];t;t=t-if(pre[t->v])TSdfs(Dt->vts);//深度优先遍历递归实现}时间复杂DAG的邻接矩阵实现下反拓DAG的邻接矩阵实现下反拓扑排序算voidRevTopSort(GraphD,int{intv;for(v=0;v<=D->n;v++)for(v=1;v<=D->n;v++)if(pre[v])TSdfs(D,v,}voidTSdfs(GraphD,intv,int{intw;for(w=0;w<d->n;if(D->a[w][v]&&pre[w])TSdfs(Dt->v,ts);//数组ts给出所有顶点的反拓扑序}时间复杂当DG顶点数n1时，显然有拓扑排序假设对于所有顶点数小于nDG拓扑排序删除一个入度为0的顶点v，以及所有该顶点为起点的边，得到一个包含n-1根据归纳假设，G'可以进行拓扑排序v的入度为0，因此将v至于G'拓扑序列的最前面，即可合成图G的拓扑序列0DA拓扑序列拓扑序列拓扑序列拓扑序列拓扑序列：C1--拓扑序列拓扑序列：C1--拓扑序列拓扑序列：C1--拓扑序列拓扑序列：C1--拓扑序列拓扑序列：C1--C2--拓扑序列：C1--C2--拓扑序列：C1--C2--拓扑序列：C1--C2--拓扑序列：C1--C2--C3--拓扑序列：C1--C2--拓扑序列：C1--C2--C3--拓扑序列：C1--C2--拓扑序列：C1--C2--C3--拓扑序列：C1--C2--拓扑序列：C1--C2--C3--拓扑序列：C1--C2--拓扑序列：C1--C2--C3--C4--拓扑序列：C1--C2--C3--C4--拓扑序列：C1--C2--C3--C4--C5--拓扑序列：C1--C2--C3--C4--拓扑序列：C1--C2--C3--C4--C5--拓扑序列：C1--C2--C3--C4--拓扑序列：C1--C2--C3--C4--C5--拓扑序列：C1--C2--C3--C4--拓扑序列：C1--C2--C3--C4--C5--拓扑序列：C1--C2--C3--C4--拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7---10拓扑序列：C1--C2--C3--C4--C5--C7---10拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7---10拓扑序列：C1--C2--C3--C4--C5--C7---10拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7--拓扑序列：C1--C2--C3--C4--C5--C7----C10--拓扑序列：C1--C2--C3--C4--