図の動作(c++実装)

(1)隣接マトリクス/隣接テーブルを用いて図を作成する.(2)深さ優先/広さ優先探索方式で図を遍歴する.(3)プログラミングはDijkstra最短パスアルゴリズムを実現する.

#include 
using namespace std;
#define MaxInt 32767
#define MVNum 100
typedef struct{
     
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;
typedef struct ArcNode{
     
    int adjvex;
    struct ArcNode * nextarc;
}ArcNode;
typedef struct VNode{
     
    char data;
    ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct{
     
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;
#define MAXQSIZE 100
typedef struct{
     
    int *base;
    int front;
    int rear;
}SqQueue;
void CreateUDN(AMGraph &G);
int LocateVex(AMGraph G,char v);
void CreateUDG(ALGraph &G);
int LocateVex(ALGraph G,char v);
void DFS(ALGraph G,int v);
void BFS(AMGraph G,int v);
void InitQueue(SqQueue &s);
int GetFront(SqQueue s,int e);
int EnQueue(SqQueue &s,int e);
int DeQueue(SqQueue &s,int e);
void ShortestPath_DIJ(AMGraph G,int v0);
int main(){
     
    AMGraph G1;
    ALGraph G2;
    int v;
    CreateUDN(G1);
    CreateUDG(G2);
    cout<<"                  :";
    cin>>v;
    cout<<"              （    ）:";
    DFS(G2,v);
    cout<<"
                  :";
    cin>>v;
    cout<<"               （    ）:";
    BFS(G1,v);
    cout<<"
                  :";
    cin>>v;
    cout<<"           "<<v<<"               "<<endl;
    ShortestPath_DIJ(G1,v);
    return 0;
}
//         
void CreateUDN(AMGraph &G){
     
    cout<<"-----         -----"<<endl;
    cout<<"          ："<<endl;
    cin>>G.vexnum>>G.arcnum;
    cout<<"      ："<<endl;
    for(int i=0;i<G.vexnum;i++){
     
        cin>>G.vexs[i];
    }
    for(int i=0;i<G.vexnum;i++){
     
        for(int j=0;j<G.vexnum;j++){
     
            G.arcs[i][j]=MaxInt;
        }
    }
    char v1,v2;
    int w,i,j;
    cout<<"      2      ："<<endl;
    for(int k=0;k<G.arcnum;k++){
     
        cin>>v1>>v2>>w;
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);
        G.arcs[i][j]=w;
        G.arcs[j][i]=G.arcs[i][j];
    }
    cout<<"    "<<endl;
    cout<<"        ："<<endl;
    for(int i=0;i<G.vexnum;i++){
     
        cout<<"[";
        for(int j=0;j<G.vexnum;j++){
     
            if(G.arcs[i][j]==32767)
                cout<<"* ";
            else
                cout<<G.arcs[i][j]<<" ";
        }
        cout<<"]"<<endl;
    }
}
int LocateVex(AMGraph G,char v){
     
    for(int i=0;i<G.vexnum;i++){
     
        if(v==G.vexs[i]){
     
            return i;
        }
    }
}
//        
void CreateUDG(ALGraph &G){
     
    cout<<"-----        -----"<<endl;
    cout<<"          ："<<endl;
    cin>>G.vexnum>>G.arcnum;
    cout<<"      ："<<endl;
    for(int i=0;i<G.vexnum;i++){
     
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    char v1,v2;
    int i,j;
    ArcNode *p1,*p2;
    cout<<"      2   ："<<endl;
    for(int k=0;k<G.arcnum;k++){
     
        cin>>v1>>v2;
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);
        p1=new ArcNode;
        p1->adjvex=j;
        p1->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p1;
        p2=new ArcNode;
        p2->adjvex=i;
        p2->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;
    }
    cout<<"    "<<endl;
    cout<<"       ："<<endl;
    for(int i=0;i<G.vexnum;i++){
     
        ArcNode *p=G.vertices[i].firstarc;
        cout<<i<<"->";
        while(p!=NULL){
     
            cout<<p->adjvex<<"->";
            p=p->nextarc;
        }
        cout<<endl;
    }
}
int LocateVex(ALGraph G,char v){
     
     for(int i=0;i<G.vexnum;i++){
     
        if(v==G.vertices[i].data){
     
            return i;
        }
    }
}
//              （    ）
//         ，0    
int visited[MVNum] = {
     0};
void DFS(ALGraph G,int v)
{
     
    ArcNode *p;
    visited[v] = 1;
    cout<<v<<" ";
    p=G.vertices[v].firstarc;
    int temp;
    while(p!=NULL){
     
        temp=p->adjvex;
        if(visited[temp]==0){
     
            DFS(G,temp);
        }
        p=p->nextarc;
    }
}
//               （    ）
void BFS(AMGraph G,int v)
{
     
    int visited[MVNum] = {
     0};
    int e;
    //         
    visited[v]=1;
    SqQueue q;
    InitQueue(q);
    cout<<EnQueue(q,v)<<" ";
    //      ，   ，                          
    while(q.front!=q.rear)
    {
     
        e=DeQueue(q,e);
        for(int i=0;i<G.vexnum;i++){
     
            if(G.arcs[e][i]!=MaxInt && visited[i]==0)
            {
     
                cout<<EnQueue(q,i)<<" ";
                visited[i]=1;

            }
        }
    }
}
//       
void InitQueue(SqQueue &s){
     
    s.base=new int[MAXQSIZE];
    s.front=s.rear=0;
}
//     
int GetFront(SqQueue s,int e){
     
    if(s.front!=s.rear){
     
        e=s.base[s.front];
    }else{
     
        cout<<"      ，     "<<endl;
    }
    return e;
}
//     
int EnQueue(SqQueue &s,int e){
     
    if(s.front==((s.rear+1)%MAXQSIZE)){
     
        cout<<"";
    }else{
     
        s.base[s.rear]=e;
        s.rear=(s.rear+1)%MAXQSIZE;
    }
    return e;
}
//     
int DeQueue(SqQueue &s,int e){
     
    if(s.front==s.rear){
     
        cout<<"";
    }else{
     
        e=s.base[s.front];
        s.front=(s.front+1)%MAXQSIZE;
    }
    return e;
}
//Dijkstra        
void ShortestPath_DIJ(AMGraph G,int v0){
     
    int n=G.vexnum,min,v,D[n],Path[n];
    bool S[n];
    for(v=0;v<n;v++){
     
        S[v]=false;
        D[v]=G.arcs[v0][v];
        if(D[v]<MaxInt){
     
            Path[v]=v0;
        }else{
     
            Path[v]=-1;
        }
    }
    S[v0]=true;
    D[v0]=0;
    for(int i=1;i<n;i++){
     
        min=MaxInt;
        for(int w=0;w<n;w++){
     
            if(!S[w] && D[w]<min){
     
                v=w;
                min=D[w];
            }
        }
        S[v]=true;
        for(int w=0;w<n;w++){
     
            if(!S[w] && (D[v]+G.arcs[v][w]<D[w])){
     
                D[w]=D[v]+G.arcs[v][w];
                Path[w]=v;
            }
        }
    }
//  v0           
    for(int i=0;i<n;i++){
     
        cout<<i<<":"<<D[i]<<endl;
    }
}