图的应用

1、最小生成树（prim算法）

//prim算法的思想：选择一个初始顶点，把它加入辅助数组，计算该顶点到其他顶点的代价，选择其中最小代价对应点加入辅助数组，扫描加入新的顶点有没有使其到各个顶点的代价变化，并更新代价数组；重复进行以上步骤，知道所有顶点都已经加入了辅助数组
//记录顶点集U到V-U的代价最小的边的辅助数组
struct{
    VertexType adjvex;
    VRType lowcost;
}closedge[MAX_VERTEX_NUM];

void MiniSpanTree_PRIM(MGraph G,VetexType u){
    //用prim算法从第v个顶点出发构造网的最小生成树T，并输出最小生成树的各条边
      k=LocateVex(G,u);
    for(j=0;j<G.vexnum;j++) //辅助数组初始化
        if(j!=k) closedge[j]={u,G.arcs[k][j].adj}; //{adjvex,lowcost}
    closedge[k].lowcost=0; //初始，U={u}
    for(i=1;i<G.vexnum;++i){ //选择其余G.vexnum-1个顶点
        k=minimum(closedge);  //求出T的下一个顶点:第k顶点
        printf(closedge[k].adjvex,G.vexs[k]);
        closedge[k].lowcost=0;
        for(j=0;j<G.vexnum;++j)
            if(G.arcs[k][j]).adj<closedge[j].lowcost)
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};
    }
} //MiniSpanTree

2、单源最短路径

BFS可用于求不带权的图的单源最短路径（课本上没有）

bool viisted[Max_VeTex_num];

void BFS_Min_Distance(Graph G,int v){
    //BFS求无向图的单源最短路径
    for(int i=0;i<G.vexNum;i++){
        d[i]=Inifinate; //最短路径大小
        path[i]=-1; //最短路径从哪里过来
    }
    d[v]=0; //起点到自己的距离置为0；
    visited[v]=true;
    EnQueue(Q,v);
    while(!IsEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            if(!visited[w]){
                visited[w]=true;
                EnQueue(Q,w);
                d[w]=d[v]+1;
                path[w]=u;
              }
        }
    }
}

3、拓扑排序

Status TopologicalOrder(ALGraph G,Stack &T){
    //有向网G采用邻接表存储结构，求各顶点事件最早发生时间ve（全局变量）
    //T为拓扑序列顶点栈，S为零入度顶点栈
    //若G无回路，则栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR
    FindInDegree(G,indegree); //对各顶点求入度indegree[0...vernum-1]
    InitStack(S)； //建立并初始化零入度顶点栈
    count=0;ve[0...G.vexnum-1]=0; //初始化
    while(!StackEmpty(S)){
        Pop(S,j); Push(T,j);++count; //j号顶点入T栈并计数
        for(p=G.vertices[j].firstarc;p;p->nextarc){
            k=p->adjvex; //对j号顶点的每个邻接点的入度减1
            if(--indgree[k]==0) Push(S,k); //若入度减为0，则入栈
            if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info) ;
        }
    }
    if(count<G.vexnum) return ERROR; //该有向图有回路
    else retrun OK;
}