数据结构总结及代码

图基础知识子图：V(H)V(G),E(H) (注：H是G的子图支撑子图：V(H)=V(G),E(H)E(G) (注：H是G的子图)G为无向图V(G)强连通图：G为有向图V(G)中任意两个不同的vivj，vivj可及，vjvi也可及G连通分量：设G是非（强）G的子图GK（强）连通图，则称GK为GGKG的所有连通分量中边最多的一GKG的最大连通分量。选择题：一个具有n个顶点的无向图，最多有（B）An- Bn(n- Dn(n-1)/42的简单路径，若其起点和终点A B C任意 Dnn-1，则该图必是连通图。错误反例：下图中n=56判断题：nn(n-1)条边，则它一定是强连通的。正确nn-1,则该图是同样的题：填空：n个顶点的连通图至少有(n-1)条边，强连通图至少有n条边。A B C DA B C D判断题：一个没有回路的连通图是树正确图的结构邻接矩阵表示法=顶点表+n*n可以用顺序和两种方式来进行，本书中采用的是链接方式来进行。其中顶点表采用顺序方式。每个数组元素的表示形放指向边链表的头结点的指针，即adjacent存放的是顶点VerName：：cost果是无权图，这个域不存在，link为指向后继的指针。注：对于边很多的图，适于用邻接矩阵；对于顶点多而边少的图，用邻接矩阵会形成稀疏矩阵，故更适于用邻接表。（9分100010001233123123条边，则形成的邻接矩阵有多少个元素？有多少个非0元1000*1000=10000001000n个顶点和e条边的无向图，若用邻A B C D判断题：邻接表法只能用于有向的，而邻接矩阵法对于有向图和无向图的都适用。错误选择题：下面关于图的的叙述中_A_正确A用邻接矩阵图，占用的空间大小只与图中顶点个数有B用邻接矩阵图，占用的空间大小只与图中边数有关而C用邻接表图占用的空间大小只与图中顶点个数有关，D用邻接表图，占用的空间大小只与图中边数有关而与 接矩阵是对称阵，可压缩；n个顶点所需空间为 n个顶点的有向图的邻接表，设计算0设计在有向图中一条有向边<vi,vj>，的算法（15分结点数，即为i顶点的出度。求顶点的出度数的算法如下：intGraph::outdegree(int intdegree=0;Edge*p;p=head[v].Adjacent; }return}voidGraph::printout(intn){intcout<<“Theoutdegreesare:”<<endl;{cout<<i<<”<<degree<<endl;}}intGraph::indegree(intn,intv){inti,j,degree;Edge*p;{{}}return}voidGraph::printin(int{intcout<<“Theindegreesare:”<<endl;{cout<<i<<”<<degree<<endl;}}voidGraph::maxoutdegree(int{intmaxdegree=-1000,maxv=0,degree,{{}} =}0intGraph::outzero(int{intnum=0,i;{}return}GraphvoidInserEdge(constT&vi,const遍历被多次，所以要用一个visited[]来标志顶点是否已经voidGraph::DFS(constintv,int{cout<<GetName(v)<<"v //说明v已被intw=Get //取得v的第一个邻接顶点的序{ //若w没被过，从w的递归w=GetNextNeighbor(v,w);//wvw的下一个}}DFS写的稍微详细了voidGraph::BFS(constintv,int*{Queue<int> {intcurrent=v;{cout<<GetName(current)<<"";//当前结点Edge*{{}}}}}ABCEFDAABCEFDADO(n+e).对邻接表中所有的边链表中的结点一次，还要对所有顶点一次，故时间复杂度为：O(n+e).（10分//DFSDFS//visited[]0boolGraph::Connect(int*{for(intk=0;k<g.graphsize;k++)//数组初始化//0for(intk=0;k<g.graphsize;g++) returnfalse;returntrue;}拓扑排序AOV判断题：任意图必有拓扑序列。错误存在环就不可以了v0v3v2v4stack来实现的,voidTopoOrder(int*count,intn)//count[n]记录了n个顶点的{stack<int>s;for(inti=0;i<n;i++){if(count[i]=={s.push(i);//0i}}for(int //n{//n次，栈已为空，说明有回路，{cout<<"Thereisacycleinnetwork}{

intj=s.pop();弹出栈顶元素cout<<j<<endl;Edge*p=head[j].Adjacent;//令pj{intk=p //k为<j,k>//k的入度-10了，则k{}}}}}书上采用了一种用count[]stackvoidTopoOrder(int*count,intn)//count[n]记录了n个顶点的{inttop=-1; for(inti=0;i<n;i++){if(count[i]=={count[i]=top;top=i;//0i}}for(int //n{//n次，栈已为空，说明有回路，{cout<<"Thereisacycleinnetwork!"<<endl;}{

intj=top;top=count[top];弹出栈顶元素cout<<j<<endl;//输出该元素Edge*p=head[j].Adjacent;//令pj{intk=p //k为<j,k>//k的入度-10了，则k{}}}}}这个过程可能令费解，简单解释一下count[i]=0i //topij=top;//j记录当前栈顶元素top=count[top];//top回退到前一个元素建议大家仔细审题果题目要求不能使用stack（一般是节的情况下，其算法的时间复杂度为O(n+e)。O(n+e)（12分）（1）列（2）怎样修改此图，可得到唯一的拓扑序列。(8分)112341324,123432的有向边，就可以得到唯一的拓扑序最小支撑树问题（1）Prim算法（2）Kruskar算法均是贪心算法的PrimKruskar算法求下图的最小支撑树，要求给出具体步骤（例题+P164）（1）n-1条边（2）连通图（3）权值之和PrimKruskar入的过程中注意不要形成环路。终止条件为只剩通分量（n-1条边。填空题：姆算法适用于（求边稠密网的最小支撑树；（）书最短路径问题正权最短路径问题：Dijkstra算法（贪心算法的典型应用，每三年出一次简答题：(8分按Dijkstra算法计算下图中，从顶点A到其他各顶点的最短Dijkstra每对顶点间的最短路径问题:直观考虑，可对每个顶点用一次Dijkstra，但这种方法较为笨拙。下面介绍一种更直观的方法叫做算法。voidGraph::AllLength(constint{intmax=10000;代表正无穷inti,j,k;for(i=0;i<n;i++)//初始化数{{if(i!=j&&A[i][j]<{}}}{{{{ A[k][j]<max&&A[i][k]+A[k][j]<A[i][j]){}}}}}}利用path[][]