我转过来了
//AdjMWGraph.h
#include "SeqList.h"
#include "SeqQueue.h"
const int MaxVertices=10;
const int MaxWeight=10000;
class AdjMWGraph
{
private:
SeqList Vertices;
int Edge[MaxVertices][MaxVertices];
int numOfEdges;
public:
AdjMWGraph(const int sz=MaxVertices);
int GarphEmpty()const
{
return Vertices.ListEmpty();}
int NumOfVertices(void){
return Vertices.ListSize();}
int NumOfEdges(void){
return numOfEdges;
}
VerT GetValue(const int i);
int GetWeight(const int v1,const int v2);
void InsertVertex(const VerT &vertex);
void InsertEdge(const int v1,const int v2,int weight);
void DeleteVertex(const int i);
void DeleteEdge(const int v1,const int v2);
int GetFirstNeighbor(const int v);
int GetNextNeighbor(const int v1,const int v2);
void DepthFirstSearch(const int v,int visited[],void vist(VerT item));
void BroadFirstSearch(const int v1,int visited[],void visit(VerT item));
void DepthFirstSearch(void visit(VerT item));
void BroadFirstSearch(void vist(VerT item));
};
AdjMWGraph::AdjMWGraph(const int sz){
for(int i=0;i<sz;i++)
for(int j=0;j<sz;j++)
{
if(i==j)Edge[i][j]=0;
else Edge[i][j]=MaxWeight;
}
numOfEdges=0;
}
VerT AdjMWGraph::GetValue(const int i)
{
if(i<0||i>Vertices.ListSize())
{
cerr<<"参数i越界出错!"<<endl;
exit(1);
}
return Vertices.GetData(i);
}
int AdjMWGraph::GetWeight(const int v1,const int v2){
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()){
exit(1);
}
return Edge[v1][v2];
}
void AdjMWGraph::InsertVertex(const VerT &vertex)
{
Vertices.Insert(vertex,Vertices.ListSize());
}
void AdjMWGraph::InsertEdge(const int v1,const int v2,int weight)
{
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()){
exit(1);
}
Edge[v1][v2]=weight;
numOfEdges++;
}
void AdjMWGraph::DeleteVertex(const int v){
for(int i=0;i<Vertices.ListSize();i++)
for(int j=0;j<Vertices.ListSize();j++)
if((i==v||j==v)&&Edge[i][j]>0&&Edge[i][j]<MaxWeight){
Edge[i][j]=MaxWeight;
numOfEdges--;
}
Vertices.Delete(v);
}
void AdjMWGraph::DeleteEdge(const int v1,const int v2){
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
exit(1);
Edge[v1][v2]=MaxWeight;
numOfEdges--;
}
int AdjMWGraph::GetFirstNeighbor(const int v){
if(v<0||v>Vertices.ListSize())
exit(1);
for(int col=0;col<Vertices.ListSize();col++)
if(Edge[v][col]>0&&Edge[v][col]<MaxWeight)
return col;
return -1;
}
int AdjMWGraph::GetNextNeighbor(const int v1,const int v2){
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
exit(1);
for(int col=v2+1;col<Vertices.ListSize();col++)
if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight)
return col;
return -1;
}
void AdjMWGraph::DepthFirstSearch(const int v,int visited[],void visit(VerT item)){
visit(GetValue(v));
visited[v]=1;
int w=GetFirstNeighbor(v);
while(w!=-1){
if(!visited[w]) DepthFirstSearch(w,visited,visit);
w=GetNextNeighbor(v,w);
}
}
void AdjMWGraph::BroadFirstSearch(const int v,int visited[],void visit(VerT item)){
int u;
int w;
SeqQueue queue;
visit(GetValue(v));
visited[v]=1;
queue.EnQue(v);
while(!queue.IsEmpty()){
u=queue.DeQue();
w=GetFirstNeighbor(v);
while(w!=-1){
if(!visited[w]){
visit(GetValue(w));
visited[w]=1;
queue.EnQue(w);
}
w=GetNextNeighbor(u,w);
}
}
}
void AdjMWGraph::DepthFirstSearch(void visit(VerT item)){
int *visited=new int[NumOfVertices()];
for(int i=0;i<NumOfVertices();i++) visited[i]=0;
for(int i=0;i<NumOfVertices();i++)
if(!visited[i]) DepthFirstSearch(i,visited,visit);
delete []visited;
}
void AdjMWGraph::BroadFirstSearch(void visit(VerT item)){
int *visited=new int[NumOfVertices()];
for(int i=0;i<NumOfVertices();i++) visited[i]=0;
for(int i=0;i<NumOfVertices();i++)
if(!visited[i]) BroadFirstSearch(i,visited,visit);
delete []visited;
}
//Dijkstra.h
void Dijkstra(AdjMWGraph &G,int v0,int distance[],int path[]){
int n=G.NumOfVertices();
int *s=new int[n];
int minDis,i,j,u;
for(i=0;i<n;i++){
distance[i]=G.GetWeight(v0,i);
s[i]=0;
if(i!=v0&&distance[i]<MaxWeight) path[i]=v0;
else path[i]=-1;
}
s[v0]=1;
for(i=1;i<n;i++)
{
minDis=MaxWeight;
for(j=0;j<n;j++)
if(s[j]==0&&distance[j]<minDis){
u=j;
minDis=distance[j];
}
if(minDis==MaxWeight) return;
s[u]=1;
for(j=0;j<n;j++)
if(s[j]==0&&G.GetWeight(u,j)<MaxWeight&&distance[u]+G.GetWeight(u,j)<distance[j]){
distance[j]=distance[u]+G.GetWeight(u,j);
path[j]=u;
}
}
}
//GraphLib.h
struct RowColWeight{
int cow;
int col;
int wieght;
};
void CreatGarph(AdjMWGraph &G,DataType V[],int n,RowColWeight E[],int e){
for(int i=0;i<n;i++) G.InsertVertex(V[i]);
for(int k=0;k<e;k++) G.InsertEdge(E[k].cow,E[k].col,E[k].wieght);
}
void Printchar(char item)
{
cout<<item<<" ";
}
//SeqList.h
#include<iostream>
#include<stdlib.h>
using namespace std;
const int MaxListSize=100;
class SeqList{
DataType data[MaxListSize];
int size;
public:
SeqList(void);
~SeqList(void);
int ListSize(void)const;
int ListEmpty(void)const;
int Find(DataType &item);
DataType GetData(int pos)const;
void Insert(const DataType& item,int pos);
DataType Delete(const int pos);
void ClearList(void);
};
SeqList::SeqList(void):size(0){}
SeqList::~SeqList(void){}
int SeqList::ListSize(void)const{
return size;
}
int SeqList::ListEmpty(void)const{
if(size==0) return 1;
else return 0;
}
int SeqList::Find(DataType &item){
if(size==0) return -1;
int i=0;
while(i<size&&item!=data[i])i++;
return i;
}
DataType SeqList::GetData(int pos)const{
if(pos<0||pos>size-1){
cerr<<"参数pos越界!"<<endl;
exit(1);
}
return data[pos];
}
void SeqList::Insert(const DataType &item,int pos){
if(pos<0||pos>size){
cerr<<"参数越界!"<<endl;
exit(1);
}
if(size==MaxListSize-1){
cerr<<"顺序表已经满!"<<endl;
exit(1);
}
for(int i=size;i>pos;i--)
data[i]=data[i-1];
data[pos]=item;
size++;
}
DataType SeqList::Delete(const int pos)
{
if(size==0)
{
cerr<<"顺序表已空无元素可删!"<<endl;
exit(1);
}
if(pos<0||pos>size-1){
cerr<<"参数越界!"<<endl;
exit(1);
}
DataType temp=data[pos];
for(int i=pos;i<size-1;i++) data[i]=data[i+1];
size--;
return temp;
}
void SeqList::ClearList(){
size=0;
}
//SeqQueue.h
#include<assert.h>
#include<iostream>
using namespace std;
class SeqQueue{
int rear,front;
DataType *element;
int maxsize;
public:
SeqQueue(){rear=front=0;element=new char[100];}
SeqQueue(int ms);
~SeqQueue(){delete []element;}
bool IsEmpty()const{return rear==front;}
bool IsFull()const{return (rear+1)%maxsize==front;}
int Length()const{return (rear-front+maxsize)%maxsize;}
void EnQue(const &data);
DataType DeQue();
DataType GetNum();
};
SeqQueue::SeqQueue(int ms){
maxsize=ms;
element=new char[maxsize];
rear=front=0;
assert(element!=NULL);
}
void SeqQueue::EnQue(const &data){
assert(!IsFull());
rear=(rear+1)%maxsize;
element[rear]=data;
}
DataType SeqQueue::DeQue(){
assert(!IsEmpty());
front=(front+1)%maxsize;
return element[front];
}
DataType SeqQueue::GetNum(){
assert(!IsEmpty());
front=(front+1)%maxsize;
return element[front];
}
