c_ 数据结构_图_邻接矩阵

程序主要实现了图的深度遍历和广度遍历。
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define OVERFLOW -2

#define ERROR 0

#define OK 1

#define Length (q.rear+1)%QUEUE_MAXSIZE     //队满

#define MAX_VERtEX_NUM 20                   //顶点的最大个数

#define QUEUE_MAXSIZE 100

#define Queue_increment 10

typedef struct QNode{

    int data;

    struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

    QueuePtr front;   //队头指针

    QueuePtr rear;    //队尾指针

}LinkQueue;

//-------------------------------------------------------------------------------------------------------------

typedef struct {

    int adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。

}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {

    char vexs[MAX_VERtEX_NUM];        //存储图中顶点数据

    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系

    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数

}MGraph;

//---------------------------------------------------------------------------

// 矩阵打印关系

void PrintGrapth(MGraph &G){

    int i,j;

    for (i = ; i < G.vexnum;++i){

        printf("%d",G.vexs[i]);

    }

    printf("顶点间的关系:\n");

    for (i = ; i < G.vexnum; ++i){

        for (j = ; j < G.vexnum; ++j){

            printf("%d ", G.arcs[i][j].adj);

        }

        printf("\n");

    }

}

//---------------------------------------------------------------------------

//根据顶点本身数据，判断出顶点在二维数组中的位置

int LocateVex(MGraph &G,int v){

    //遍历一维数组，找到变量v

    for (int i=; i<G.vexnum; ++i) {

        if (G.vexs[i]==v) {

            return i;

        }

    }

    return -; //如果找不到，返回-1

}

//构造无向图

int CreateDN(MGraph &G){

    int i,j,k,m,n,x;int v1,v2;//char a[2];

    printf("请输入总顶点数n和总边数:");

    scanf("%d",&(G.vexnum));        // 输入总顶点数，总边数

    scanf("%d",&(G.arcnum));

    x=G.vexnum;

    if(G.vexnum< && G.arcnum<=(x*(x-)/)){

        printf("请(回车)输入 %d 个顶点的值：\n",G.vexnum);

        for (i=; i<G.vexnum; i++) {      // 循环输入顶点值

            scanf("%d",&(G.vexs[i]));

        }

        for (i=; i<G.vexnum; ++i) {        // 初始化邻接矩阵

            for (j=; j<G.vexnum; ++j) {

                G.arcs[i][j].adj=;

            }

        }

        printf("\n请实现 %d 条边的连接：\n",G.arcnum);

        for (k=;k<G.arcnum; ++k) {     // 构造邻接矩阵

            printf("\n请输入哪'两个'顶点要进行连接边：");

            fflush(stdin);

            scanf("%d",&v1);

            n=LocateVex(G, v1);    //定位顶点

            scanf("%d",&v2);

            m=LocateVex(G, v2);

            while (m==-||n==-) {

                   printf("没有这样的顶点,请重新输入：");

                fflush(stdin);

                scanf("%d",&v1);

                n=LocateVex(G, v1);    //定位顶点

                scanf("%d",&v2);

                m=LocateVex(G, v2);

        //        if(m!=-1&&n!=-1){break;    }

            }

            while(G.arcs[n][m].adj==){

                printf("\n!!!两顶点已经被连接!!!\n");

                printf("请重新输入两顶点：");

                fflush(stdin);

                scanf("%d",&v1);

                n=LocateVex(G, v1);    //定位顶点

                scanf("%d",&v2);

                m=LocateVex(G, v2);

        //        if(G.arcs[n][m].adj!=1){break;    }

                while (m==-||n==-) {

                       printf("没有这样的顶点,请重新输入：");

                    fflush(stdin);

                    scanf("%d",&v1);

                    n=LocateVex(G, v1);    //定位顶点

                    scanf("%d",&v2);

                    m=LocateVex(G, v2);

            //        if(m!=-1&&n!=-1){break;    }

                }

            }

            G.arcs[n][m].adj=G.arcs[m][n].adj=;    //无向图的二阶矩阵沿主对角线对称

        }

    }else{

        printf("\n!!!您输入的总顶点数 大于 20 了或者是输入的总边数 不符合 n(n-1)/2 !!!\n");

        CreateDN(G);

    }

    return OK;

}

//-------------------------------------------------------------------------------------------------

int visited[MAX_VERtEX_NUM];   // 辅助数组

// 遍历节点

void DFS(MGraph &G,int v){

    int j;

    printf("访问到顶点:%d\n\n",G.vexs[v]);   // 表示顶点被访问过了

    visited[v]=;

    for(j=;j<G.vexnum;++j){

        if(G.arcs[v][j].adj!= && visited[j]==){   // 如果有邻接点则继续递归

            DFS(G,j);

        }

    }

}

// 顶点的非连通图的深度遍历

int DFSTraverse(MGraph &G){

    int n=,v,x,j,m;

    for(v=;v<G.vexnum;v++) visited[v]=;    // 把所有的标记置为0

    printf("\n请输入遍历起点：\n");

    scanf("%d",&x);

    printf("遍历起点为：%d \n",x);

    m = LocateVex(G,x);

    if(m==-){

        printf("\n！！！您输入的起点不在顶点表内！！！\n");

        DFSTraverse(G);

    }

    //n=LocateVex(G,x);

    visited[m]=;

    for(j=;j<G.vexnum;++j){

        if(G.arcs[n][j].adj!= && visited[j]==){   // 如果有邻接点则继续递归

            DFS(G,j);

        }

    }

    //DFS(G,m);

    for(v=;v<G.vexnum;++v){     // 判断是否还有没有被遍历的图

        if(visited[v]==){

            DFS(G,v);    // 调用DFS遍历单个图

        }

    }

    return OK;

}

//-------------------------------------------------------------------------------------

//构建空队

int InitQueue_Q(LinkQueue &Q){

    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

    if(!Q.front){

        printf("队存储空间分配失败！！");

        exit(OVERFLOW);

    }

    Q.front->next=NULL;

    return OK;

}

//队尾插入元素

int EnQueue_Q(LinkQueue &Q,int &e){

    QueuePtr p;

    p=(QueuePtr)malloc(sizeof(QNode));

    if(!p){                   //存储分配失败

        printf("队存储空间分配失败!!!\n");

        exit(OVERFLOW);

    }

    p->data=e;                          //e赋值给p指向的空间

    p->next=NULL;                     //p指向NULL

    Q.rear->next=p;

    Q.rear=p;                           //将p赋给Q

    return OK;

}

// 删除队列头元素

int DeQueue_Q(LinkQueue &Q,int &e){

    QNode *P;

    if(Q.front==Q.rear) return ERROR;

    P=Q.front->next ;

    e=P->data;

    Q.front ->next =P->next;          //将原对头的后继p->next赋值给头结点后继

    if(Q.rear ==P)                 //当队列中只有一个元素时，q->rear指向头结点

        Q.rear =Q.front;

    free(P);

    return OK;

}

// 队判空

int QueueEmpty(LinkQueue Q)

{

    if(Q.front->next==NULL)

        return ERROR;

    else

        return OK;

 }

//-----------------------------------------------------------------------------------------------------

// BFSTraversed调用BFS每一个节点都被访问

void BFS(MGraph &G,int i){

    int j;

    LinkQueue Q;

    InitQueue_Q(Q);

    if(visited[i]==){    //未访问过该顶点

        printf("访问到顶点：%d\n\n",G.vexs[i]);

        visited[i]=;      // 置1

        EnQueue_Q(Q,i);      //将其入队列

        while(QueueEmpty(Q)){  // 循环队不为空QueueEmpty返回1

            DeQueue_Q(Q,i);    //将队头元素出队列，置为v

            for(j=;j<G.vexnum;j++){

                if(G.arcs[i][j].adj!= &&visited[j]==){      //未访问过的邻接点

                    printf("顶点走到的值：%d\n\n",G.vexs[j]);   // i 为v中未被访问的邻接点

                    visited[j]=;   // 访问置1

                    EnQueue_Q(Q,j);         //入队列

                }

            }

        }

    }

}

// 广度优先遍历图

int BFSTraverse(MGraph &G)

{

    int i,v,j,m;char x;

    LinkQueue Q;

    InitQueue_Q(Q);

    for(v=;v<G.vexnum;v++){   // 辅助数组置零

        visited[v]=;

    }

    printf("\n请输入遍历起点：\n");

    scanf("%d",&x);

    printf("遍历起点为：%d \n",x);

    m=LocateVex(G,x);

    if(m==-){

        printf("\n！！！您输入的起点不在顶点表内！！！\n");

        BFSTraverse(G);

    }

    visited[m]=;

        EnQueue_Q(Q,m);      //将其入队列

        while(QueueEmpty(Q)){  // 循环队不为空QueueEmpty返回1

            DeQueue_Q(Q,m);    //将队头元素出队列，置为v

            for(j=;j<G.vexnum;j++){

                if(G.arcs[m][j].adj!= &&visited[j]==){      //未访问过的邻接点

                    printf("顶点走到的值：%d\n\n",G.vexs[j]);   // i 为v中未被访问的邻接点

                    visited[j]=;   // 访问置1

                    EnQueue_Q(Q,j);         //入队列

                }

            }

        }

    for(i=;i<G.vexnum;i++){   // 保证所有节点被访问

        BFS(G, i );

    }

    return OK;

}

 //操作菜单

void OperateMenu(){      

    printf("\n\n--------------请选择元素处理方式---------\n\n");

    printf("！！！！！注：测试程序过程中，输入应全为数字！！！！！\n\n");

    printf("0> :退出\n\n");

    printf("1>: 深度遍历\n\n");

    printf("2>: 广度遍历\n\n");

    printf("3>: 输出邻接矩阵\n\n");

    printf("(注：选择过程中应为数字)\n\n");

    printf("请选择对元素的处理：");

}

void main() {

    MGraph G;//建立一个图的变量

    int w=,k,boo=;

    printf("请用户选择创建图 或 退出程序：\n\n");

    printf("注：程序测试过程中输入应全为数字\n\n");

    printf("创建图请输入：'1'\n\n");

    printf("退出请选择'0'或 其它！！\n\n");

    printf("请选择：");

    scanf("%d",&w);

    if(w==){

        boo=CreateDN(G);

        if(boo)

            printf("\n建图成功！！！\n");

        else

            printf("\n建图失败！！！\n");

        OperateMenu();

        scanf("%d",&k);

        while(k){

            switch(k){

            case :break;

            case :boo=DFSTraverse(G);    // 深度遍历

                if(boo)

                    printf("\n深度遍历成功！！！\n");

                else

                    printf("\n深度遍历失败！！！\n");

                break;

            case :boo=BFSTraverse(G);        // 广度遍历

                if(boo)

                    printf("\n广度遍历成功！！！\n");

                else

                    printf("\n广度遍历失败！！！\n");

                break;

            case :PrintGrapth(G);

            }

            OperateMenu();

            scanf("%d",&k);

        }

    }

}
巴特西

c_ 数据结构_图_邻接矩阵

最新文章

热门文章
