编辑代码

#include <iostream>
using namespace std;

#define ding 6;
#define bian 10;

#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
char vex[6] = {'1','2','3','4','5','6'};
char arc[100][2] = {{'1','2'},{'1','3'},{'1','4'},{'2','3'},{'2','5'},{'3','4'},{'3','5'},{'3','6'},{'4','6'},{'5','6'}};
int w[10]={6,1,5,5,3,5,6,4,2,6};
int Vexset[5];
int D[6][6];
int Path[6][6];
int a[6];
typedef struct{
    VerTexType vexs[MVNum];
    ArcType arcs[MVNum][MVNum];
    int vexnum,arcnum;
}AMGraph;

int LocateVex(AMGraph G,char v){
    for(int i = 0;i<G.vexnum;i++){
        if(G.vexs[i]==v)    
            return i;
    }
    return 0;
}

bool CreateUDN(AMGraph &G){
    //cin>>G.vexnum>>G.arcnum;
    int e=0;
    G.vexnum = ding;
    G.arcnum = bian;
    for(int i = 0;i<G.vexnum;i++)
        G.vexs[i] = vex[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;
    for(int k = 0;k<G.arcnum;k++){
        char v1,v2;
        int i,j;
        //int w=1;
        v1 = arc[k][0];
        v2 = arc[k][1];//cin>>v1>>v2>>w;
        i = LocateVex(G,v1);
        j = LocateVex(G,v2);
        G.arcs[i][j] = w[k];
        G.arcs[j][i] = G.arcs[i][j];
    }
    return true;
}
 
void ShortestPath_Floyd(AMGraph G){
    for(int i=0;i<G.vexnum;i++)
        for(int j=0;j<G.vexnum;j++){
            D[i][j] = G.arcs[i][j];
            if(D[i][j]<MaxInt&&i!=j)    Path[i][j] = i;
            else Path[i][j] = -1;
        }
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++)
            if(D[i][j]!=MaxInt) cout<<D[i][j]<<". ";
            else cout<<0<<". ";
        cout<<endl;
    }
    cout<<endl;
    for(int k=0;k<G.vexnum;k++){
        for(int i=0;i<G.vexnum;i++)
            for(int j=0;j<G.vexnum;j++)
                if(D[i][k]+D[k][j]<D[i][j]&&i!=j)
                {
                    D[i][j] = D[i][k]+D[k][j];
                    Path[i][j] = Path[k][j];
                }
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++)
            {
                if(D[i][j]==MaxInt) cout<<0<<". ";
                else cout<<D[i][j]<<". ";
            }
        cout<<endl;
    }
    cout<<endl;
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++)
            cout<<Path[i][j];
        cout<<endl;
    }
    }
}
void DFS(AMGraph G,int v1,int v2,int k,int p){
    //cout<<w;
    if(v1==v2&&k==0){
        for(int i=0;i<G.vexnum;i++)
            cout<<a[i]<<endl;
        cout<<endl;
        return ;
    }
    else if(k>0){
        a[v1] = p;
        for(int i=0;i<G.vexnum;i++){
            if(G.arcs[v1][i]<MaxInt&&a[i]==0){
                int w =k - G.arcs[v1][i];
            //cout<<v1<<". "<<i<<". "<<w<<endl;
            //int b[6];
            //for(int j=0;j<G.vexnum;j++)
                //b[j] = a[j];
                DFS(G,i,v2,w,p+1);
            }
        }
        a[v1] = 0;
    }
}
//08年 第四题
void DFST(AMGraph G,int v1,int v2,int k)
{
    for(int i=0;i<G.vexnum;i++)
        a[i] = 0;
    DFS(G,v1,v2,k,1);
}

int main() {
    AMGraph G;
    int a[6];
    CreateUDN(G);
    //ShortestPath_Floyd(G);
    DFST(G,0,4,9);
    //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。 
	cout << "Hello world!    - cpp.jsrun.net." << endl;
	return 0;
}