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_VERt

程序主要实现了图的深度遍历和广度遍历。

#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 10typedef 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 = 0; i < G.vexnum;++i){        printf("%d",G.vexs[i]);    }    printf("顶点间的关系:\n");    for (i = 0; i < G.vexnum; ++i){        for (j = 0; j < G.vexnum; ++j){            printf("%d ",G.arcs[i][j].adj);        }        printf("\n");    }}//---------------------------------------------------------------------------//根据顶点本身数据，判断出顶点在二维数组中的位置int LocateVex(MGraph &G,int v){    //遍历一维数组，找到变量v    for (int i=0; i<G.vexnum; ++i) {        if (G.vexs[i]==v) {            return i;        }    }    return -1; //如果找不到，返回-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<20 && G.arcnum<=(x*(x-1)/2)){        printf("请(回车)输入 %d 个顶点的值：\n",G.vexnum);        for (i=0; i<G.vexnum; i++) {      // 循环输入顶点值            scanf("%d",&(G.vexs[i]));        }                for (i=0; i<G.vexnum; ++i) {        // 初始化邻接矩阵            for (j=0; j<G.vexnum; ++j) {                G.arcs[i][j].adj=0;            }        }        printf("\n请实现 %d 条边的连接：\n",G.arcnum);        for (k=0;k<G.arcnum; ++k) {     // 构造邻接矩阵            printf("\n请输入哪‘两个‘顶点要进行连接边：");            fflush(stdin);            scanf("%d",&v1);            n=LocateVex(G,v1);    //定位顶点            scanf("%d",&v2);            m=LocateVex(G,v2);            while (m==-1||n==-1) {                   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==1){                printf("\n!!!两顶点已经被连接!!!\n");                printf("请重新输入两顶点：");                fflush(stdin);                scanf("%d",v2);        //        if(G.arcs[n][m].adj!=1){break;    }                while (m==-1||n==-1) {                       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=1;    //无向图的二阶矩阵沿主对角线对称        }    }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]=1;    for(j=0;j<G.vexnum;++j){                if(G.arcs[v][j].adj!=0 && visited[j]==0){   // 如果有邻接点则继续递归            DFS(G,j);        }    }}// 顶点的非连通图的深度遍历int DFSTraverse(MGraph &G){       int n=0,v,x,m;    for(v=0;v<G.vexnum;v++) visited[v]=0;    // 把所有的标记置为0    printf("\n请输入遍历起点：\n");    scanf("%d",&x);    printf("遍历起点为：%d \n",x);    m = LocateVex(G,x);    if(m==-1){        printf("\n！！！您输入的起点不在顶点表内！！！\n");        DFSTraverse(G);    }    //n=LocateVex(G,x);    visited[m]=1;        for(j=0;j<G.vexnum;++j){                if(G.arcs[n][j].adj!=0 && visited[j]==0){   // 如果有邻接点则继续递归            DFS(G,j);        }    }    //DFS(G,m);    for(v=0;v<G.vexnum;++v){     // 判断是否还有没有被遍历的图        if(visited[v]==0){            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]==0){    //未访问过该顶点             printf("访问到顶点：%d\n\n",G.vexs[i]);        visited[i]=1;      // 置1        EnQueue_Q(Q,i);      //将其入队列         while(QueueEmpty(Q)){  // 循环队不为空QueueEmpty返回1            DeQueue_Q(Q,i);    //将队头元素出队列，置为v            for(j=0;j<G.vexnum;j++){                if(G.arcs[i][j].adj!=0 &&visited[j]==0){      //未访问过的邻接点                     printf("顶点走到的值：%d\n\n",G.vexs[j]);   // i 为v中未被访问的邻接点                                        visited[j]=1;   // 访问置1                    EnQueue_Q(Q,j);         //入队列                 }                }         }     }}// 广度优先遍历图int BFSTraverse(MGraph &G){     int i,m;char x;    linkQueue Q;    InitQueue_Q(Q);    for(v=0;v<G.vexnum;v++){   // 辅助数组置零        visited[v]=0;    }    printf("\n请输入遍历起点：\n");    scanf("%d",x);    m=LocateVex(G,x);    if(m==-1){        printf("\n！！！您输入的起点不在顶点表内！！！\n");        BFSTraverse(G);    }    visited[m]=1;        EnQueue_Q(Q,m);      //将其入队列         while(QueueEmpty(Q)){  // 循环队不为空QueueEmpty返回1            DeQueue_Q(Q,m);    //将队头元素出队列，置为v            for(j=0;j<G.vexnum;j++){                if(G.arcs[m][j].adj!=0 &&visited[j]==0){      //未访问过的邻接点                     printf("顶点走到的值：%d\n\n",j);         //入队列                 }                }         }     for(i=0;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=0,boo=1;    printf("请用户选择创建图 或 退出程序：\n\n");    printf("注：程序测试过程中输入应全为数字\n\n");    printf("创建图请输入：‘1‘\n\n");    printf("退出请选择‘0‘或 其它！！\n\n");    printf("请选择：");    scanf("%d",&w);    if(w==1){        boo=Createdn(G);        if(boo)            printf("\n建图成功！！！\n");        else            printf("\n建图失败！！！\n");        OperateMenu();        scanf("%d",&k);        while(k){            switch(k){            case 0:break;            case 1:boo=DFSTraverse(G);    // 深度遍历                if(boo)                    printf("\n深度遍历成功！！！\n");                else                    printf("\n深度遍历失败！！！\n");                break;            case 2:boo=BFSTraverse(G);        // 广度遍历                if(boo)                    printf("\n广度遍历成功！！！\n");                else                    printf("\n广度遍历失败！！！\n");                break;            case 3:PrintGrapth(G);            }            OperateMenu();            scanf("%d",&k);        }     }}

总结

以上是内存溢出为你收集整理的c_ 数据结构_图_邻接矩阵全部内容，希望文章能够帮你解决c_ 数据结构_图_邻接矩阵所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。