template<class Type>int Graph<Type>::
InsertArc(int v1,int v2,int w)
{//在图中插入弧<v1,v2>
if(v1>=0&&v1<CurrentNumVertexes){
Arcs[v1][v2]=w;
ArcNode *newnode =new ArcNode(v2,w);
ArcNode *h=VTable[v1].firstarc;
if(h!=NULL){
ArcNode *p=h;
while(h!=NULL&&h->adjvex<v2){
p=h; h=h->nextarc;
}
newnode->nextarc=p->nextarc;
p->nextarc=newnode;
return 1;
}
VTable[v1].firstarc=newnode;
return 1;
}
return -1;
}
template<class Type>int Graph<Type>::
InVertex(Type &v)
{//在图中插入顶点，插入成功则返回1，否则返回0
if(CurrentNumVertexes<MaxVertexes-1){//若顶点表未满
VTable[CurrentNumVertexes].data=v;
VTable[CurrentNumVertexes].firstarc=NULL;
CurrentNumVertexes++; return 1;
}
return -1;
}
///////////////////////////////////////////////////////////////////////
//以下是实验要求的函数
//输出邻接表
template<class Type>void Graph<Type>::link(){
cout<<"输出邻接表:"<<endl;
for(int i=0;i<CurrentNumVertexes;i++){
cout<<GetValue(i);
int a=GetFirstNeighbor(i);
if(a!=-1) cout<<"->"<<GetValue(a)<<Getweight(i,a);
for(int j=a;j!=-1;j=a){
a=GetNextNeighbor(i,j);
if(a!=-1) cout<<"->"<<GetValue(a)<<Getweight(i,a);
}
cout<<endl;
}
}
//拓扑排序
template<class type>void Graph<type>::
TopologicalOrder()
{
int m=0;//m为输出的顶点数，初始值为0
for(int i=0;i<CurrentNumVertexes;i++){
for(int n=0;n<CurrentNumVertexes;n++){
if(InDegree[n]==0){
m++;//输出的顶点数加1
cout<<VTable[n].data<<endl;
InDegree[n]=-1;
for(int t=0;t<CurrentNumVertexes;t++){
if(n>=0&&n<CurrentNumVertexes){
if(t>=0&&t<CurrentNumVertexes){
if(Arcs[n][t]!=0&&Arcs[n][t]!=b)
InDegree[t]--;
}
}
}
for(int h=0;h<CurrentNumVertexes;h++){
cout<<InDegree[h]<<" ";
} cout<<endl; break;
}
}
}
if(m<CurrentNumVertexes) cout<<"AOV网络中有回路（有向环）！"<<endl;
}
//深度遍历
template<class Type>
void Graph<Type>::
DFS(const int v,int visited[ ])
{
cout<< VTable[v].data<<" "; //访问顶点 v
visited[v] =1; //顶点v 作访问标记
int w = GetFirstNeighbor (v);
while (w != -1) { //若顶点 w 存在
if (!visited[w]) DFS (w,visited);
w = GetNextNeighbor(v,w);
} //重复检测 v 的所有邻接顶点
}
template<class Type>
void Graph <Type> ::
DFTraverse ()
{
int i, n = NumberOfVertexes() ; //取图的顶点个数
int * visited = new int [n]; //定义访问标记数组 visited
for ( i = 0; i < n; i++ )
visited [i] = 0; //访问标记数组 visited 初始化
for ( i = 0; i < n; i++ ) //对图中的每一个顶点进行判断
if (!visited [i]) DFS (i, visited );
delete[ ]visited; //释放 visited
}
//求最短路径
template<class Type>void Graph<Type>::
ShortestPath(int n,int v)
{
int min,u;
dist=new int[n]; s=new int[n]; path=new int[n];
for(int j=0;j<n;j++){
dist[j]=Arcs[v][j]; s[j]=0;
if(j!=v&&dist[j]<MaxVertexes) path[j]=v;
else path[j]=-1; s[v]=1;
}
for(int i=0;i<=n-1;i++){
min=MaxVertexes; u=v;
for(int j=0;j<n;j++)
if(!s[j]&&dist[j]<min){
u=j; min=dist[j];
}
s[u]=1;
for(int w=0;w<n;w++)
if(!s[w]&&dist[u]+Arcs[u][w]<dist[w])
{
dist[w]=dist[u]+Arcs[u][w];
path[w]=u;
}
if(v!=i&&dist[i]!=10000&&v!=path[i])
cout<<GetValue(v)<<"到顶点"<<GetValue(i)<<"的最短路径是:"<<GetValue(v)<<GetValue(path[i])<<GetValue(i)<<endl;
else if(v!=i&&dist[i]!=10000)
cout<<GetValue(v)<<"到顶点"<<GetValue(i)<<"的最短路径是:"<<GetValue(path[i])<<GetValue(i)<<endl;
}
for(int m=0;m<n;m++)
cout<<GetValue(v)<<"到顶点"<<GetValue(m)<<"的最短路径长度是:"<<dist[m]<<endl;
}
//主函数
void main(){
char op;
do{
int m,i=0,j=0,w;
char a[20],c;
cout<<"请你输入顶点的个数:"; cin>>m;
for(i=0;i<m;i++){
cout<<"请输入第"<<j<<"个结点:";
cin>>a[i]; cout<<endl; j=j+1;
}
Graph<char>G(a,m);
G.link();
cout<<"深度遍历:"<<endl;
G.DFTraverse();
cout<<endl;
cout<<"拓扑排序:"<<endl;
G.TopologicalOrder();
cout<<endl;
cout<<"输入最小路径的源头结点:"<<endl;
cin>>c;
w=G.GetVertexPos(c);
G.ShortestPath(m,w);
loop:cout<<"是继续？(Y or N)"<<endl;
cin>>op;
if(op=='N'||op=='n')break;
if(op!='Y'&&op!='y'&&op!='N'&&op!='n')goto loop;
}while(op=='Y'||op=='y');
}
上一页 [1] [2]
数据结构课程设计C++图邻接矩阵-邻接表的建立 第2页下载如图片无法显示或论文不完整，请联系qq752018766
