c语言和图,C语言版–图的实现和各种操作

#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

if(i==G.vexnum) return FALSE;

else return i;

}

Status CreateGraph(MGraph &G)

{

int n;

cout<

cout<

cout<

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.vexs[i];

if(n%2)

{

for(i=0;i

for(j=0;j

G.arcs[i][j]=MAX;

for(k=0;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

for(j=0;j

G.arcs[i][j]=0;

for(k=0;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<

case DN:cout<

case UDG:cout<

case UDN:cout<

}

cout<

cout<

int i,j;

if(G.kind/2)

{

for(i=0;i

for(j=0;j

{

if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAX)

{

cout<

if(G.kind%2) cout<

cout<

}

}

}

else

{

for(i=0;i

for(j=0;j

{

if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MAX)

{

cout<

if(G.kind%2) cout<

cout<

}

}

}

}

void DFSTraverse(MGraph G)

{

int visited[MAX_VERTEX_NUM],i;

for(i=0;i

visited[i]=0;

for(i=0;i

{

if(!visited[i]) continue;

visited[i]=1;

cout<

}

}

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

if(j!=k) {closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j];}

closedge[k].lowcost=0;

cout<

for(i=1;i

{ min=MAX;

for(j=0;j

{   if(closedge[j].lowcost)

if(closedge[j].lowcost

}

cout<

closedge[k].lowcost=0;

for(j=0;j

if(G.arcs[k][j]

{

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

for(j=0;j

{

if(G.arcs[j][i]) indegree[i]++;

}

SqStack S;

InitStack(S);

for(i=0;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<

// ostrm<

i=LocateVex(G,e);

for(j=0;j

{

if(G.arcs[i][j])

{

if(!(–indegree[j])) Push(S,G.vexs[j]);

}

}

}

if(count

else return OK;

cout<

}

Status TopoOrder(MGraph G,SqStack &T,int ve[])

{

int indegree[MAX_VERTEX_NUM]={0};

int i,j;

VertexType e;

for(i=0;i

for(j=0;j

{

if(G.arcs[j][i]!=MAX) indegree[i]++;

}

SqStack S;

InitStack(S);

for(i=0;i

{

if(!indegree[i]) {Push(S,G.vexs[i]);}

}

int count=0;

for(i=0;i

ve[i]=0;

//ofstream ostrm;

//ostrm.open(“TopoOrder.txt”);

while(!StackEmpty(S))

{

Pop(S,e);Push(T,e);

count++;

// ostrm<

i=LocateVex(G,e);

for(j=0;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

else return OK;

cout<

}

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

while(!StackEmpty(T))

{

Pop(T,e);k=LocateVex(G,e);

for(j=0;j

{

if(G.arcs[k][j]!=MAX)

if(vl[j]-G.arcs[k][j]

}

}

//for(i=0;i

for(i=0;i

for(j=0;j

if(G.arcs[i][j]!=MAX)

{

ee=ve[i];el=vl[j]-G.arcs[i][j];

char tag=(ee==el)?’*':’+';

cout<

}

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

{

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

{

min=MAX;

for(j=0;j

if(!final[j])

if(D[j]

final[v]=TRUE;

for(j=0;j

if(!final[j]&&(min+G.arcs[v][j]

{

D[j]=min+G.arcs[v][j];

P[j]=v;

}//if

}//for

for(i=0;i

{

cout<

j=i;

while(j!=v0)

{

j=P[j];

cout<

}

cout<

}

}//DIJ