/****************************************
定义采用邻接矩阵存储的图结构
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法
****************************************************/
#include <iostream>
#include <math.h>
#include <limits.h>
#include <Queue>
#define UNVISITED 1;
#define VISITED 0;
using namespace std;
template <class T>
class MinHeap
{
private:
T * heapArray;
int CurrentSize;
int MaxSize;
void BuildHeap()
{
for(int i=CurrentSize/2-1;i>0;i--)
SiftDown(i);
}
public:
MinHeap(const int n)
{
if (n<=0) return;
CurrentSize=0;
MaxSize=n;
heapArray=new T [MaxSize];
BuildHeap();
}
~MinHeap()
{
delete []heapArray;
}
bool isLeaf(int pos)
{
return((pos>=CurrentSize/2)&&(pos<CurrentSize));
}
int leftChild(int pos)const
{
return 2*pos+1;
}
int rightChild(int pos)const
{
return 2*pos+2;
}
int parent(int pos)const
{
return (pos-1)/2;
}
bool Remove(int pos)//, T& node)//删除指定下标的元素
{
if ((pos < 0) || (pos >= CurrentSize)) return false;
heapArray[pos] = heapArray[- -CurrentSize]; // 用最后的元素值替代删除位置的元素
if (heapArray[parent(pos)] > heapArray[pos])
SiftUp(pos); // 当前元素小于父结点,需要上升调整
else SiftDown(pos); // 当前元素大于父结点,向下筛
return true;
}
bool Insert(const T & newNode)
{
if (CurrentSize == MaxSize) return false; // 堆空间已经满
heapArray[CurrentSize] = newNode;
SiftUp(CurrentSize); // 向上调整
CurrentSize++;
return true;
}
T RemoveMin()
{
T item;
if (CurrentSize == 0)
{
cout<< "Can't Delete";
}
else
{
item=heapArray[0];
heapArray[0]=heapArray[CurrentSize-1];
heapArray[--CurrentSize]=item;
if (CurrentSize>1)
SiftDown(0);
}
return item;
}
void SiftUp(int pos)
{
int tempposition=pos;
T temp=heapArray[tempposition];
while((tempposition>0)&&(heapArray[parent(tempposition)]>temp))
{
heapArray[tempposition]=heapArray[parent(tempposition)];
tempposition=parent(tempposition);
}
heapArray[tempposition]=temp;
}
void SiftDown(int pos)
{
int i=pos;
int j=leftChild(i);
T temp=heapArray[i];
while(j<CurrentSize)
{
if((j<CurrentSize-1)&&heapArray[j]>heapArray[j+1])
j++;
if(temp>heapArray[j])
{
heapArray[i]=heapArray[j];
i=j;
j=leftChild(j);
}
else break;
}
heapArray[i]=temp;
}
void print()
{
for(int i=0;i<CurrentSize;i++)
{
cout<<heapArray[i]<<' ';
}
cout<<endl;
}
bool IsEmpty()
{
return CurrentSize==0;
}
};
class Edge
{
public:
int from;
int to;
int weight;
Edge()
{
from=to=-1;
weight=0;
}
Edge(int st,int en, int w)
{
from=st;
to=en;
weight=w;
}
bool operator >(Edge oneEdge)
{
return weight>oneEdge.weight;
}
bool operator <(Edge oneEdge)
{
return weight<oneEdge.weight;
}
};
class Graph
{
public:
int numVertex;//图的顶点个数
int numEdge;//图的边的数目
int *Mark;//保存有图的顶点是否被访问过的数组
int *Indegree;//保存有图的顶点的入度的数组
Graph(int verticesNum)
{
numVertex=verticesNum;
numEdge=0;
Mark=new int [numVertex];
Indegree=new int [numVertex];
for(int i=0;i<numVertex;i++)
{
Mark[i]=UNVISITED;
Indegree[i]=0;
}
}
~Graph()
{
delete [] Mark;
delete [] Indegree;
}
virtual Edge FirstEdge(int oneVertex)=0;//返回与顶点关联的第一条边
virtual Edge NextEdge(Edge oneEdge)=0;
virtual void setEdge(int from,int to,int weight)=0;
virtual void delEdge(int from,int to)=0;
void visit(int i)
{
cout<<i+1<<' ';
}
int VerticesNum()
{
return numVertex;
}
int EdgesNum()
{
return numEdge;
}
bool IsEdge(Edge oneEdge)
{
if((oneEdge.weight > 0)&&(oneEdge.weight < INT_MAX)&&(oneEdge.to >= 0))return true;
else return false;
}
int FromVertex(Edge oneEdge)
{
return oneEdge.from;
}
int ToVertex(Edge oneEdge)
{
return oneEdge.to;
}
int Weight(Edge oneEdge)
{
return oneEdge.weight;
}
void GDFS(int v)
{
Mark[v]=VISITED;
visit(v);
for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))
{
if(Mark[ToVertex(e)]==1)
GDFS(ToVertex(e));
}
}
void DFSTraverse()
{
cout<<"深度优先搜索DFS:"<<endl;
for(int i=0;i<VerticesNum();i++)
{
Mark[i]=1;
}
for(int r=0;r<VerticesNum();r++)
{
if(Mark[r]==1)
GDFS(r);
}
cout<<endl;
}
void GBFS(int v)
{
queue<int> Q;
Mark[v]=0;
visit(v);
Q.push(v);
while(!Q.empty())
{
v = Q.front();
Q.pop();
for(Edge e = FirstEdge(v);IsEdge(e); e = NextEdge(e))
{
if(Mark[ToVertex(e)] == 1)
{
visit(ToVertex(e));
Mark[ToVertex(e)] = 0;
Q.push(ToVertex(e));
}
}
}
}
void BFSTraverse()
{
cout<<endl<<"广度优先搜索BFS:"<<endl;
int i=0;
for(i=0;i<VerticesNum();i++)
{
Mark[i] = 1;
}
for(i=0;i<VerticesNum();i++)
{
if(Mark[i] == 1)
GBFS(i);
}
cout<<endl;
}
int StartVertex(Edge oneEdge){//返回边的始点
return oneEdge.from;
}
int EndVertex(Edge oneEdge){//返回边的终点
return oneEdge.to;
}
};
class AdjGraph : public Graph
{
private:
int **matrix;
public:
AdjGraph(int verticesNum):Graph(verticesNum)
{
int i,j;
matrix=(int **)new int *[numVertex];
for(i=0;i<numVertex;i++)
matrix[i]=new int [numVertex];
for(i=0;i<numVertex;i++)
for(j=0;j<numVertex;j++) matrix[i][j]=0;
}
~AdjGraph()
{
for(int i=0;i<numVertex;i++) delete[]matrix[i];
delete []matrix;
}
Edge FirstEdge(int oneVertex)
{
Edge myEdge;
myEdge.from=oneVertex;
myEdge.to=-1;
for(int i=0;i<numVertex;i++)
{
if(matrix[oneVertex][i]!=0)
{
myEdge.to=i;
myEdge.weight=matrix[oneVertex][i];
break;
}
}
return myEdge;
}
Edge NextEdge(Edge preEdge)
{
Edge myEdge;
myEdge.from=preEdge.from;
myEdge.to=-1;
for(int i=preEdge.to+1;i<numVertex;i++)
{
if(matrix[preEdge.from][i]!=0)
{
myEdge.to=i;
myEdge.weight=matrix[preEdge.from][i];
break;
}
}
return myEdge;
}
void setEdge(int from,int to,int weight)
{
if(matrix[from][to]<=0)
{
numEdge++;
Indegree[to]++;
}
mat
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
.rar (42个子文件)
★图综合实现
★图综合实现.v11.suo 21KB
★图综合实现
★图综合实现.vcxproj.filters 941B
★图综合实现.vcxproj 4KB
Debug
link.142368-rc.write.1.tlog 2B
★图综合实现.lastbuildstate 84B
vc110.idb 259KB
CL.write.1.tlog 246B
CL.read.1.tlog 7KB
link.142368-cvtres.write.1.tlog 2B
link.23788-cvtres.write.1.tlog 2B
link.142368-rc.read.1.tlog 2B
link.23788-cvtres.read.1.tlog 2B
link.143140-cvtres.write.1.tlog 2B
link.143140-rc.read.1.tlog 2B
link.23788-rc.read.1.tlog 2B
cl.command.1.tlog 546B
link.143140-rc.write.1.tlog 2B
link-cvtres.read.1.tlog 2B
link.23788.write.1.tlog 2B
link.23788.read.1.tlog 2B
link.143140-cvtres.read.1.tlog 2B
link.write.1.tlog 320B
link-rc.write.1.tlog 2B
link.142368.read.1.tlog 2B
link-cvtres.write.1.tlog 2B
link.command.1.tlog 1010B
link-rc.read.1.tlog 2B
link.read.1.tlog 3KB
link.143140.write.1.tlog 2B
vc110.pdb 372KB
源.obj 307KB
link.143140.read.1.tlog 2B
★图综合实现.log 2KB
link.23788-rc.write.1.tlog 2B
link.142368-cvtres.read.1.tlog 2B
link.142368.write.1.tlog 2B
源.cpp 15KB
★图综合实现.sln 921B
★图综合实现.sdf 7.75MB
Debug
★图综合实现.pdb 963KB
★图综合实现.ilk 414KB
★图综合实现.exe 105KB
共 42 条
- 1
资源评论
chenzhuo94319
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功