数据结构实验3——图的基本运算及职能交通中的最佳路径选择问题

实验3.图的基本运算及职能交通中的最佳路径选择问题

3.2-邻接矩阵的DFS和BFS

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ERROR 0
#define OK 1
#define Overflow 2  //表示上溢
#define Underflow 3  //表示下溢
#define NotPresent 4 //表示元素不存在
#define Duplicate 5  //表示有重复元素

#define FALSE 0
#define TRUE 1
typedef int ElemType;
typedef int Status;
typedef int BOOL;

/************队列操作**************/
//循环队列的结构体定义
typedef struct{
    int front;
    int rear;
    int maxSize;    //最大容量
    ElemType *element;
}Queue;

//创建一个能容纳mSize个单元的空队列
void Create(Queue *Q,int mSize){
    Q->maxSize=mSize;
    Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
    Q->front=Q->rear=0;
}
 
 
//判断队列是否为空,若是,则返回TRUE;否则返回FALSE
BOOL IsEmpty(Queue *Q){
    return Q->front==Q->rear;
}
 
 
//判断队列是否已满,若是,则返回TRUE,否则返回FALSE
BOOL IsFULL(Queue *Q){
    return (Q->rear+1)%Q->maxSize==Q->front;
}
 
 
//获取队头元素,并通过x返回.若操作成功,则返回TRUE,否则返回FALSE
BOOL Front(Queue *Q,ElemType *x){
    if(IsEmpty(Q))      //空队列处理
        return FALSE;
    *x=Q->element[(Q->front+1)%Q->maxSize];
    return TRUE;
}
 
 
//入队.在队列Q的队尾插入元素x(入队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL EnQueue(Queue *Q,ElemType x){
    if(IsFULL(Q))      //溢出处理
        return FALSE;
    Q->rear=(Q->rear+1)%Q->maxSize;
    Q->element[Q->rear]=x;
    return TRUE;
}
 
 
//出队.从队列Q中删除队头元素(出队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL DeQueue(Queue *Q){
    if(IsEmpty(Q)){   //空队列处理
        return FALSE;
    }
    Q->front=(Q->front+1)%Q->maxSize;
    return TRUE;
}
 
 /************队列操作**************/


//邻接矩阵的结构体定义
typedef struct{
    ElemType **a;     //邻接矩阵
    int n;            //图的当前顶点数
    int e;            //图的当前边数
    ElemType noEdge;  //两顶点间无边时的值
}mGraph;
 

//邻接矩阵的初始化
Status Init(mGraph *mg,int nSize,ElemType noEdgeValue){
    int i,j;
    mg->n = nSize;               //初始化顶点数
    mg->e = 0;                   //初始化时没有边
    mg->noEdge = noEdgeValue;    //初始化没有边时的取值
    mg->a = (ElemType**)malloc(nSize*sizeof(ElemType *));  //生成长度为n的一维指针数组
    if(!mg->a) return ERROR;
    for(i = 0;i < mg->n;i ++){   //动态生成二维数组
        mg->a[i] = (ElemType*)malloc(nSize*sizeof(ElemType));
        for(j = 0;j < mg->n;j ++){
            mg->a[i][j] = mg->noEdge;
        }
        mg->a[i][i] = 0;        //自回路设置为0
    }
    return OK;
}
 
 
//邻接矩阵的撤销(改成了int型，有返回值),先释放一维数组,再释放指针数组
int Destory(mGraph *mg){
    int i;
    for(i = 0;i < mg->n;i ++){
        free(mg->a[i]);  //释放n个一维数组的存储空间
    }
    free(mg->a);         //释放一维数组的存储空间
    return 1;
}
 
 
//邻接矩阵的边的搜索
Status Exist(mGraph *mg,int u,int v){
    if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v||mg->a[u][v] == mg->noEdge) return ERROR;
    return OK;
}
 
 
//邻接矩阵的边的插入
Status Insert(mGraph *mg,int u,int v,ElemType w){
    if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return ERROR;
    if(mg->a[u][v] != mg->noEdge) return Duplicate;  
    //若待插入边已存在,则返回出错信息
    mg->a[u][v] = w;                                 //插入新边
    mg->e ++;                                        //增加一条边
    return OK;
}
 
 
//邻接矩阵的边的删除
Status Remove(mGraph *mg,int u,int v){
    if(u < 0||v < 0||u > mg->n-1||v > mg->n-1 ||u == v) return ERROR;
    if(mg->a[u][v] == mg->noEdge) return NotPresent;  
    //若待删除边不存在,则返回出错信息
    mg->a[u][v] = mg->noEdge;                         //删除边
    mg->e --;
    return OK;
}
 

void DFS(mGraph mg,int v,int visited[]){
    int j;
    printf("%d",v );
    visited[v] = 1;
    for( j = 0; j < mg.n; j++){             //遍历v的邻接点
        if(!visited[j] && mg.a[v][j] > 0){  //当未被访问且有权值
            DFS(mg,j,visited);
        }
    }

}

//DFS搜索全图
void DFSGraph(mGraph mg){
    int i;
    int *visited = (int *)malloc(mg.n * sizeof(int));   //访问为1,未访问为0
    for(i=0; i< mg.n;i++) visited[i] = 0;   //visted数组初始化
    for(i=0;i< mg.n; i++)
            if( !visited[i] ) 
                DFS(mg,i,visited);
    free(visited);           //整个图的DFS遍历后,释放visted数组
} 

void BFS(mGraph mg,int v,int visited[]){
    Queue q;
    Create(&q,mg.n);
    visited[v] = 1;
    printf("%d",v);
    EnQueue(&q,v);                         //将当前顶点v放入队列
    while( !IsEmpty(&q) ){
        Front(&q,&v);
        DeQueue(&q);                       //队首顶点出队列
        for(int i = 0;i < mg.n;i ++){       //遍历图的每一项
            if( !visited[i] && mg.a[v][i] > 0){       
                //若未被访问且有权值,则将其访问并放入队列
                visited[i] = 1;
                printf("%d",i);
                EnQueue(&q,i);
            }
        }
    }
}

//BFS搜索全图
void BFSGraph(mGraph mg){
    int i;
    int *visited = (int *)malloc(mg.n * sizeof(int));   //访问为1,未访问为0
    for(i=0; i< mg.n;i++) visited[i] = 0;   //visted数组初始化
    for(i=0;i< mg.n; i++)
            if( !visited[i] ) 
                BFS(mg,i,visited);
    free(visited);           //整个图的BFS遍历后,释放visted数组
} 

 
int main(){
    mGraph g;
    int nSize,edge,u,v,i;
    ElemType w;

    printf("Enter the mgraph's Size:");
    scanf("%d",&nSize);
    Init(&g,nSize,-1);
    printf("Enter the mgraph's Edge num:");
    scanf("%d",&edge);

    for(i = 0;i < edge;i ++){
        printf("Please enter the edge(Pu,Pv,Weight):");
        scanf("%d%d%d",&u,&v,&w);
        Insert(&g,u,v,w);
    }

    printf("DFS:");
    DFSGraph(g);

    printf("\nBFS:");
    BFSGraph(g);
    printf("\n");

    system("pause");
    return 0;
}

3.4-邻接表的BFS和DFS

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ERROR 0
#define OK 1
#define Overflow 2  //表示上溢
#define Underflow 3  //表示下溢
#define NotPresent 4 //表示元素不存在
#define Duplicate 5  //表示有重复元素

#define FALSE 0
#define TRUE 1
typedef int ElemType;
typedef int Status;
typedef int BOOL;

/************队列操作**************/
//循环队列的结构体定义
typedef struct{
    int front;
    int rear;
    int maxSize;    //最大容量
    ElemType *element;
}Queue;

//创建一个能容纳mSize个单元的空队列
void Create(Queue *Q,int mSize){
    Q->maxSize=mSize;
    Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
    Q->front=Q->rear=0;
}
 
 
//判断队列是否为空,若是,则返回TRUE;否则返回FALSE
BOOL IsEmpty(Queue *Q){
    return Q->front==Q->rear;
}
 
 
//判断队列是否已满,若是,则返回TRUE,否则返回FALSE
BOOL IsFULL(Queue *Q){
    return (Q->rear+1)%Q->maxSize==Q->front;
}
 
 
//获取队头元素,并通过x返回.若操作成功,则返回TRUE,否则返回FALSE
BOOL Front(Queue *Q,ElemType *x){
    if(IsEmpty(Q))      //空队列处理
        return FALSE;
    *x=Q->element[(Q->front+1)%Q->maxSize];
    return TRUE;
}
 
 
//入队.在队列Q的队尾插入元素x(入队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL EnQueue(Queue *Q,ElemType x){
    if(IsFULL(Q))      //溢出处理
        return FALSE;
    Q->rear=(Q->rear+1)%Q->maxSize;
    Q->element[Q->rear]=x;
    return TRUE;
}
 
 
//出队.从队列Q中删除队头元素(出队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL DeQueue(Queue *Q){
    if(IsEmpty(Q)){   //空队列处理
        return FALSE;
    }
    Q->front=(Q->front+1)%Q->maxSize;
    return TRUE;
}
 


 /************队列操作**************/

//邻接表的结构体定义
typedef struct ENode{
    int adjVex;              //任意顶点u相邻的顶点
    ElemType w;              //边的权值
    struct ENode *nextArc;   //指向下一个边结点
}ENode;
 
typedef struct{
    int n;           //图的当前顶点数
    int e;           //图的当前边数
    ENode **a;       //指向一维指针数组
}LGraph;
 

//邻接表的初始化
Status Init(LGraph *lg,int nSize){
    int  i;
    lg->n = nSize;
    lg->e = 0;
    lg->a = (ENode**)malloc(nSize*sizeof(ENode*));      
    //动态生成长度为n的一维指针数组
    if(!lg->a) return ERROR;
    for(i = 0;i < lg->n;i ++) lg->a[i] = NULL;          //将指针数组a置空
    return OK;
}
 
 
//邻接表的撤销
int Destory(LGraph *lg){
    int i;
    ENode *p,*q;
    for(i = 0;i < lg->n;i ++){        //链表的撤销操作
        p = lg->a[i];                 //指针p指向顶点i的单链表的第一个边结点
        q = p;
        while(p){                     //释放顶点i的单链表中所有边结点
            p = p->nextArc;
            free(q);
            q = p;
        }
    }
    free(lg->a);                     //释放一维指针数组a的存储空间
    return OK;                        //改为int型函数,有返回值
}
 
 
//邻接表的搜索边
Status Exist(LGraph *lg,int u,int v){
    ENode *p;
    if(u < 0||v < 0||u > lg->n-1 ||v > lg->n-1 ||u == v) return ERROR;
    p = lg->a[u];                   //指针p指向顶点u的单链表的第一个边结点
    while(p!=NULL && p->adjVex != v){
        p = p->nextArc;
    }
    if(!p) return ERROR;            
    else return OK;
}
 
 
//邻接表的插入边
Status Insert(LGraph *lg,int u,int v,ElemType w){
    ENode *p;
    if(u < 0||v < 0||u > lg->n-1||v > lg->n-1 ||u == v) return ERROR;
    if(Exist(lg,u,v)) return Duplicate;  //此边已存在,返回错误
    p = (ENode*)malloc(sizeof(ENode));   //为新的边结点分配存储空间
    p->adjVex = v;
    p->w = w;
    p -> nextArc = lg->a[u];             //将新的边结点插入单链表的最前面
    lg->a[u] = p;
    lg->e ++;                       
    return OK;
}
  
//邻接表的删除边
Status Remove(LGraph *lg,int u,int v){
    ENode *p,*q;
    if(u < 0 || v < 0 || u > lg->n-1 || v > lg->n-1 || u == v) return ERROR;
    p = lg->a[u];
    q = NULL;
    while(p && p->adjVex != v){         //查找待删除边是否存在
        q = p;
        p = p->nextArc;
    }
    if(!p) return NotPresent;       
    if(q) q->nextArc = p->nextArc;     //从单链表删除此边
    else lg->a[u] = p->nextArc;
    free(p);
    lg->e --;
    return OK;
}
 

void BFS(LGraph lg,int v,int visited[]){
    ENode *j;
    Queue q;
    Create(&q,lg.n);
    visited[v] = 1;
    printf("%d", v);
    EnQueue(&q,v);              //访问的节点入队
    while( !IsEmpty(&q) ){       //一直到该层没有节点为止
        Front(&q,&v);           // 取出父节点
        DeQueue(&q);
        for (j=lg.a[v]; j!= NULL;j=j->nextArc ){
            if ( !visited[j->adjVex]){
                visited[j->adjVex] = 1;
                printf("%d", j->adjVex);
                EnQueue(&q,j->adjVex);
            }
        }
    }
}

void BFSGraph(LGraph lg){
    int i;
    int *visited = (int *)malloc(sizeof(int)* lg.n);    //记录n个节点的访问情况
    for(i=0; i< lg.n;i++) visited[i] = 0;   //visted数组初始化
    for (int i = 0; i < lg.n; ++i)
        if( !visited[i] ) BFS(lg,i,visited);
    free(visited);
}



void DFS(LGraph lg,int v,int visited[]){
    ENode *j;
    printf("%d",v );
    visited[v] = 1;
    for (j = lg.a[v];j!=NULL;j= j->nextArc)     //lg.a链表的循环
        if( !visited[j->adjVex] ) 
            DFS(lg,j->adjVex,visited);
}

void DFSGraph(LGraph lg){
    int i;
    int *visited = (int *)malloc(sizeof(int)* lg.n);    //记录n个节点的访问情况
    for(i=0; i< lg.n ; i++) visited[i] = 0;               //visted数组初始化
    for (int i = 0; i < lg.n; ++i)
        if( !visited[i] ) DFS(lg,i,visited);
    free(visited);
}

 
int main(){
    LGraph g;
    int i,u,v,enode,edge;
    ElemType w;

    printf("Enter the number of mgraph's Nodes:");
    scanf("%d",&enode);
    Init(&g,enode);
    printf("Enter the mgraph's Edge num:");
    scanf("%d",&edge);

    for(i = 0;i < edge;i ++){
        printf("Please enter the edge(Pu,Pv,Weight):");
        scanf("%d%d%d",&u,&v,&w);
        Insert(&g,u,v,w);
    }

    printf("DFS:");
    DFSGraph(g);

    printf("\nBFS:");
    BFSGraph(g);
    printf("\n");

    system("pause");
    return 0;
}

以上大多直接从学长的博客搬运过来.

3.5- 飞机换乘最短距离(Dijkstra单源最短路径)

编写程序，实现智能交通中的最佳路径选择问题：设有n个地点，编号为0~n-1，m条路径的起点、终点和代价由用户输入提供，采用实验3.1所示邻接矩阵为存储结构，寻找最佳路径方案(如花费时间最少、路径长度最短、交通费用最小等，任选其一即可)。

借了学长的整体框架,将邻接矩阵改成了邻接表,并完成了题目要求的给定起点、终点，算最短路径。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ERROR 0
#define OK 1
#define Overflow 2  //表示上溢
#define Underflow 3  //表示下溢
#define NotPresent 4 //表示元素不存在
#define Duplicate 5  //表示有重复元素
#define INFTY 32657 //表示正无穷
#define FALSE 0
#define TRUE 1
typedef int ElemType;
typedef int Status;
typedef int BOOL;

//邻接表的结构体定义
typedef struct ENode{
    int adjVex;              //任意顶点u相邻的顶点
    ElemType w;              //边的权值
    struct ENode *nextArc;   //指向下一个边结点
}ENode;
 
typedef struct{
    int n;           //图的当前顶点数
    int e;           //图的当前边数
    ENode **a;       //指向一维指针数组
}LGraph;
 

//邻接表的初始化
Status Init(LGraph *lg,int nSize){
    int  i;
    lg->n = nSize;
    lg->e = 0;
    lg->a = (ENode**)malloc(nSize*sizeof(ENode*));      
    //动态生成长度为n的一维指针数组
    if(!lg->a) return ERROR;
    for(i = 0;i < lg->n;i ++) lg->a[i] = NULL;          
    //将指针数组a置空
    return OK;
}
 
 
//邻接表的撤销
int Destory(LGraph *lg){
    int i;
    ENode *p,*q;
    for(i = 0;i < lg->n;i ++){        //链表的撤销操作
        p = lg->a[i];                 //指针p指向顶点i的单链表的第一个边结点
        q = p;
        while(p){                     //释放顶点i的单链表中所有边结点
            p = p->nextArc;
            free(q);
            q = p;
        }
    }
    free(lg->a);                     //释放一维指针数组a的存储空间
    return OK;                        //改为int型函数,有返回值
}
 
 
//邻接表的搜索边
Status Exist(LGraph *lg,int u,int v){
    ENode *p;
    if(u < 0||v < 0||u > lg->n-1 ||v > lg->n-1 ||u == v) return ERROR;
    p = lg->a[u];                   //指针p指向顶点u的单链表的第一个边结点
    while(p!=NULL && p->adjVex != v){
        p = p->nextArc;
    }
    if(!p) return ERROR;            
    else return OK;
}
 
 
//邻接表的插入边
Status Insert(LGraph *lg,int u,int v,ElemType w){
    ENode *p;
    if(u < 0||v < 0||u > lg->n-1||v > lg->n-1 ||u == v) return ERROR;
    if(Exist(lg,u,v)) return Duplicate;  //此边已存在,返回错误
    p = (ENode*)malloc(sizeof(ENode));   //为新的边结点分配存储空间
    p->adjVex = v;
    p->w = w;
    p -> nextArc = lg->a[u];             //将新的边结点插入单链表的最前面
    lg->a[u] = p;
    lg->e ++;                       
    return OK;
}
  
//邻接表的删除边
Status Remove(LGraph *lg,int u,int v){
    ENode *p,*q;
    if(u < 0 || v < 0 || u > lg->n-1 || v > lg->n-1 || u == v) return ERROR;
    p = lg->a[u];
    q = NULL;
    while(p && p->adjVex != v){         //查找待删除边是否存在
        q = p;
        p = p->nextArc;
    }
    if(!p) return NotPresent;       
    if(q) q->nextArc = p->nextArc;     //从单链表删除此边
    else lg->a[u] = p->nextArc;
    free(p);
    lg->e --;
    return OK;
}
 

 
//选出最小的d[i],i ∈ V-S
int Choose(int d[],int n,int s[]){  
    int minpos;
    int i;
    ElemType min;
    min = INFTY;
    minpos = -1;
    for(i = 0;i < n;i ++){         //这里i初值改为0
        if( d[i] <= min && !s[i]){  //<改为<=
            // printf("Choose: d[%d]:%d ",i, d[i]);	  
            //可以将这段注释打开理解
            min = d[i];
            minpos = i;
        }
    }
    return minpos;                //返回下标位置
}
 

//Dijkstra算法
Status Dijkstra(LGraph g,int v,int d[],int path[]){  
    int i,k,w,distance = 0;       //增加了一个distance记录最短距离之和
    int *s;
    if(v < 0 || v > g.n-1)  return ERROR;
    ENode *j;

    /*对辅助数据结构的初始化*/
    s = (int*)malloc(g.n*sizeof(int));
    /*非源点结点初始化*/
    for(i = 0;i < g.n;i ++){      
        s[i] = 0;                 //表示顶点i是否在s中
        for( j=g.a[v];j!=NULL; j=j->nextArc) 
            if(j->adjVex == i ) 
                d[i] = j->w;         //v到i的距离
        if(i != v && d[i] < INFTY) path[i] = v;          
        //如果与源点有边相通,标识指向i的源点v
        else path[i] = -1;
    }
    /*源点初始化*/
    s[v] = 1;                     //顶点v为源点,将原点v加入集合S
    printf("The order:%d ",v);              //输出源点0
    d[v] = 0;
    /*对辅助数据结构的初始化*/


    for(i = 1;i <= g.n-1;i ++){   //最多产生n-1条最短路径,<改为<=
        k = Choose(d, g.n ,s);      //求当前路径最短者k
        s[k] = 1;                 //将k加入集合S中
        printf("%d ",k);
        for( j = g.a[k]; j!=NULL; j= j->nextArc){  //更新d和path
            if( !s[j->adjVex] && d[k] + j->w < d[ j->adjVex ]){        
            //未被访问过,且 当前边+到前个结点的权值 < 现在的路径长度
            //j->adjVex为所有与v相邻接的顶点
                d[j->adjVex ] = d[k] + j->w;
                distance = d[j->adjVex ];  //计算所有路径中的min距离
                path[j->adjVex ] = k;
            }
        }
    }
    return OK;
}
 
 
 
int main(){
    LGraph g;
    int nSize,edge,u,v,i;
    int s,t;  //起点,终点
    int d[100];
    for(int i=0;i<100;i++) d[i] = INFTY;
    int path[100];
    ElemType w;
    printf("Enter the number of mgraph's Nodes:");
    scanf("%d",&nSize);
    Init(&g,nSize);
    printf("Enter the mgraph's Edge num:");
    scanf("%d",&edge);

    for(i = 0;i < edge;i ++){
        printf("Please enter the edge(Pu,Pv,Weight):");
        scanf("%d%d%d",&u,&v,&w);
        Insert(&g,u,v,w);
    }

    printf("Enter the Start Point :");
    scanf("%d",&s);
    printf("Enter the Destination Point :");
    scanf("%d",&t);

    Dijkstra(g,0,d,path);
    printf("\nThe shortest distance from %d to Point %d:%d\n",s,t, d[t]);
    system("pause");
    return 0;
}