数据结构第八章图答案,数据结构 笔记

　　数据结构复习[图]-Java开发笔记-青藤苑

　　数据结构复习[图] 1。基本术语图：由有限且非空的点集和边集组成，缩写为G(V，E)；

　　顶点：图中的顶点；

　　无向图：图中的每条边都没有方向；

　　有向图：图中的每条边都有方向；

　　无向：一条边是无向的，记为(a，b)

　　边：边有方向，写为A和b。

　　有向边也变成弧；起始顶点叫弧尾，终止顶点叫弧头；

　　简单图：没有指向自身的边，也没有两条重复边的图；

　　无向完全图：每个顶点之间有一条边的无向图；

　　有向完全图：每个顶点之间有两条对边的无向图；

　　稀疏图：相对于顶点边很少的图；

　　稠密图：有许多边的图；

　　权重：图中的边可以有一个权重来区分边的长度；

　　网：有权重的图；

　　度：连接到特定顶点的边的数量；

　　度外和度内：对于有向图的概念，度外表示以该顶点为起点的边数，度内表示以该顶点为终点的边数；

　　环：第一个顶点和最后一个顶点相同的路径；

　　简单环：去掉第一个顶点和最后一个顶点后没有重复顶点的环；

　　连通图：任意两个顶点相互连接的图；

　　最大连通子图：包含尽可能多的顶点(必须是连通的)，即找不到另一个顶点，使得这个顶点可以连接到这个最大连通子图的任意一个顶点；

　　分量：最大连通子图的个数；

　　强连通图：这是有向图的概念，表示任意两个顶点A和B，使得A可以连接B，B也可以连接A；

　　生成树：N个顶点，n-1条边，保证N个顶点互相连通(没有环)；

　　最小生成树：这个生成树的边的权重之和是所有生成树中最小的；

　　AOV网络：节点代表主动网络；

　　AOE网：其边表示活动持续时间的网；

　　2.图1的存储结构。邻接矩阵维护一个二维数组，arr[i][j]表示从I到j的边，如果两个顶点之间有边，则为1，否则为0；

　　维护一个一维数组来存储顶点信息，比如顶点的名称；

　　下图显示了一个一般的有向图：

　　注意：如果想看到vi个节点的相邻点，只需要遍历arr[I]；

　　下图显示了带权重的图的邻接矩阵表示：

　　缺点：邻接矩阵表示对于稀疏图不合理，因为浪费太多空间；

　　2.邻接表如果显示一般图表，如下所示：

　　如果是净重，即边带重量，则如下：

　　3.交叉链表只针对有向图；适用于计算出度和度；

　　顶点：

　　边缘节点：

　　优点：创建的时间复杂度与相邻链表相同，但可以同时计算入度和出度；

　　4.邻接多表是针对无向图的；如果只对节点进行操作，邻接表是个不错的选择，但是如果要删除邻接表中的一条边，就需要删除四个顶点(因为是无向图)；

　　在相邻的多个表中，只需要删除一个节点就可以完成边的删除，因此更加方便。

　　所以相邻多表适合删除边的操作；

　　节点和邻接表没有区别。副表的节点如下：

　　例如：

　　5.边缘集合数组适于依次操作边缘；

　　存储边缘信息，如下所示：

　　三、图遍历DFS思想：去深，去不了深，回朔；

　　例如：

　　1234567891011121314151617181920212223/* * * O(v e)*/@ Testpublic void DFS(){ for(int I=0；即节点长度；我){如果(！visited[i]) {DFS_Traverse(g，I)；} } } private void DFS _ Traverse(graph 2g，int I){ visited[I]=true；system . out . println(I)；EdgeNode node=g.nodes[i]。接下来；while(节点！=null) {if(！已访问[node.idx]) {DFS_Traverse(g，node . idx)；} node=node.next}}BFS思想：遍历所有相邻节点；

　　12345678910111213141516171819202122232425262728 span/span/* * * O(v e)*/@ Testpublic void BFS(){ ArrayList Integer list=new ArrayList Integer for(int I=0；即节点长度；我){如果(!visited[I]){ visited[I]=true；列表。添加；系统。出去。println(一)；而(!列表。isempty()){ int k=list。删除(0)；边缘节点电流=g.nodes[k].接下来；而（当前！=null) {if(！访问过[当前。idx]){已访问[当前。idx]=true；系统。出去。println(当前。idx)；列表。添加(当前。idx)；} current=current.next}}}}四、最小生成树整洁的邻接矩阵存储；123456789101112131415161718192021222324252627282930313233 span/span/* * *时间复杂度为O(n^2)*适用于稠密图*/@ test public void prim(){ int cost[]=new int[9]；int pre[]=new int[9]；for(int I=0；我是G1。顶点。长度；I){成本[I]=G1。adj matrix[0][I]；} cost[0]=0；for(int I=1；我是G1。顶点。长度；I){ int min=65536；int k=0；for(int j=1；G1。顶点。长度；j ){if(cost[j]！=0 cost[j]min){ min=cost[j]；k=j；} }成本[k]=0；System.out.println(pre[k]， k)；for(int j=1；G1。顶点。长度；j ){if(cost[j]！=0 G1。adj matrix[k][j]cost[j]){ pre[j]=k；成本[j]=G1。adj矩阵[k][j]；}}}}krustral边集数组存储；12345678910111213141516171819202122232425 span/span/* * *时间复杂度：O(eloge)*适用于稀疏图*/@ test public void kru stral(){ Edge[]edges=init edges()；int parent[]=new int[9]；for(int I=0；我边缘。长度；I){ Edge Edge=edges[I]；int m=find(parent，edge。begin)；int n=find(parent，edge。end)；如果(m！=n){ parent[m]=n；System.out.println(m ， n)；} } } private static int find(int[]parent，int f){ while(parent[f]0){ f=parent[f]；}返回f；}五、最短路径最短路径算法邻接矩阵存储；123456789101112131415161718192021222223242526272829 span/span //o(n^2)@testpublic void Dijkstra(){ int distance[]=new int[9]；int pre[]=new int[9]；boolean finished[]=new boolean[9]；已完成[0]=真；for(int I=0；I 9；I){距离[I]=G1。adj matrix[0][I]；} int k=0；for(int I=1；I 9；I){ int min=65536；for(int j=0；j 9；j ){if(！完成[j]距离[j] min){min=距离[j]；k=j；} }完成[k]=真；System.out.println(pre[k]， k)；for(int j=1；j 9；j ){if(！已完成[j] (min g1.adjMatrix[k][j])距离{距离[j]=最小G1。adj矩阵[k][j]；pre[j]=k；} } } }弗洛伊德使用：(1)邻接矩阵：存储图；1234567891011121314151617181920212223242526272829 span/span/* * * o(n^3)*求出任意顶点之间的距离*/@ test public void Floyd(图1g){ int I，j，k；整数长度=g .顶点。长度；int dist[][]=new int[长度][长度];int pre[][]=new int[长度][长度];for(I=0；即顶点长度；I){ for(j=0；顶点长度；j){ pre[I][j]=j；dist[I][j]=g . adj矩阵[I][j]；} } for(I=0；我长度；I){ for(j=0；顶点长度；j){ for(k=0；顶点长度；k){ if(dist[I][j]dist[I][k]dist[k][j]){ dist[I][j]=dist[I][k]dist[k][j]；pre[I][j]=pre[I][k]；} } } }系统。出去。println()；}六、拓扑排序使用数据结构：

　　(1)栈：用来存放入度为0的节点；

　　(2)变种邻接列表：作为图的存储结构；此邻接列表的顶点节点还需要存放入度属性；

　　123456789101112131415161718192021222324252627282930/* * * O(n e)*/private静态字符串拓扑排序(图2g 2){ Stack Integer s=new Stack Integer int count=0；for(int I=0；我G2。节点。长度；i ){if(g2.nodes[i].Inde gree==0){ s . push(I)；}}while(！s . isempty()){ int value=s . pop()；System.out.println(值、);数数；边节点node=G2。节点[值]。接下来；而(节点！=null){g2.nodes[node.idx].在度数上-；if(g2.nodes[node.idx]).in gree==0){ s . push(node。idx)；} node=node.next} } if(计G2。节点。length){ return error ；}返回ok ；}七、关键路径使用数据结构：(1)变种邻接列表：同拓扑排序；(2)变量：ltv表示某个事件的最晚开始时间；教育电视表示事件最早开始时间；夏梵表示活动最早开始时间；长期演进表示活动最晚开始时间；123457891 112131415161819 2022234 25265 int length=stack。size()；if(stack==null){ return；} else { int[]ltv=new int[length]；for(int I=0；我堆叠。size()；I){ ltv[I]=ETV[堆栈。size()-1]；}//从拓扑排序的最后开始计算ltvwhile(！堆栈。isempty()){ int top=stack。pop()；EdgeNode current=g.nodes[top]。接下来；而（当前！=null){ int idx=current。idx//最晚发生时间要取所有活动中最早的if((ltv[idx]-当前。weight)ltv[top]){ ltv[top]=ltv[idx]-当前。重量；} } } int ete=0；int LTE=0；for(int j=0；j长度；{EdgeNode current=g.nodes[j].接下来；而（当前！=null){ int idx=current。idxETV[j]；LTE=ltv[idx]-当前。重量；if(ete==lte){//是关键路径} } } } }私有栈整数拓扑_ ETV(){栈整数堆栈2=新栈整数栈整数堆栈1=新栈整数for(int I=0；即节点长度；i ){if(g.nodes[i].Inde gree==0){ stack 1。添加；} } ETV[]=新的int[g .节点。长度]；int count=0；而(!堆栈1。isempty()){ int top=stack 1。pop()；数数；堆栈2.push(顶);EdgeNode current=g.nodes[top]。接下来；而（当前！=null){ int idx=current。idxif(( - g.nodes[idx]).in gree)==0){ stack 1。推送(idx)；}如果((ETV[上]当前。重量)ETV[idx]){ ETV[idx]=ETV[top]当前。重量；} current=current . next } } if(count g . nodes。长度){返回null}返回堆栈2}来源：http://博客。csdn。net/xiazdong/文章/详情/7354411

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。