数据结构图--课程设计

2024-05-25 04:38
文章标签 数据结构 课程设计

本文主要是介绍数据结构图--课程设计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构课程设计-----图的创建及相关操作的实现

输入图的类型（有向图、有向网、无向图、无向网）、图的顶点个数、边的条数、图的顶点信息、各条边以及边的权重（如果是网），任意选用一种数据结构，编写程序将图存入内存，并实现以下的各个操作：

  1. 存储结构的转换：如果是无向图或无向网，在邻接矩阵、邻接表、邻接多重表之间转换；如果是有向图或有向网，在邻接矩阵、邻接表和逆邻接表、十字链表之间转换；

  2. 完成增加顶点和删除顶点的功能，删除顶点也要删除与之关联的边；

  3. 完成增加边和删除边的功能；

  4. 完成图的深度优先遍历和广度优先遍历；

  5. 求图的深度优先或广度优先的生成树（或生成森林）（存储结构为孩子-兄弟链表），并对生成树进行遍历；

  6. 判断图的连通性，输出连通分量的个数；

  7. 判断图中是否存在环；

  8. 判断u到v是否存在路径；

  9. 对于图（不是网），求顶点u到v的一条简单路径；

  10. 对于图（不是网），求顶点u到v的所有简单路径；

  11. 实现Dijkstra和Floyd算法求最短路径；

  12. 实现普里姆或克鲁斯卡尔算法求最小生成树。

[java]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. package GraphDemo;  
  2.   
  3. public class Vertex<AnyType>{  
  4.     public AnyType data;  
  5.     public Arc firstArc;  
  6.     public boolean vis;  
  7.     public boolean primVis;  
  8.     public int inDegree;  
  9.     public int outDegree;  
  10.     public int degree;  
  11.     public int topNum;  
  12.     public int dist;  
  13.     public int primDist;  
  14.     public int weight;  
  15.     public Vertex(AnyType data,Arc firstArc){  
  16.         this.data=data;  
  17.         this.firstArc=firstArc;  
  18.     }  
  19.     public Vertex(AnyType data){  
  20.         this(data,null);  
  21.     }  
  22. }  

[java]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. package GraphDemo;  
  2.   
  3. import TwoWayLinkedListDemo.TwoWayLinkedListNode;  
  4.   
  5. public class Arc{  
  6.     int vex;  
  7.     int adjVex;  
  8.     public Arc nextArc;  
  9.     int weight;  
  10.     public Arc(){}  
  11.     public Arc(int adjVex,Arc nextArc,int weight){  
  12.         this.adjVex=adjVex;  
  13.         this.nextArc=nextArc;  
  14.         this.weight=weight;  
  15.     }  
  16.     public Arc(int adjVex,int weight){  
  17.         this(adjVex,null,weight);  
  18.     }  
  19.     public Arc(int adjVex,Arc nextArc){  
  20.         this(adjVex,nextArc,1);  
  21.     }  
  22.     public Arc(int adjVex){  
  23.         this(adjVex,null,1);  
  24.     }  
  25. }  

[java]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. package GraphDemo;  
  2.   
  3. public class Node<AnyType>{  
  4.     AnyType data;  
  5.     Node<AnyType> firstChild,Sibling;  
  6.     Node(){  
  7.         data=null;  
  8.         firstChild=Sibling=null;  
  9.     }  
  10.     Node(AnyType data){  
  11.         this.data=data;  
  12.         firstChild=Sibling=null;  
  13.     }  
  14.     Node(AnyType data,Node<AnyType>lt,Node<AnyType>rt){  
  15.         this.data=data;  
  16.         firstChild=lt;  
  17.         Sibling=rt;  
  18.     }  
  19.     public Node<AnyType>getleftChild(){  
  20.         return firstChild;  
  21.     }  
  22.     public Node<AnyType>getrigthChild(){  
  23.         return Sibling;  
  24.     }  
  25. }  
[java]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. package GraphDemo;  
  2.   
  3. class DisjSets{  
  4.     public int s[];  
  5.     public DisjSets(int numElements){  
  6.         s=new int[numElements];  
  7.         for(int i=0;i<s.length;i++)  
  8.             s[i]=i;  
  9.     }  
  10.     public void union(int root1,int root2){  
  11.         int x,y;  
  12.         x=find(root1);  
  13.         y=find(root2);  
  14.         if(x!=y) s[y]=x;  
  15.     }  
  16.     public int find(int x){  
  17.         while(x!=s[x])  
  18.             x=s[x];  
  19.         return x;  
  20.     }  
  21. }  

[java]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. package GraphDemo;  
  2.   
  3. import java.util.ArrayList;  
  4. import java.util.Comparator;  
  5. import java.util.HashMap;  
  6. import java.util.LinkedList;  
  7. import java.util.List;  
  8. import java.util.Map;  
  9. import java.util.PriorityQueue;  
  10. import java.util.Queue;  
  11. import java.util.Scanner;  
  12. import java.util.Stack;  
  13. public class Graph<AnyType>{  
  14.     int DG=1,UNG=2,DN=3,UND=4;  
  15.     int vexNum;  
  16.     int arcNum;  
  17.     int type;  
  18.     int count;  
  19.     int INF=0xfffff;  
  20.     Node first;  
  21.     LinkedList<Vertex> vertexs=new LinkedList<Vertex>();  
  22.     public Graph(int type,int vexNum,int arcNum){  
  23.         this.type=type;  
  24.         this.arcNum=arcNum;  
  25.         this.vexNum=vexNum;  
  26.     }  
  27.     //创建图  
  28.     public Graph(){}  
  29.     //创建有向图  
  30.     public void createDG(List<AnyType>v,List<Integer>a,List<Integer> b,List<Integer> x){  
  31.         for(int i=0;i<vexNum;i++)  
  32.             vertexs.add(new Vertex<AnyType>(v.get(i)));  
  33.         for(int i=0;i<a.size();i++){  
  34.             int arc1=a.get(i);  
  35.             int arc2=b.get(i);  
  36.             Vertex<AnyType> ver=vertexs.get(arc1);  
  37.             Arc arc=new Arc(arc2);  
  38.             arc.vex=arc1;  
  39.             arc.weight=x.get(i);  
  40.             arc.nextArc=ver.firstArc;  
  41.             ver.firstArc=arc;  
  42.         }  
  43.     }  
  44.     //创建无向图  
  45.     public void createUDG(List<AnyType> v,List<Integer> a,List<Integer> b,List<Integer> x){  
  46.         for(int i=0;i<vexNum;i++)  
  47.             vertexs.add(new Vertex<AnyType>(v.get(i)));  
  48.         for(int i=0;i<a.size();i++){  
  49.             int arc1=a.get(i);  
  50.             int arc2=b.get(i);  
  51.             Vertex<AnyType> ver=vertexs.get(arc1);  
  52.             Arc p=new Arc(arc2);  
  53.             p.nextArc=ver.firstArc;  
  54.             ver.firstArc=p;  
  55.             Arc q=new Arc(arc1);  
  56.             ver=vertexs.get(arc2);  
  57.             q.nextArc=ver.firstArc;  
  58.             ver.firstArc=q;  
  59.             q.weight=x.get(i);  
  60.             p.weight=x.get(i);  
  61.         }  
  62.     }  
  63.     //创建有向网  
  64.     public void createDN(List<AnyType> v,List<Integer> a,List<Integer> b,List<Integer> x){  
  65.         for(int i=0;i<vexNum;i++)  
  66.             vertexs.add(new Vertex<AnyType>(v.get(i)));  
  67.         for(int i=0;i<a.size();i++){  
  68.          int arc1=a.get(i);  
  69.          int arc2=b.get(i);   
  70.          int weight=x.get(i);  
  71.          Vertex<AnyType> ver=vertexs.get(arc1);  
  72.          Arc arc=new Arc(arc2,weight);  
  73.          arc.nextArc=ver.firstArc;  
  74.          ver.firstArc=arc;   
  75.         }  
  76.     }  
  77.     //创建无向网  
  78.     public void createUDN(List<AnyType> v,List<Integer> a,List<Integer> b,List<Integer> x){  
  79.         for(int i=0;i<vexNum;i++)      
  80.             vertexs.add(new Vertex<AnyType>(v.get(i)));  
  81.         for(int i=0;i<a.size();i++){  
  82.             int arc1=a.get(i);  
  83.             int arc2=b.get(i);    
  84.          Vertex<AnyType> ver=vertexs.get(arc1);  
  85.          Arc p=new Arc(arc2);  
  86.          p.nextArc=ver.firstArc;  
  87.          ver.firstArc=p;  
  88.          Arc q=new Arc(arc1);  
  89.          ver=vertexs.get(arc2);  
  90.          q.nextArc=ver.firstArc;  
  91.          ver.firstArc=q;  
  92.          q.weight=x.get(i);  
  93.          p.weight=x.get(i);  
  94.         }  
  95.     }  
  96.     public void createGraph(int type,List<AnyType> v,List<Integer> a,List<Integer> b,List<Integer> x){  
  97.         if(vexNum<=0||arcNum<0){  
  98.             System.out.println("您创建的图有误！");  
  99.             return;  
  100.         }  
  101.         switch(type){  
  102.         case 1:createDG(v,a,b,x);break;  
  103.         case 2:createUDG(v,a,b,x);break;  
  104.         case 3:createDN(v,a,b,x);break;  
  105.         case 4:createUDN(v,a,b,x);break;  
  106.         default:System.out.println("您指定的图的类型有误！");  
  107.         }  
  108.     }  
  109.     //求第一个邻接点  
  110.     public int firstAdjVex(int v){  
  111.         if(v<0||v>vexNum){  
  112.             System.out.println("输入不合法！");  
  113.         }  
  114.         Vertex<AnyType> ver=vertexs.get(v);  
  115.         Arc p=ver.firstArc;  
  116.         if(p!=null)return p.adjVex;  
  117.         return -1;  
  118.     }  
  119.     //求下一条边  
  120.     public int nextAdjVex(int v,int w){  
  121.         if(v<0||v>=vexNum){  
  122.             System.out.println("输入不合法！");  
  123.         }  
  124.         Vertex<AnyType> ver=vertexs.get(v);  
  125.         Arc arc=ver.firstArc;  
  126.         int next=arc.adjVex;  
  127.         while(arc!=null&&next!=w){  
  128.             arc=arc.nextArc;  
  129.             next=arc.adjVex;  
  130.         }  
  131.         if(arc!=null)  
  132.             arc=arc.nextArc;  
  133.         if(arc!=null)return arc.adjVex;  
  134.         return -1;  
  135.     }  
  136.     //求出度  
  137.     public int outDegree(int v){  
  138.         int outDegree=0;  
  139.         Vertex<AnyType> ver=vertexs.get(v);  
  140.         Arc arc=ver.firstArc;  
  141.         while(arc!=null){  
  142.             outDegree++;  
  143.             arc=arc.nextArc;  
  144.         }  
  145.         return outDegree;  
  146.     }  
  147.     //求入度  
  148.     public int inDegree(int v){  
  149.         int inDegree=0;  
  150.         for(int i=0;i<vexNum;i++){  
  151.             if(i==v)continue;  
  152.             Vertex<AnyType> ver=vertexs.get(i);  
  153.             Arc arc=ver.firstArc;  
  154.             while(arc!=null){  
  155.                 if(arc.adjVex==v){  
  156.                     inDegree++;  
  157.                     break;  
  158.                 }  
  159.                 arc=arc.nextArc;  
  160.             }  
  161.         }  
  162.         return inDegree;  
  163.     }  
  164.     //邻接表转换为邻接矩阵  
  165.     public int[][] getAdjacencyMatrix(){  
  166.         int[][] adjacencyMatrix=new int[vexNum][vexNum];  
  167.         for(int i=0;i<vexNum;i++){  
  168.             Vertex<AnyType> ver=vertexs.get(i);  
  169.             Arc arc=ver.firstArc;  
  170.             for(int j=firstAdjVex(i);j>=0;j=nextAdjVex(i,j)){  
  171.                 adjacencyMatrix[i][j]=arc.weight;  
  172.                 arc=arc.nextArc;  
  173.             }  
  174.         }  
  175.         return adjacencyMatrix;  
  176.     }  
  177.     //打印邻接矩阵  
  178.     public void printAdjacencyMatrix(){  
  179.         int[][] adjacencyMatrix=getAdjacencyMatrix();  
  180.         for(int i=0;i<adjacencyMatrix.length;i++)  
  181.         {  
  182.             for(int j=0;j<adjacencyMatrix[i].length;j++)  
  183.                 System.out.print(adjacencyMatrix[i][j]+" ");  
  184.             System.out.println();  
  185.         }  
  186.     }  
  187.     //插入节点  
  188.     public void insertVertex(AnyType data){  
  189.         vertexs.add(new Vertex<AnyType>(data));  
  190.         vexNum++;  
  191.     }  
  192.     //删除节点  
  193.     public void delete(AnyType a){  
  194.         int i;  
  195.         for(i=0;i<vexNum;i++)  
  196.             if(vertexs.get(i).data.equals(a))  
  197.                 break;  
  198.         if(i==vexNum){  
  199.             System.out.println("您所删除的元素不存在！");  
  200.             return;  
  201.         }  
  202.         for(int j=firstAdjVex(i);j>=0;j=nextAdjVex(i,j)){  
  203.             if(type==2||type==4)  
  204.                 vertexs.get(j).degree--;  
  205.             else{  
  206.                 vertexs.get(j).inDegree--;  
  207.                 vertexs.get(j).degree--;  
  208.             }  
  209.         }  
  210.         vertexs.remove(i);  
  211.         vexNum--;  
  212.         for(int j=0;j<vexNum;j++){  
  213.             Vertex<AnyType> v=vertexs.get(j);  
  214.             Arc arc=v.firstArc;  
  215.             if(arc!=null){  
  216.                 if(arc.adjVex==i){  
  217.                     v.firstArc=v.firstArc.nextArc;  
  218.                     if(type==2||type==4)  
  219.                         v.degree--;  
  220.                     else{  
  221.                         v.outDegree--;  
  222.                         v.degree--;  
  223.                     }  
  224.                     continue;  
  225.                 }  
  226.             while(arc.nextArc!=null){  
  227.                 if(arc.nextArc.adjVex==i){  
  228.                     arc.nextArc=arc.nextArc.nextArc;  
  229.                     if(type==2||type==4){  
  230.                         v.degree--;  
  231.                     }  
  232.                     else if(type==1||type==3){  
  233.                         arc=arc.nextArc;  
  234.                         v.outDegree--;  
  235.                         v.degree--;  
  236.                     }  
  237.                     break;  
  238.                 }  
  239.                 arc=arc.nextArc;  
  240.             }  
  241.         }  
  242.     }  
  243.    }  
  244.     //删除边  
  245.     public void removeEdege(int i,int a){  
  246.         Arc q=vertexs.get(i).firstArc;  
  247.         if(q.adjVex==a)  
  248.             vertexs.get(i).firstArc=q.nextArc;  
  249.         while(q.nextArc!=null){  
  250.             if(q.nextArc.adjVex==a){  
  251.                 q.nextArc=q.nextArc.nextArc;  
  252.                 break;  
  253.             }  
  254.             q=q.nextArc;  
  255.         }  
  256.     }  
  257.     //增加边  
  258.     public void addEdege(int ss[],int ee[],int num){  
  259.         for(int i=0;i<num;i++){  
  260.             Arc tmp1=new Arc();  
  261.             tmp1.adjVex=ee[i];  
  262.             Arc q=vertexs.get(ss[i]).firstArc;  
  263.             tmp1.nextArc=q;  
  264.             vertexs.get(ss[i]).firstArc=tmp1;  
  265.         }  
  266.     }  
  267.     //DFS  
  268.     void DFS(int start){  
  269.         if(start>=vexNum)return;  
  270.         Vertex<AnyType> tmp=vertexs.get(start);  
  271.         tmp.vis=true;  
  272.         System.out.print(tmp.data+" ");  
  273.         if(tmp.firstArc!=null){  
  274.             for(int w=tmp.firstArc.adjVex;w>=0;w=nextAdjVex(start,w)){  
  275.                 if(vertexs.get(w).vis==false)  
  276.                     DFS(w);  
  277.             }  
  278.         }  
  279.     }  
  280.     //BFS  
  281.     void BFS(int start){  
  282.         Queue<Integer> queue=new LinkedList<Integer>();  
  283.         vertexs.get(start).vis=true;  
  284.         queue.add(start);  
  285.         while(!queue.isEmpty()){  
  286.             int tmp1=queue.remove();  
  287.             System.out.print(vertexs.get(tmp1).data+" ");  
  288.             int tmp2=firstAdjVex(tmp1);  
  289.             while(tmp2!=-1){  
  290.                 if(vertexs.get(tmp2).vis==false){  
  291.                     vertexs.get(tmp2).vis=true;  
  292.                     queue.add(tmp2);  
  293.                 }  
  294.                 tmp2=nextAdjVex(tmp1,tmp2);  
  295.             }  
  296.         }  
  297.     }  
  298.     //深度优先遍历最小生成树  
  299.     public void DFSTree(int v){  
  300.         first=new Node<AnyType>();  
  301.         first.data=vertexs.get(v).data;  
  302.         DFSTree(v,first);  
  303.     }  
  304.     void DFSTree(int v,Node T){  
  305.         vertexs.get(v).vis=true;  
  306.         int w;  
  307.         Node p;  
  308.         boolean first=true;  
  309.         Node q=null;  
  310.         System.out.print(T.data+" ");  
  311.         for(w=firstAdjVex(v);w>=0;w=nextAdjVex(v,w))  
  312.             if(!vertexs.get(w).vis){  
  313.                 p=new Node(vertexs.get(w).data);  
  314.                 if(first){  
  315.                     T.firstChild=p;  
  316.                     first=false;  
  317.                 }  
  318.                 else q.Sibling=p;  
  319.                 q=p;  
  320.                 DFSTree(w,q);  
  321.             }  
  322.     }  
  323.     //广度优先遍历最小生成树(先序遍历)  
  324.     public void preOrderTree(){  
  325.         if(first!=null)preOrderTree(first);  
  326.     }  
  327.     public void preOrderTree(Node<AnyType> t){  
  328.         if(t!=null){  
  329.             System.out.print(t.data+" ");//遍历根  
  330.             preOrderTree(t.firstChild);//遍历左子树  
  331.             preOrderTree(t.Sibling);//遍历右子树  
  332.         }  
  333.     }  
  334.     //判断有向图是否存在环  
  335.     public boolean isDGCircle(){  
  336.         Queue<Vertex> q=new LinkedList<Vertex>();  
  337.         int count=0;  
  338.         for(int i=0;i<vertexs.size();i++)  
  339.             if(vertexs.get(i).inDegree==0)  
  340.                 q.add(vertexs.get(i));  
  341.         while(!q.isEmpty()){  
  342.             Vertex v=q.poll();  
  343.             count++;  
  344.             Arc p=null;  
  345.             for(p=v.firstArc;p!=null;p=p.nextArc)  
  346.                 if(--vertexs.get(p.adjVex).inDegree==0)  
  347.                     q.add(vertexs.get(p.adjVex));  
  348.         }  
  349.         if(count!=vexNum)return false;  
  350.         else return true;  
  351.     }  
  352.     //判断无向图是否存在环  
  353.     public boolean UDGCircle(){  
  354.         if(arcNum>vexNum-1)  
  355.             return false;  
  356.         else return true;  
  357.     }  
  358.     //BFS判断是否存在路径  
  359.     public boolean BFSRoute(Graph<AnyType> g,int u,int v){  
  360.         Queue<Integer> queue=new LinkedList<Integer>();  
  361.         g.vertexs.get(u).vis=true;  
  362.         queue.add(u);  
  363.         while(!queue.isEmpty()){  
  364.             int tmp1=queue.remove();  
  365.             if(tmp1==v){  
  366.                 for(int i=0;i<g.vertexs.size();i++)  
  367.                     g.vertexs.get(i).vis=false;  
  368.                 return true;  
  369.             }  
  370.             int tmp2=firstAdjVex(tmp1);  
  371.             while(tmp2!=-1){  
  372.                 if(g.vertexs.get(tmp2).vis==false){  
  373.                     queue.add(tmp2);  
  374.                     g.vertexs.get(tmp2).vis=true;  
  375.                 }  
  376.                 tmp2=nextAdjVex(tmp1,tmp2);  
  377.             }  
  378.         }  
  379.         for(int i=0;i<g.vertexs.size();i++)  
  380.             g.vertexs.get(i).vis=false;  
  381.         return false;  
  382.     }  
  383.     //判断U到V是否存在路径  
  384.     public boolean isURouteV(Graph<AnyType> g,int u,int v){  
  385.         if(BFSRoute(g,u,v)==true)  
  386.             return true;  
  387.         return false;  
  388.     }  
  389.     //求一条从U到V的简单路径  
  390.     public LinkedList<Integer> oneURouteV(Graph<AnyType> g,int u,int v){  
  391.         Map<Integer,Integer> parent=new HashMap<Integer,Integer>();  
  392.         LinkedList<Integer> tmp=new LinkedList<Integer>();  
  393.         if(isURouteV(g,u,v)==true){  
  394.             Queue<Integer> queue=new LinkedList<Integer>();  
  395.             for(int i=0;i<g.vertexs.size();i++)  
  396.                 parent.put(i,i);  
  397.             g.vertexs.get(u).vis=true;  
  398.             queue.add(u);  
  399.             while(!queue.isEmpty()){  
  400.                 int tmp1=queue.remove();  
  401.                 if(tmp1==v)break;  
  402.                 int tmp2=firstAdjVex(tmp1);  
  403.                 while(tmp2!=-1){  
  404.                     if(g.vertexs.get(tmp2).vis==false){  
  405.                         parent.put(tmp2,tmp1);  
  406.                         queue.add(tmp2);  
  407.                         g.vertexs.get(tmp2).vis=true;  
  408.                     }  
  409.                     tmp2=nextAdjVex(tmp1,tmp2);  
  410.                 }  
  411.             }  
  412.             //存路径  
  413.             int x=v;  
  414.             while(x!=u){  
  415.                 tmp.add(x);  
  416.                 x=parent.get(x);  
  417.             }  
  418.             tmp.add(u);  
  419.             return tmp;  
  420.         }  
  421.         else{  
  422.             System.out.println("两点之间没有路径。");  
  423.             return null;  
  424.         }  
  425.     }  
  426.     //求U到V的所有路径  
  427.     public void allURouteV(Graph<AnyType> g,int u,int v){  
  428.         LinkedList<Integer> stack=new LinkedList<Integer>();  
  429.         count=1;  
  430.         stack.addLast(u);  
  431.         for(int i=firstAdjVex(u);i!=-1;i=nextAdjVex(u,i)){  
  432.             if(g.vertexs.get(i).vis==false){  
  433.                 g.vertexs.get(i).vis=true;  
  434.                 stack.addLast(i);  
  435.                 search(g,i,v,stack);  
  436.                 g.vertexs.get(i).vis=false;  
  437.                 stack.pollLast();  
  438.             }  
  439.         }  
  440.     }  
  441.     public void search(Graph<AnyType> g,int x,int v,LinkedList<Integer> ss){  
  442.         if(x==v){  
  443.             System.out.print("路径"+count+":");  
  444.             count++;  
  445.             for(int i=0;i<ss.size()-1;i++)  
  446.                 System.out.print(g.vertexs.get(ss.get(i)).data+"->");  
  447.             System.out.println(g.vertexs.get(ss.get(ss.size()-1)).data);  
  448.             return;  
  449.         }  
  450.         else{  
  451.             for(int j=firstAdjVex(x);j!=-1;j=nextAdjVex(x,j))  
  452.                 if(g.vertexs.get(j).vis==false){  
  453.                     g.vertexs.get(j).vis=true;  
  454.                     ss.addLast(j);  
  455.                     search(g,j,v,ss);  
  456.                     g.vertexs.get(j).vis=false;  
  457.                     ss.pollLast();  
  458.                 }  
  459.         }  
  460.     }  
  461.     //Dijkstra  
  462.     int pre[]=new int[107];  
  463.     Map<Integer,Integer> parents=new HashMap<Integer,Integer>();  
  464.     public void Dijkstra(Graph<AnyType> g,Vertex<AnyType> s,int start){  
  465.         LinkedList<Integer> tmp=new LinkedList<Integer>();  
  466.         for(int i=0;i<g.vertexs.size();i++){  
  467.             pre[i]=start;  
  468.             g.vertexs.get(i).dist=INF;  
  469.             g.vertexs.get(i).vis=false;  
  470.             parents.put(i,i);  
  471.         }  
  472.         s.dist=0;  
  473.         for(int i=0;i<g.vertexs.size();i++){  
  474.             int min=INF;  
  475.             int v=0;  
  476.             for(int j=0;j<g.vertexs.size();j++)  
  477.                 if(g.vertexs.get(j).vis==false&&g.vertexs.get(j).dist<min){  
  478.                     min=g.vertexs.get(j).dist;  
  479.                     v=j;  
  480.                 }  
  481.             g.vertexs.get(v).vis=true;  
  482.             for(int j=0;j<g.vertexs.size();j++)  
  483.                 if(g.vertexs.get(j).vis==false&&weigthWith(v,j)!=-1){  
  484.                     if(g.vertexs.get(j).dist>g.vertexs.get(v).dist+weigthWith(v,j)){  
  485.                         g.vertexs.get(j).dist=g.vertexs.get(v).dist+weigthWith(v,j);  
  486.                         pre[j]=v;  
  487.                         parents.put(j,v);  
  488.                     }  
  489.                 }  
  490.         }  
  491.     }  
  492.     public void printPath(Graph<AnyType>g,int u,int v){  
  493.         int x=v;  
  494.         LinkedList<Integer> tmp=new LinkedList<Integer>();  
  495.         while(x!=u){  
  496.             tmp.add(x);  
  497.             x=parents.get(x);  
  498.         }  
  499.         tmp.add(u);  
  500.         for(int i=tmp.size()-1;i>0;i--)  
  501.             System.out.print(g.vertexs.get(tmp.get(i)).data+"->");  
  502.         System.out.println(g.vertexs.get(tmp.get(0)).data);  
  503.     }  
  504.     public void printPath(int s,int e,int num){  
  505.         int a[]=new int[107],i,k;  
  506.         k=0;  
  507.         a[k++]=e;  
  508.         i=e;  
  509.         while(s!=i){  
  510.             i=pre[i];  
  511.             a[k++]=i;  
  512.         }  
  513.         System.out.print("Path"+num+": ");  
  514.         for(i=k-1;i>0;i--)  
  515.             System.out.print(a[i]+"-->");  
  516.         System.out.println(a[0]);  
  517.     }  
  518.     //判断v到w是否存在路径，并返回其权值  
  519.     public int weigthWith(int v,int w){  
  520.         Arc p=vertexs.get(v).firstArc;  
  521.         if(p==null)return -1;  
  522.         while(p!=null&&p.adjVex!=w)  
  523.             p=p.nextArc;  
  524.         if(p==null)return -1;  
  525.         return p.weight;  
  526.     }  
  527.     //Kruskal  
  528.     public int Kruskal(Graph<AnyType> g){  
  529.         int edgesAccept=0,ans=0;  
  530.         LinkedList<Arc> minTree=new LinkedList<Arc>();  
  531.         PriorityQueue<Arc> pq=new PriorityQueue<Arc>(100,new Comparator<Arc>(){  
  532.             public int compare(Arc a,Arc b){  
  533.                 if(a.weight>b.weight)return 1;  
  534.                 else return -1;  
  535.             }  
  536.         });  
  537.         for(int i=0;i<g.vertexs.size();i++){  
  538.             Arc p=g.vertexs.get(i).firstArc;  
  539.             while(p!=null){  
  540.                 pq.add(p);  
  541.                 p=p.nextArc;  
  542.             }  
  543.         }  
  544.         DisjSets ds=new DisjSets(100);  
  545.         Arc edge;  
  546.         int u,v;  
  547.         while(edgesAccept<g.vertexs.size()-1){  
  548.             edge=pq.poll();  
  549.             u=edge.vex;  
  550.             v=edge.adjVex;  
  551.             int uset=ds.find(u);  
  552.             int vset=ds.find(v);  
  553.             if(uset!=vset){  
  554.                 edgesAccept++;  
  555.                 ds.union(u,v);  
  556.                 minTree.add(edge);  
  557.                 ans+=edge.weight;  
  558.             }  
  559.         }  
  560.         return ans;  
  561.     }  
  562.     //prime  
  563.     public void prime(Graph<AnyType> g){  
  564.         for(int i=0;i<g.vertexs.size();i++){  
  565.             g.vertexs.get(i).primDist=INF;  
  566.             g.vertexs.get(i).primVis=false;  
  567.         }  
  568.         g.vertexs.get(0).primDist=0;  
  569.         int count=0;  
  570.         for(int i=0;i<g.vertexs.size();i++){  
  571.             int min=INF;  
  572.             int v=0;  
  573.             for(int j=0;j<g.vertexs.size();j++)  
  574.                 if(g.vertexs.get(j).primVis==false&&g.vertexs.get(i).primDist<min){  
  575.                     min=g.vertexs.get(i).primDist;  
  576.                     v=j;  
  577.                 }  
  578.             g.vertexs.get(v).primVis=true;  
  579.             count+=min;  
  580.             System.out.print(g.vertexs.get(v).data+" ");  
  581.             if(i==g.vertexs.size()-1)  
  582.             {  
  583.                 System.out.println("\n最小生成树的值是:"+count);  
  584.                 break;  
  585.             }  
  586.             for(int j=0;j<g.vertexs.size();j++)  
  587.                 if(g.vertexs.get(j).primVis==false&&weigthWith(v,j)!=-1)  
  588.                     if(g.vertexs.get(j).primDist>weigthWith(v,j))  
  589.                         g.vertexs.get(j).primDist=weigthWith(v,j);  
  590.         }  
  591.     }  
  592.         public void Floyd(){  
  593.             int[][] adjacencyMartix=getAdjacencyMatrix();  
  594.             for(int i=0;i<adjacencyMartix.length;i++)  
  595.                 for(int j=0;j<adjacencyMartix[i].length;j++)  
  596.                     if(adjacencyMartix[i][j]==0)  
  597.                         adjacencyMartix[i][j]=INF;  
  598.             for(int k=0;k<adjacencyMartix.length;k++)  
  599.                 for(int i=0;i<adjacencyMartix.length;i++)  
  600.                     for(int j=0;j<adjacencyMartix[i].length;j++)  
  601.                         if(i!=j&&adjacencyMartix[i][k]+adjacencyMartix[k][j]<adjacencyMartix[i][j])  
  602.                             adjacencyMartix[i][j]=adjacencyMartix[i][k]+adjacencyMartix[k][j];  
  603.             for(int i=0;i<adjacencyMartix.length;i++){  
  604.                 System.out.print("点"+i+"到其它点的最短距离是：");  
  605.                 for(int j=0;j<adjacencyMartix[i].length;j++)  
  606.                     if(adjacencyMartix[i][j]==INF)  
  607.                             System.out.print("不存在  ");  
  608.                     else System.out.print(adjacencyMartix[i][j]+"  ");  
  609.                 System.out.println();  
  610.             }  
  611.     }  
  612. }  

[java]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. package GraphDemo;  
  2.   
  3.   
  4. import java.util.ArrayList;  
  5. import java.util.LinkedList;  
  6. import java.util.List;  
  7. import java.util.Scanner;  
  8. public class Test{  
  9.     public static void main(String args[]){  
  10.         Scanner cin=new Scanner(System.in);  
  11.         int INF=0xfffff;  
  12.         //建图  
  13.         System.out.println("请输入要建的图的类型：\n1:有向图  2：无向图  3：有向网  4：无向网");  
  14.         int type=cin.nextInt();  
  15.         System.out.println("请输入节点个数和边的条数：");  
  16.         int vnum=cin.nextInt();  
  17.         int anum=cin.nextInt();  
  18.         Graph<String>graph =new Graph<String>(type,vnum,anum);  
  19.         List<String>v=new ArrayList<String>();  
  20.         List<Integer> a=new ArrayList<Integer>();  
  21.         List<Integer> b=new ArrayList<Integer>();  
  22.         List<Integer> x=new ArrayList<Integer>();  
  23.         System.out.println("请输入"+vnum+"个节点：");  
  24.         for(int i=0;i<vnum;i++)  
  25.             v.add(cin.next());  
  26.         if(type==3||type==4)  
  27.             System.out.println("请输入"+anum+"条边及其权值：");  
  28.         else System.out.println("请输入"+anum+"条边：");  
  29.         for(int i=0;i<anum;i++){  
  30.             a.add(cin.nextInt());  
  31.             b.add(cin.nextInt());  
  32.             if(type==3||type==4)  
  33.                 x.add(cin.nextInt());  
  34.             else x.add(1);  
  35.         }  
  36.         graph.createGraph(type,v,a,b,x);  
  37.         //邻接表转换为邻接矩阵  
  38.         System.out.println("邻接表转换为邻接矩阵是：");  
  39.         graph.printAdjacencyMatrix();  
  40.         for(int i=0;i<graph.vertexs.size();i++)  
  41.             graph.vertexs.get(i).vis=false;  
  42.         //增加顶点  
  43.         /*System.out.println("请输入要增加顶点的个数："); 
  44.         int addnum=cin.nextInt(); 
  45.         System.out.println("请输入顶点："); 
  46.         for(int i=0;i<addnum;i++) 
  47.             graph.insertVertex(cin.next()); 
  48.         //增加边 
  49.         System.out.println("请输入要增加边的条数："); 
  50.         int addarc=cin.nextInt(); 
  51.         int ss[]=new int [100]; 
  52.         int ee[]=new int [100]; 
  53.         System.out.println("请输入边的信息："); 
  54.         for(int i=0;i<addarc;i++){ 
  55.             ss[i]=cin.nextInt(); 
  56.             ee[i]=cin.nextInt(); 
  57.         } 
  58.         graph.addEdege(ss,ee,addarc); 
  59.         //删除点 
  60.         System.out.println("请输入要删除的点的个数："); 
  61.         int delenum=cin.nextInt(); 
  62.         System.out.println("请输入要删除点的信息："); 
  63.         for(int i=0;i<delenum;i++) 
  64.             graph.delete(cin.next()); 
  65.         //删除边 
  66.         System.out.println("请输入要删除边的条数："); 
  67.         int delearc=cin.nextInt(); 
  68.         System.out.println("请输入要删除边的信息："); 
  69.         for(int i=0;i<delearc;i++) 
  70.             graph.removeEdege(cin.nextInt(),cin.nextInt()); 
  71.         //DFS 
  72.         int count=0; 
  73.         System.out.println("图的深度优先遍历结果是："); 
  74.         for(int i=0;i<graph.vertexs.size();i++) 
  75.             if(graph.vertexs.get(i).vis==false){ 
  76.                 graph.DFS(i); 
  77.                 count++; 
  78.             } 
  79.         for(int i=0;i<graph.vertexs.size();i++) 
  80.             graph.vertexs.get(i).vis=false; 
  81.         System.out.println(); 
  82.         //BFS 
  83.         System.out.println("图的广度优先遍历结果是："); 
  84.         for(int i=0;i<graph.vertexs.size();i++) 
  85.             if(graph.vertexs.get(i).vis==false){ 
  86.                 graph.BFS(i); 
  87.             } 
  88.         for(int i=0;i<graph.vertexs.size();i++) 
  89.             graph.vertexs.get(i).vis=false; 
  90.         System.out.println(); 
  91.         System.out.println("DFS生成树和BFS生成树，请输入要遍历的点的编号："); 
  92.         //DFS生成树 
  93.         int startnum=cin.nextInt(); 
  94.         System.out.println("图的深度优先生成树："); 
  95.         graph.DFSTree(startnum); 
  96.         System.out.println(); 
  97.         //BFS生成树 
  98.         System.out.println("图的广度优先生成树："); 
  99.         graph.preOrderTree(); 
  100.         System.out.println(); 
  101.         //判断联通分量的个数 
  102.         System.out.println("图的连通分量的个数是："+count); 
  103.         //判断是否存在环 
  104.         //判断有向图是否存在环 
  105.         if(type==1){ 
  106.             for(int i=0;i<graph.vertexs.size();i++){ 
  107.                 graph.vertexs.get(i).inDegree=graph.inDegree(i); 
  108.                 graph.vertexs.get(i).outDegree=graph.outDegree(i); 
  109.             } 
  110.             if(graph.isDGCircle()) 
  111.                 System.out.println("不存在环。"); 
  112.             else 
  113.                 System.out.println("存在环"); 
  114.         } 
  115.         //判断无向图是否存在环 
  116.         else if(type==2){ 
  117.             if(graph.UDGCircle()) 
  118.                 System.out.println("不存在环。"); 
  119.             else 
  120.                 System.out.println("存在环"); 
  121.         } 
  122.         for(int i=0;i<graph.vertexs.size();i++) 
  123.             graph.vertexs.get(i).vis=false; 
  124.         //判断u到v是否存在路径 
  125.         System.out.println("请输入u和v判断，u->v是否存在路径"); 
  126.         if(graph.isURouteV(graph,cin.nextInt(),cin.nextInt())) 
  127.             System.out.println("u到v存在路径。"); 
  128.         else System.out.println("u到v不存在路径。"); 
  129.         for(int i=0;i<graph.vertexs.size();i++) 
  130.             graph.vertexs.get(i).vis=false; 
  131.         //求一条u到v的路径 
  132.         System.out.println("请输入u和v并求出u->v的一条简单路径"); 
  133.         LinkedList<Integer> g=graph.oneURouteV(graph,cin.nextInt(),cin.nextInt()); 
  134.         for(int i=g.size()-1;i>=0;i--) 
  135.             System.out.print(graph.vertexs.get(g.get(i)).data+" "); 
  136.         System.out.println(); 
  137.         for(int i=0;i<graph.vertexs.size();i++) 
  138.             graph.vertexs.get(i).vis=false; 
  139.         //求u到v的所有路径 
  140.         System.out.println("请输入u和v并求出u->v的所有路径"); 
  141.         graph.allURouteV(graph,cin.nextInt(),cin.nextInt()); 
  142.         for(int i=0;i<graph.vertexs.size();i++) 
  143.             graph.vertexs.get(i).vis=false;*/  
  144.         //Dijkstra  
  145.         System.out.println("Dijkstra算法\n请输入起点：");  
  146.         int startDij=cin.nextInt(),num=0;  
  147.         graph.Dijkstra(graph,graph.vertexs.get(startDij),startDij);  
  148.         for(int i=0;i<graph.vertexs.size();i++)  
  149.             if(graph.vertexs.get(i).dist!=INF&&i!=startDij){  
  150.                 graph.printPath(graph,startDij,i);  
  151.                 graph.printPath(startDij,i,++num);  
  152.             }  
  153.                   
  154.         System.out.println("点"+startDij+"到其它点的最短路径分别是:");  
  155.         for(int i=0;i<graph.vertexs.size();i++)  
  156.             if(graph.vertexs.get(i).dist!=INF)  
  157.                 System.out.println("到点"+i+"的最短距离是："+graph.vertexs.get(i).dist);  
  158.             else System.out.println("到点"+i+"不存在最短距离。");  
  159.         for(int i=0;i<graph.vertexs.size();i++)  
  160.             graph.vertexs.get(i).vis=false;  
  161.         //Floyd  
  162.         System.out.println("Floyd算法");  
  163.         graph.Floyd();  
  164.         //Prime  
  165.         System.out.println("Prime算法");  
  166.         graph.prime(graph);  
  167.         System.out.println();  
  168.         for(int i=0;i<graph.vertexs.size();i++)  
  169.             graph.vertexs.get(i).vis=false;  
  170.         //Kruskal  
  171.         System.out.println("Kruskal算法");  
  172.         int ans=graph.Kruskal(graph);  
  173.         System.out.println("Kruskal求得的最小生成树结果是： "+ans);  
  174.     }  
  175. }  

这篇关于数据结构图--课程设计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1000502。

相关文章

Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2