2013级数据结构实验代码7vc6可直接运行.doc

一、实验目的掌握图的基本概念，描述方法；遍历方法。二、实验内容1、创建图类。二叉树的存储结构使用邻接矩阵或链表。2、提供操作:遍历、BFS、DFS3、对建立好的图，执行上述各操作。4、输出生成树。1、输出最小生成树。三、最小生成树的思想(1)、2个for循环都是从2开始的，因为一般我们默认开始就把第一个节点加入生成树，因此之后不需要再次寻找它。( 2)、lowcosti记录的是以节点i为终点的最小边权值。初始化时因为默认把第一个节点加入生成树，因此lowcosti = graph1i，即最小边权值就是各节点到1号节点的边权值中最小的。( 3)msti记录的是lowcosti对应的起点，这样有起点，有终点，即可唯一确定一条边了。初始化时msti = 1，即每条边都是从1号节点出发。四、程序代码#include using namespace std;/队列template class Nodepublic:Node()virtual Node()T data;Node *link;templateclass LinkedQueuepublic:LinkedQueue();virtual LinkedQueue();bool IsEmpty() constreturn (front)?false:true);LinkedQueue& Add(const T& x);LinkedQueue& Delete(T& x);public:Node *front;Node *rear;template LinkedQueue:LinkedQueue()front=rear=0;template LinkedQueue:LinkedQueue()Node *next;while(front)next=front-link;delete front;front=next;template LinkedQueue& LinkedQueue:Add(const T& x)Node *p=new Node;p-data=x;p-link=0;if(front)rear-link=p;else front=p;rear=p;return *this;template LinkedQueue& LinkedQueue:Delete(T& x)if(IsEmpty()return *this;x=front-data;Node *p=front;front=front-link;delete p;return *this;/加权有向图template class AdjacencyWDigraphpublic:AdjacencyWDigraph(int Vertices = 10,T noEdge=0);virtual AdjacencyWDigraph()Delete2DArray(a,n+1);bool Exist(int i,int j) const;int Edges() const return e;int Vertices() const return n;AdjacencyWDigraph& Add(int i,int j ,const T& w);AdjacencyWDigraph& Delete(int i,int j);int OutDegree(int i) const;int InDegree(int i) const;void Make2DArray(T * &x,int rows,int cols);void Delete2DArray(T * &x,int rows);/遍历void InitializePos()pos=new intn+1;void DeactivatePos()delete pos;int Begin(int i);int NextVertex(int i);/宽度优先搜索void BFS(int v,int reach,int label);/深度优先搜索void DFS(int v,int reach,int label);void dfs(int v,int reach,int label);public:T NoEdge;int n;int e;T *a;int *pos;template AdjacencyWDigraph:AdjacencyWDigraph(int Vertices ,T noEdge)n = Vertices;e = 0;NoEdge = noEdge;Make2DArray(a,n+1,n+1);for(int i =1;i = n;i+)for(int j =1;j =n;j+)aij = NoEdge;template bool AdjacencyWDigraph:Exist(int i,int j) constif(i1 | jn | jn | aij=NoEdge)return false;return true;template AdjacencyWDigraph& AdjacencyWDigraph:Add(int i,int j ,const T&w)if(i1 | jn | jn | i=j | aij!=NoEdge)coutzzzzzzzzzzzzzzzzzzzzzzzendl;aij = w;e+;cout aij=aijendl;return *this;template AdjacencyWDigraph& AdjacencyWDigraph:Delete(int i,int j)if(i1 | jn | jn | aij=NoEdge)throw BadInput();aij =NoEdge;e-;return *this;template int AdjacencyWDigraph:OutDegree(int i) constif(in)coutxxxxxxxxxxxxxxxxxxxxxxxxxxendl;int sum=0;for(int j=1;j=n;j+)if(aij !=NoEdge)sum+;return sum;template int AdjacencyWDigraph:InDegree(int i) constif(in) throw BadInput();int sum=0;for(int j=1;j=n;j+)if(aji !=NoEdge)sum+;return sum;template void AdjacencyWDigraph:Make2DArray(T * &x,int rows,int cols)x=new T * rows;for(int i=0;irows;i+)xi=new int cols;template void AdjacencyWDigraph:Delete2DArray(T * &x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;/遍历template int AdjacencyWDigraph:Begin(int i)if(in)coutqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqendl;for(int j=1;j=n;j+)if(aij != NoEdge)posi=j;return j;posi=n+1;return 0;template int AdjacencyWDigraph:NextVertex(int i)if(in)coutsassssssssssssssssssssssssssssssssendl;for(int j=posi+1;j=n;j+)if(aij != NoEdge)posi=j;return j;posi=n+1;return 0;/宽度优先搜索template void AdjacencyWDigraph:BFS(int v,int reach,int label)LinkedQueue Q;InitializePos();reachv=label;Q.Add(v);while(!Q.IsEmpty()int w;Q.Delete(w);cout w ;int u=Begin(w);while(u)if(reachu !=label)Q.Add(u);reachu=label;u=NextVertex(w);DeactivatePos();/深度优先搜索template void AdjacencyWDigraph:DFS(int v,int reach,int label)InitializePos();dfs(v,reach,label);DeactivatePos();template void AdjacencyWDigraph:dfs(int v,int reach,int label)coutv ;reachv=label;int u=Begin(v);while(u)if(reachu !=label)dfs(u,reach,label);u=NextVertex(v);/加权无向图template class AdjacencyWGraph : public AdjacencyWDigraphpublic:AdjacencyWGraph(int Vertices = 10,T noEdge=0):AdjacencyWDigraph(Vertices,noEdge)AdjacencyWGraph& Add(int i,int j ,const T& w)AdjacencyWDigraph:Add(i,j,w);aji=w;cout aji=wendl;return *this;AdjacencyWGraph& Delete(int i,int j)AdjacencyWDigraph:Delete(i,j);aji=NoEdge;return *this;int Degree(int i) const return OutDegree(i);#define INF 999999 ;void Prim(int n, int *c)int *lowcost;int *closest;bool *s;lowcost = new intn;closest = new intn;s = new booln;s1 = true;for(int i=1;i=n;i+)lowcosti = c1i;closesti=1;si = false;cout最小生成树为:endl;for(i=1;in;i+)int min = INF;int j=1;for(int k=2;k=n;k+)if(lowcostkmin) & (!sk)min=lowcostk;j=k;coutclosestj jendl;sj=true;for(k=2;k=n;k+)if(cjklowcostk) & (!sk)lowcostk = cjk;closestk = j;void main()/初始一个加权有向图cout建立加权有向图：endl;int n1,n2,a,b,c;coutn1n2;AdjacencyWDigraph graph(n1,0);for(int i=1;i=n2;i+)cout输入第iabc;graph.Add(a,b,c);/遍历graph.InitializePos();cout遍历：endl;cout遍历所有从顶点i开始的下一顶点：（输入1n1nn;x = graph.Begin(nn);cout xendl;x = graph.NextVertex(nn);while(x!=0)coutxendl;x = graph.NextVertex(nn);/宽度优先搜索cout宽度优先搜索: endl;int reach26;graph.BFS(1,reach2,9);coutendl;/深度优先搜索cout深度优先搜索：endl;int reach16;graph.DFS(1,reach1,9);coutendl;/最小生成树/cout建立加权无向图：endl;int nn1,nn2,a1,b1,c1;coutnn1nn2;#define INF 999999AdjacencyWGraph graph1(nn1,INF);for(int i1=1;i1=nn2;i1+)cout输入第i1a1b1c1;graph1.Add(a1,b1,c1);graph1.Prim(nn1,graph1.a);关于最小生成树的算法我使用的是Prim算法最小生成树之Prim算法1、生成树的概念 连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。 生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。2、最小生成树的性质 用哲学的观点来说，每个事物都有自己特有的性质，那么图的最小生成树也是不例外的。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。3、构造最小生成树，要解决以下两个问题：( 1).尽可能选取权值小的边，但不能构成回路（也就是环）。(2).选取n-1条恰当的边以连接网的n个顶点。求最小生成树的算法一般都使用贪心策略，有Prim算法和Krusal算法等。普里姆算法的基本思想：1）清空生成树，任取一个顶点加入生成树；2）在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树；3）重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树。即:从连通网络N = V, E 中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点v加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点v加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。编写程序:对于如下一个带权无向图，给出节点个数以及所有边权值，用Prim算法求最小生成树。代码的注释我写得很详细，方便理解，有几点需要说明一下。(1)、2个for循环都是从2开始的，因为一般我们默认开始就把第一个节点加入生成树，因此之后不需要再次寻找它。( 2)、lowcosti记录的是以节点i为终点的最小边权值。初始化时因为默认把第一个节点加入生成树，因此lowcosti = graph1i，即最小边权值就是各节点到1号节点的边权值中最小的。( 3)、msti记录的是lowcosti对应的起点，这样有起点，有终点，即可唯一确定一条边了。初始化时msti = 1，即每条边都是从1号节点出发。输入数据:7 11A B 7A D 5B C 8B D 9B E 7C E 5D E 15D F 6E F 8E G 9F G 11输出:A - D : 5D - F : 6A - B : 7B - E : 7E - C : 5E - G : 9Total:39最小生成树Prim算法朴素版java语言实现 代码如下import java.util.*;public class Main static int MAXCOST=Integer.MAX_VALUE;static int Prim(int graph, int n)int lowcost=new intn+1;int mst=new intn+1;int min, minid, sum = 0;for (int i = 2; i = n; i+)lowcosti = graph1i;msti = 1;mst1 = 0;for (int i = 2; i = n; i+)min = MAXCOST;minid = 0;for (int j = 2; j = n; j+)if (lowcostj min & lowcostj != 0)min = lowcostj;minid = j;System.out.printf(%c - %c : %dn, mstminid + A - 1, minid + A - 1, min);sum += min;lowcostminid = 0;for (int j = 2; j = n; j+)if (graphminidj lowcostj)lowcostj = graphminidj;mstj = minid;return sum;public static void main(String args)Scanner sc=new Scanner(System.in);intcost;char chx, chy;int n=sc.nextInt();/节点int m=sc.nextInt();/边数int graph=new intn+1n+1;for (int i = 1; i = n; i+)for (int j = 1; j = n; j+)graphij = MAXCOST;for (int k = 0; k m; k+)chx=sc.next().charAt(0);chy=sc.next().charAt(0);cost=sc.nextInt();int i = chx - A + 1;int j = chy - A + 1;graphij = cost;graphji = cost;cost = Prim(graph, n);System.out.println(Total:+cost);#include using namespace std;/队列template class Node public:Node()virtual Node()T data;Node *link;templateclass LinkedQueuepublic:LinkedQueue();virtual LinkedQueue();bool IsEmpty() constreturn (front)?false:true);LinkedQueue& Add(const T& x);LinkedQueue& Delete(T& x);public:Node *front;Node *rear;template LinkedQueue:LinkedQueue()front=rear=0;template LinkedQueue:LinkedQueue()Node *next;while(front)next=front-link;delete front;front=next;template LinkedQueue& LinkedQueue:Add(const T& x)Node *p=new Node;p-data=x;p-link=0;if(front)rear-link=p;else front=p;rear=p;return *this;template LinkedQueue& LinkedQueue:Delete(T& x)if(IsEmpty()return *this;x=front-data;Node *p=front;front=front-link;delete p;return *this;/加权有向图template class AdjacencyWDigraphpublic:AdjacencyWDigraph(int Vertices = 10,T noEdge=0);virtual AdjacencyWDigraph()Delete2DArray(a,n+1);bool Exist(int i,int j) const;int Edges() const return e;int Vertices() const return n;AdjacencyWDigraph& Add(int i,int j ,const T& w);AdjacencyWDigraph& Delete(int i,int j);int OutDegree(int i) const;int InDegree(int i) const;void Make2DArray(T * &x,int rows,int cols);void Delete2DArray(T * &x,int rows);/遍历void InitializePos()pos=new intn+1;void DeactivatePos()delete pos;int Begin(int i);int NextVertex(int i);/宽度优先搜索void BFS(int v,int reach,int label);/深度优先搜索void DFS(int v,int reach,int label);void dfs(int v,int reach,int label);public:T NoEdge;int n;int e;T *a;int *pos;template AdjacencyWDigraph:AdjacencyWDigraph(int Vertices ,T noEdge)n = Vertices;e = 0;NoEdge = noEdge;Make2DArray(a,n+1,n+1);for(int i =1;i = n;i+)for(int j =1;j =n;j+)aij = NoEdge;template bool AdjacencyWDigraph:Exist(int i,int j) constif(i1 | jn | jn | aij=NoEdge)return false;return true;template AdjacencyWDigraph& AdjacencyWDigraph:Add(int i,int j ,const T&w)if(i1 | jn | jn | i=j | aij!=NoEdge)coutzzzzzzzzzzzzzzzzzzzzzzzendl;aij = w;e+;cout aij=aijendl;return *this;template AdjacencyWDigraph& AdjacencyWDigraph:Delete(int i,int j)if(i1 | jn | jn | aij=NoEdge)throw BadInput();aij =NoEdge;e-;return *this;template int AdjacencyWDigraph:OutDegree(int i) constif(in)coutxxxxxxxxxxxxxxxxxxxxxxxxxxendl;int sum=0;for(int j=1;j=n;j+)if(aij !=NoEdge)sum+;return sum;template int AdjacencyWDigraph:InDegree(int i) constif(in) throw BadInput();int sum=0;for(int j=1;j=n;j+)if(aji !=NoEdge)sum+;return sum;template void AdjacencyWDigraph:Make2DArray(T * &x,int rows,int cols)x=new T * rows;for(int i=0;irows;i+)xi=new int cols;template void AdjacencyWDigraph:Delete2DArray(T * &x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;/遍历template int AdjacencyWDigraph:Begin(int i)if(in)coutqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqendl;for(int j=1;j=n;j+)if(aij != NoEdge)posi=j;return j;posi=n+1;return 0;template int AdjacencyWDigraph:NextVertex(int i)if(in)coutsassssssssssssssssssssssssssssssssendl;for(int j=posi+1;j=n;j+)if(aij != NoEdge)posi=j;return j;posi=n+1;return 0;/宽度优先搜索template void AdjacencyWDigraph:BFS(int v,int reach,int label)LinkedQueue Q;InitializePos();reachv=label;Q.Add(v);while(!Q.IsEmpty()int w;Q.Delete(w);cout w ;int u=Begin(w);while(u)if(reachu !=label)Q.Add(u);reachu=label;u=NextVertex(w);DeactivatePos();/深度优先搜索template void AdjacencyWDigraph:DFS(int v,int reach,int label)InitializePos();dfs(v,reach,label);DeactivatePos();template void AdjacencyWDigraph:dfs(int v,int reach,int label)coutv ;reachv=label;int u=Begin(v);while(u)if(reachu !=label)dfs(u,reach,label);u=NextVertex(v);/加权无向图template class AdjacencyWGraph : public AdjacencyWDigraphpublic:AdjacencyWGraph(int Vertices = 10,T noEdge=0):AdjacencyWDigraph(Vertices,noEdge)AdjacencyWGraph& Add(int i,int j ,const T& w)AdjacencyWDigr