Java_02

7-1 邻接表存储实现图的深度优先遍历

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
int a[MAXSIZE]={0};
//边表
typedef struct At{
    int t;          //保存邻接点下标
    char wei;       //储存权值
    struct At* next; //链域，指向下一个邻接点
}At;
//顶点表
typedef struct bt{
    char x;   //顶点
    At *First;   //边表头指针
}S[MAXSIZE];
//图结构
typedef struct{
    S s;    //顶点的实例化对象
    int vexnum,edgnum;//顶点数量和边数量
}ct;
int locateVex(ct G,char v){
    for(int i=0;i<G.vexnum;i++)
    {
        if(G.s[i].x==v)return i;
    }
    return -1;
}
void Creatgraph(ct &G,int &err){
     cin>>G.vexnum>>G.edgnum;
    for(int i=0;i<G.vexnum;i++){
        cin>>G.s[i].x;
        G.s[i].First=NULL;
    }
    
    for(int k=0;k<G.edgnum;k++){
        char v1,v2;
        cin>>v1>>v2;
        int i,j;
        i=locateVex(G,v1),j=locateVex(G,v2);
    if(i==-1||j==-1)err=1;
        else{
            At *p1=new At;
            p1->t=j;
            p1->next=G.s[i].First;
            G.s[i].First=p1;
            At *p2=new At;
            p2->t=i;
            p2->next=G.s[j].First;
            G.s[j].First=p2;
        }
    }
}
void DFS_ASgraphy(ct &G,int adj){
    cout<<G.s[adj].x<<" ";
    a[adj]=1;
    At *p=G.s[adj].First;
    while(p!=NULL){
        if(a[p->t]!=1)
            DFS_ASgraphy(G,p->t);
        p=p->next;
    }
}
int main(){
   ct G;
    int err=0;
    char start;
    Creatgraph(G,err);
    cin>>start;
    int adj=locateVex(G,start);
    if(adj==-1||start==1)cout<<"error";
    else{
    DFS_ASgraphy(G,adj);
    }
    return 0;
}

7-2 迪杰斯特拉方法实现最短路径

#include<bits/stdc++.h>
using namespace std;
#define THEMAX 100     //顶点的最大个数
#define MAXINT 32367
int S[THEMAX];//为各个顶点配置一个标记值，用于确认该顶点是否已经找到最短路径
int Path[THEMAX],D[THEMAX];
typedef struct{
    int vex[THEMAX];//存储图中顶点数据
    int arc[THEMAX][THEMAX];//二维数组，记录顶点之间的关系
    int vexnum,arcnum;//记录图的顶点数和弧（边）数
}AMgraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int locateVex(AMgraph G,int v){
    for(int i=0;i<G.vexnum;i++){
        if(G.vex[i]==v)return i;
    }
    return -1;
}
//构造无向有权图
void CreatGraph(AMgraph &G,int &err){
    cin>>G.vexnum>>G.arcnum;
    for(int i=0;i<G.vexnum;i++)
        for(int j=0;j<G.vexnum;j++)
            G.arc[i][j]=MAXINT;
    for(int i=0;i<G.vexnum;i++){
        cin>>G.vex[i];
    }
    for(int k=0;k<G.arcnum;k++){
        int v1,v2,W;
        cin>>v1>>v2>>W;
        int i,j;
        i=locateVex(G,v1),j=locateVex(G,v2);
        if(i==-1||j==-1)err=1;
        else
            G.arc[i][j]=W;
        
    }
}
//迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标
void ShortPath(AMgraph G,int v0){
      //对各数组进行初始化
    for(int v=0;v<G.vexnum;v++){
        S[v]=0;
        D[v]=G.arc[v0][v];
        if(D[v]<MAXINT)Path[v]=v0;
        else Path[v]=-1;
    }
    //由于以v0位下标的顶点为起始点，所以不用再判断
    S[v0]=1,D[v0]=0;
    for(int k=0;k<G.vexnum-1;k++){
        int wmin=MAXINT,vmin;
        //选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点
        for(int w=0;w<G.vexnum;w++){
            if(!S[w]&&D[w]<wmin){
                vmin=w;
                wmin=D[w];
            }
        }
        S[vmin]=1;//设置该顶点的标志位为1，避免下次重复判断
          //对v0到各顶点的权值进行更新
        for(int i=0;i<G.vexnum;i++){
            if(!S[i]&&(D[vmin]+G.arc[vmin][i])<D[i]){
                D[i]=D[vmin]+G.arc[vmin][i];
                Path[i]=vmin;//记录各个最短路径上存在的顶点
            }
        }
    }
}
int main(){
    AMgraph G;
    int err=0;
    int v0,ve;
    CreatGraph(G,err);
    cin>>v0>>ve;
    int i=locateVex(G,v0),j=locateVex(G,ve);
    if(i!=-1&&j!=-1){
        ShortPath(G,i);
        int adj[MAXINT],k=1;
        adj[0]=j;
        while(Path[j]!=i){
            adj[k]=Path[j];
            j=Path[j];
            ++k;
        }
        adj[k]=i;
        for(int n=k;n>=0;--n){
            if(n!=0){
                cout<<G.vex[adj[n]]<<"-->";
            }else{
                cout<<G.vex[adj[n]];
            }
        }
    }
    return 0;
}