#include "iostream.h"
#include "fstream.h"
#include "SqStack.h"
#include "stdlib.h"
#define MAX 100000
#define MAX_VERTEX_NUM 20
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef char VertexType;
typedef struct {
VertexType vexs[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
GraphKind kind;
} MGraph;
int LocateVex(MGraph G,VertexType u)
{
for(int i=0;i<G.vexnum&&G.vexs[i]!=u;i++);
if(i==G.vexnum) return FALSE;
else return i;
}
Status CreateGraph(MGraph &G)
{
int n;
cout<<" 0. 有向圖 1. 有向網(wǎng)、 "<<endl;
cout<<" 2. 無向圖 3. 無向網(wǎng) "<<endl;
cout<<"輸入你要建立的圖的類型:"<<endl;
cin>>n;
ifstream istrm;
switch(n)
{
case 0:G.kind=DG;istrm.open("DGraph.txt");break;
case 1:G.kind=DN;istrm.open("DNet.txt");break;
case 2:G.kind=UDG;istrm.open("UDGraph.txt");break;
case 3:G.kind=UDN;istrm.open("UDNet.txt");break;
}
istrm>>G.vexnum>>G.arcnum;
int i,j,k,w;
VertexType v1,v2;
for(i=0;i<G.vexnum;i++) istrm>>G.vexs[i];
if(n%2)
{
for(i=0;i<G.arcnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=MAX;
for(k=0;k<G.arcnum;k++)
{
istrm>>v1>>v2>>w;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=w;
if(n/2) G.arcs[j][i]=w;
}
}
else
{
for(i=0;i<G.arcnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=0;
for(k=0;k<G.arcnum;k++)
{
istrm>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=1;
if(n/2) G.arcs[j][i]=1;
}
}
return OK;
}
void OutPut(MGraph G)
{
cout<<"該圖為";
switch(G.kind)
{
case DG:cout<<"有向圖"<<endl;break;
case DN:cout<<"有向網(wǎng)"<<endl;break;
case UDG:cout<<"無向圖"<<endl;break;
case UDN:cout<<"無向網(wǎng)"<<endl;break;
}
cout<<"頂點個數(shù)為"<<G.vexnum<<endl;
cout<<"邊的條數(shù)為"<<G.arcnum<<endl;
int i,j;
if(G.kind/2)
{
for(i=0;i<G.vexnum;i++)
for(j=0;j<i;j++)
{
if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAX)
{
cout<<G.vexs[i]<<" "<<G.vexs[j];
if(G.kind%2) cout<<" "<<G.arcs[i][j];
cout<<endl;
}
}
}
else
{
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAX)
{
cout<<G.vexs[i]<<" "<<G.vexs[j];
if(G.kind%2) cout<<" "<<G.arcs[i][j];
cout<<endl;
}
}
}
}
void DFSTraverse(MGraph G)
{
int visited[MAX_VERTEX_NUM],i;
for(i=0;i<G.vexnum;i++)
visited[i]=0;
for(i=0;i<G.vexnum;i++)
{
if(!visited[i]) continue;
visited[i]=1;
cout<<G.vexs[i]<<" ";
}
}
void MiniTree_PRIM(MGraph G,VertexType u)
{
struct{
VertexType adjvex;
int lowcost;
}closedge[MAX_VERTEX_NUM];
int k=LocateVex(G,u);
int i,j,min;
for(j=0;j<G.vexnum;j++)
if(j!=k) {closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j];}
closedge[k].lowcost=0;
cout<<"最小生成樹為"<<endl;
for(i=1;i<G.vexnum;i++)
{ min=MAX;
for(j=0;j<G.vexnum;j++)
{ if(closedge[j].lowcost)
if(closedge[j].lowcost<min) {k=j;min=closedge[j].lowcost;}
}
cout<<closedge[k].adjvex<<" "<<G.vexs[k]<<endl;
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;j++)
if(G.arcs[k][j]<closedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j];
}
}
}
Status TopoSort(MGraph G)
{
cout<<"拓撲排序序列為";
int indegree[MAX_VERTEX_NUM]={0};
int i,j;
VertexType e;
for(i=0;i<G.vexnum;i++)//FindInDegree
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[j][i]) indegree[i]++;
}
SqStack S;
InitStack(S);
for(i=0;i<G.vexnum;i++)
{
if(!indegree[i]) {Push(S,G.vexs[i]);}
}
int count=0;
//ofstream ostrm;
//ostrm.open("TopoOrder.txt");
while(!StackEmpty(S))
{
Pop(S,e);
cout<<e<<" ";count++;
// ostrm<<e<<" ";
i=LocateVex(G,e);
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j])
{
if(!(--indegree[j])) Push(S,G.vexs[j]);
}
}
}
if(count<G.vexnum) return ERROR;
else return OK;
cout<<endl;
}
Status TopoOrder(MGraph G,SqStack &T,int ve[])
{
int indegree[MAX_VERTEX_NUM]={0};
int i,j;
VertexType e;
for(i=0;i<G.vexnum;i++)//FindInDegree
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[j][i]!=MAX) indegree[i]++;
}
SqStack S;
InitStack(S);
for(i=0;i<G.vexnum;i++)
{
if(!indegree[i]) {Push(S,G.vexs[i]);}
}
int count=0;
for(i=0;i<G.vexnum;i++)
ve[i]=0;
//ofstream ostrm;
//ostrm.open("TopoOrder.txt");
while(!StackEmpty(S))
{
Pop(S,e);Push(T,e);
count++;
// ostrm<<e<<" ";
i=LocateVex(G,e);
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j]!=MAX)
{
if(!(--indegree[j])) Push(S,G.vexs[j]);
if(ve[i]+G.arcs[i][j]>ve[j]) {ve[j]=ve[i]+G.arcs[i][j];}
}
}
}
if(count<G.vexnum) return ERROR;
else return OK;
cout<<endl;
}
Status CriticalPath(MGraph G)
{
SqStack T;
InitStack(T);
int i,j,k;
int ee,el;
int ve[MAX_VERTEX_NUM],vl[MAX_VERTEX_NUM];
VertexType e;
if(!TopoOrder(G,T,ve)) return ERROR;
for(i=0;i<G.vexnum;i++) vl[i]=ve[G.vexnum-1];
while(!StackEmpty(T))
{
Pop(T,e);k=LocateVex(G,e);
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[k][j]!=MAX)
if(vl[j]-G.arcs[k][j]<vl[k]) vl[k]=vl[j]-G.arcs[k][j];
}
}
//for(i=0;i<G.vexnum;i++) cout<<" "<<vl[i];exit(1);
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
if(G.arcs[i][j]!=MAX)
{
ee=ve[i];el=vl[j]-G.arcs[i][j];
char tag=(ee==el)?'*':'+';
cout<<G.vexs[i]<<" "<<G.vexs[j]<<" "<<G.arcs[i][j]<<" "<<tag<<endl;
}
return OK;
}
void ShortestPath_DIJ(MGraph G,VertexType u)
{
int v0=LocateVex(G,u);
bool final[MAX_VERTEX_NUM];
int P[MAX_VERTEX_NUM],D[MAX_VERTEX_NUM];
int i,j,min,v;
for(i=0;i<G.vexnum;i++)
{
final[i]=FALSE;D[i]=G.arcs[v0][i];
if(G.arcs[v0][i]!=MAX) P[i]=v0;
else P[i]=MAX;
}
final[v0]=TRUE;
P[v0]=v0;
D[v0]=0;
for(i=1;i<G.vexnum;i++)
{
min=MAX;
for(j=0;j<G.vexnum;j++)
if(!final[j])
if(D[j]<min) {v=j;min=D[j];}
final[v]=TRUE;
for(j=0;j<G.vexnum;j++)
if(!final[j]&&(min+G.arcs[v][j]<D[j]))
{
D[j]=min+G.arcs[v][j];
P[j]=v;
}//if
}//for
for(i=0;i<G.vexnum;i++)
{
cout<<G.vexs[i]<<" ";
j=i;
while(j!=v0)
{
j=P[j];
cout<<G.vexs[j]<<" ";
}
cout<<D[i]<<endl;
}
}//DIJ