#ifndef _GRAPH_H
#define _GRAPH_H
#define DEFAULT_VERTEX_SIZE 10
typedef struct
{
int x;
int y;
int cost;
}edge;
template<class Type>
class Graph;
class Edge
{
public:
Edge(int num,int c):dest(num),cost(c),link(NULL)
{}
~Edge()
{}
int dest;
Edge* link;
int cost;
};
template<class Type>
class Vertex
{
friend Graph<Type>;
public:
Vertex():data(Type()),adj(NULL)
{}
~Vertex()
{}
private:
Edge *adj;
Type data;
};
template<class Type>
class Graph
{
public:
Graph(int sz=DEFAULT_VERTEX_SIZE)
{
MaxVertices=sz>DEFAULT_VERTEX_SIZE?sz:DEFAULT_VERTEX_SIZE;
NumVertices=NumEdge=0;
NodeTable=new Vertex<Type>[MaxVertices];
}
~Graph()
{
Edge *t;
for(int i=0;i<NumVertices;++i)
{
Edge *w;
t=NodeTable[i].adj;
while(t!=NULL)
{
w=t;
t=t->link;
delete w;
}
}
delete[] NodeTable;
//////
}
int GetPosOfVertex(const Type &v)const
{
for(int i=0;i<NumVertices;++i)
{
if(NodeTable[i].data==v)
return i;
}
return -1;
}
void InsertVertex(const Type &val)
{
if(NumVertices<MaxVertices)
{
NodeTable[NumVertices++].data=val;
}
}
bool InsertEdge(const Type &vertex1, const Type &vertex2,int cost)
{
int v1 = GetPosOfVertex(vertex1);
int v2 = GetPosOfVertex(vertex2);
if(v1==-1 || v2==-1)
return false;
//v1 --> v2
Edge *e = new Edge(v2,cost);
e->link = NodeTable[v1].adj;
NodeTable[v1].adj = e;
//v2 --> v1
e = new Edge(v1,cost);
e->link = NodeTable[v2].adj;
NodeTable[v2].adj = e;
NumEdge++;
return true;
}
/*
bool InsertEdge(const Type &v1,const Type &v2)
{
int V1=GetPosOfVertex(v1);
int V2=GetPosOfVertex(v2);
if(V1==-1||V2==-1)
return false;
//v1-->v2
cout<<"v1: "<<V1<<" v2: "<<V2<<endl;
Edge *s=new Edge(V2);
s->link=NodeTable[V1].adj;
NodeTable[V1].adj=s;
//v2-->v1
Edge *s1=new Edge(V1);
s1->link=NodeTable[V2].adj;
NodeTable[V1].adj=s1;
++NumEdge;
return true;
}
*/
int NumOfVertex()const
{
return NumVertices;
}
int NumOfEdge()const
{
return NumEdge;
}
Type GetValueByIndex(int i)
{
if(i<=NumVertices&&i>=0)
return NodeTable[i].data;
}
int GetFirstNeighbor(const Type &vertex)const
{
int v=GetPosOfVertex(vertex);
if(v==-1)
return -1;
if( NodeTable[v].adj!=NULL)
return NodeTable[v].adj->dest;
else
return -1;
}
int GetNextNeighbor(const Type &vertex1,const Type &vertex2)const
{
int v1=GetPosOfVertex(vertex1);
int v2=GetPosOfVertex(vertex2);
if(v1==-1||v2==-1)
return -1;
if(NodeTable[v1].adj==NULL)
return -1;
Edge *t=NodeTable[v1].adj;
while(t!=NULL&&t->dest!=v2)
t=t->link;
if(t==NULL)
return -1;
else
if(t->link!=NULL)
return t->link->dest;
else
return -1;
}
bool RemoveEdge(const Type &vertex1,const Type &vertex2)
{
int v1=GetPosOfVertex(vertex1);
int v2=GetPosOfVertex(vertex2);
if(v1==-1||v2==-1)
return false;
Edge *t=NodeTable[v1].adj;
Edge *p=t;
while(t!=NULL&&t->dest!=v2)
{
p=t;
t=t->link;
}
if(t==NULL)
return false;
else
{
if(p==t)
{
Edge *w=NodeTable[v1].adj;
NodeTable[v1].adj=NodeTable[v1].adj->link;
delete w;
}
else
{
Edge *w=p->link;
p->link=t->link;
delete w;
}
//
t=p=NodeTable[v2].adj;
while(t->dest!=v1)
{
p=t;
t=t->link;
}
if(t==p)
{
Edge *w=NodeTable[v2].adj;
NodeTable[v2].adj=NodeTable[v2].adj->link;
delete w;
}
else
{
Edge *w=p->link;
p->link=t->link;
delete w;
}
--NumEdge;
return true;
}
}
bool RemoveVertex(const Type &vertex)
{
int v=GetPosOfVertex(vertex);
if(v==-1)
return false;
Edge* t=NodeTable[v].adj;
while(t!=NULL)
{
Edge *p=NodeTable[t->dest].adj;
Edge *p1=p;
while(p!=NULL)
{
while(p->dest!=v)
{
p1=p;
p=p->link;
}
if(p==p1)
{
Edge *w=NodeTable[t->dest].adj;
NodeTable[t->dest].adj=NodeTable[t->dest].adj->link;
delete w;
break;
}
else
{
Edge* w=p1->link;
p1->link=p->link;
delete w;
break;
}
}
p1=t;
t=t->link;
delete p1;
--NumEdge;
}
if(v!=NumVertices-1)
{
NodeTable[v].data=NodeTable[NumVertices-1].data;
NodeTable[v].adj=NodeTable[NumVertices-1].adj;
Edge *t1=NodeTable[NumVertices-1].adj;
while(t1!=NULL)
{
Edge *p3=NodeTable[t1->dest].adj;
while(p3->dest!=NumVertices-1)
p3=p3->link;
p3->dest=v;
t1=t1->link;
}
}
--NumVertices;
return true;
}
void DFSTraverse()//深度遍历
{
bool *visited=new bool[NumVertices];
for(int i=0;i<NumVertices;++i)
visited[i]=false;
for(int i=0;i<NumVertices;++i)
if(!visited[i])
DFS(i,visited);
}
void DFS(int v,bool *&visited)
{
if(v<=-1&&v>=NumVertices)
return ;
visited[v]=true;
cout<<NodeTable[v].data<<" ";
for(int w=GetFirstNeighbor(GetValueByIndex(v));w>=0;w=GetNextNeighbor(GetValueByIndex(v),GetValueByIndex(w)))
if(!visited[w])
DFS(w,visited);
}
void DFSTraverse_1(Type val)
{
bool *visited=new bool[NumVertices];
for(int i=0;i<NumVertices;++i)
visited[i]=false;
int x=GetPosOfVertex(val);
visited[x]=true;
cout<<NodeTable[x].data<<" ";
for(int w=GetFirstNeighbor(val);w>=0;w=GetNextNeighbor(val,GetValueByIndex(w)))
{
if(!visited[w])
{
visited[w]=true;
cout<<NodeTable[w].data<<" ";
}
}
for(int i=0;i<NumVertices;++i)
{
if(!visited[i])
{
visited[i]=true;
cout<<NodeTable[i].data<<" ";
for(int w=GetFirstNeighbor(GetValueByIndex(i));w>=0;w=GetNextNeighbor(GetValueByIndex(i),GetValueByIndex(w)))
if(!visited[w])
{
visited[w]=true;
cout<<NodeTable[w].data<<" ";
}
}
}
}
void BFSTraverse()//广度遍历
{
bool *visited=new bool[NumVertices];
for(int i=0;i<NumVertices;++i)
visited[i]=false;
queue<int> Q;
for(int i=0;i<NumVertices;++i)
{
if(!visited[i])
{
visited[i]=true;
cout<<NodeTable[i].data<<" ";
}
Q.push(i);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
Edge *s=NodeTable[u].adj;
while(s!=NULL)
{
if(!visited[s->dest])
{
visited[s->dest]=true;
cout<<NodeTable[s->dest].data<<" ";
Q.push(s->dest);
}
s=s->link;
}
}
}
}
void BFSTraverse_1(Type v)
{
bool *visited=new bool[NumVertices];
queue<int> Q;
int x=GetPosOfVertex(v);
if(x==-1)
return;
Q.push(x);
cout<<v<<" ";
visited[x]=true;
Edge *s=NodeTable[x].adj;
while(s!=NULL)
{
if(!visited[s->dest])
{
visited[s->dest]=true;
Q.push(s->dest);
cout<<NodeTable[s->dest].data<<" ";
}
s=s->link;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
s=NodeTable[u].adj;
while(s!=NULL)
{
if(!visited[s->dest])
{
visited[s->dest]=true;
cout<<NodeTable[s->dest].data<<" ";
Q.push(s->dest);
}
s=s->link;
}
}
}
void MinSpinTree(Type v)
{
int x=GetPosOfVertex(v);
cout<<v<<"-->"<<endl;
int *adjvertex=new int[NumVertices];
int *lowcost=new int [NumVertices];
for(int i=0;i<NumVertices;++i)
{
if(x!=i)
{
lowcost[i]=10000;
}
else
lowcost[i]=0;
adjvertex[i]=x;
}
Edge* p=NodeTable[x].adj;
while(p!=NULL)
{
lowcost[p->dest]=p->cost;
p=p->link;
}
for(int i=0;i<NumVertices;++i)
cout<<lowcost[i]<<" ";
cout<<endl;
for(int i=1;i<NumVertices;++i)
{
int min=1000;
int min_index;
for(int j=0;j<NumVertices;++j)
{
if(lowcost[j]!=0)
{
if(lowcost[j]<min)
{
min=lowcost[j];
x=j;
}
}
}
cout<<NodeTable[adjvertex[x]].data<<"-->"<<NodeTable[x].data<<":"<<min<<endl;
lowcost[x]=0;
p=NodeTable[x].adj;
while(p!=NULL)
{
if(p->cost!=0&&lowcost[p->dest]>p->cost)
{
lowcost[p->dest]=p->cost;
adjvertex[p->dest]=x;
}
p=p->link;
}
lowcost[x]=0;
// /*
for(int q=0;q<NumVertices;++q)
cout<<lowcost[q]<<" ";
cout<<endl;
//*/
}
}
void MinSpanTree_Kruskal();
void ShowGraph()
{
for(int i=0;i<NumVertices;++i)
{
cout<<i<<" "<<NodeTable[i].data<<" "<<"-->";
Edge* e=NodeTable[i].adj;
while(e!=NULL)
{
cout<<e->dest<<"("<<e->cost<<")"<<"-->";
e=e->link;
}
cout<<"NUL"<<endl;;
}
}
private:
Vertex<Type>*NodeTable;
int MaxVertices;
int NumVertices;
int NumEdge;
};
template<class Type>
void Graph<Type>::MinSpanTree_Kruskal()
{
}
#endif
相关文章
- 6、求最小生成树,普里姆(Prim)算法
- 普里姆算法求图(邻接矩阵存储)的最小生成树
- 有点混乱的普里姆算法求最小生成树
- Java 数据结构-特点： 代表一个队列，通常按照先进先出（FIFO）的顺序操作元素。 实现类： LinkedList, PriorityQueue, ArrayDeque。 堆（Heap） 堆（Heap）优先队列的基础，可以实现最大堆和最小堆。 PriorityQueue<Integer minHeap = new PriorityQueue<>; PriorityQueue<Integer maxHeap = new PriorityQueue<>(Collections.reverseOrder); 树（Trees） Java 提供了 TreeNode 类型，可以用于构建二叉树等数据结构。 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } 图（Graphs） 图的表示通常需要自定义数据结构或使用图库，Java 没有内建的图类。 以上介绍的只是 Java 中一些常见的数据结构，实际上还有很多其他的数据结构和算法可以根据具体问题选择使用。 其他一些说明 以下这些类是传统遗留的，在 Java2 中引入了一种新的框架-集合框架(Collection)，我们后面再讨论。 枚举（Enumeration） 枚举（Enumeration）接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很广。 枚举（The Enumeration）接口定义了一种从数据结构中取回连续元素的方式。 例如，枚举定义了一个叫nextElement 的方法，该方法用来得到一个包含多元素的数据结构的下一个元素。 关于枚举接口的更多信息，请参见枚举（Enumeration）。 位集合（BitSet） 位集合类实现了一组可以单独设置和清除的位或标志。 该类在处理一组布尔值的时候非常有用，你只需要给每个值赋值一"位"，然后对位进行适当的设置或清除，就可以对布尔值进行操作了。 关于该类的更多信息，请参见位集合（BitSet）。 向量（Vector） 向量（Vector）类和传统数组非常相似，但是Vector的大小能根据需要动态的变化。 和数组一样，Vector对象的元素也能通过索引访问。 使用Vector类最主要的好处就是在创建对象的时候不必给对象指定大小，它的大小会根据需要动态的变化。 关于该类的更多信息，请参见向量(Vector) 栈（Stack） 栈（Stack）实现了一个后进先出（LIFO）的数据结构。 你可以把栈理解为对象的垂直分布的栈，当你添加一个新元素时，就将新元素放在其他元素的顶部。 当你从栈中取元素的时候，就从栈顶取一个元素。换句话说，最后进栈的元素最先被取出。 关于该类的更多信息，请参见栈（Stack）。 字典（Dictionary） 字典（Dictionary） 类是一个抽象类，它定义了键映射到值的数据结构。 当你想要通过特定的键而不是整数索引来访问数据的时候，这时候应该使用 Dictionary。 由于 Dictionary 类是抽象类，所以它只提供了键映射到值的数据结构，而没有提供特定的实现。 关于该类的更多信息，请参见字典（ Dictionary）。 Dictionary 类在较新的 Java 版本中已经被弃用（deprecated），推荐使用 Map 接口及其实现类，如 HashMap、TreeMap 等，来代替 Dictionary。
- （原创）最小生成树之Prim（普里姆）算法+代码详解，最懂你的讲解
- 图的最小生成树prim算法模板
- 图的建立(邻接矩阵)+深度优先遍历+广度优先遍历+Prim算法构造最小生成树(Java语言描述)
- 图的生成树（森林）（克鲁斯卡尔Kruskal算法和普里姆Prim算法）、以及并查集的使用
- 无向图的生成树和生成森林算法
- C++ 图进阶系列之 kruskal 和 Prim 算法_图向最小生成树的华丽转身