graph.cpp文件以邻接矩阵和邻接表的形式来表示图的存储

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #include<math.h>
    4. #define INF 32767  //定义∞ 
    5. #define MAXV 100   //最大顶点个数
    6. typedef char InfoType;
    7. //-----------------------------定义邻接矩阵类型------------------------------------------------
    8. typedef struct{
    9.     int no;                        //顶点编号
    10.     InfoType info;                 //顶点其它信息
    11. }VertexType;                       //顶点类型
    12. typedef struct{
    13.     int edges[MAXV][MAXV];         //邻接矩阵数组
    14.     int n,e;                       //顶点数，边数
    15.     VertexType vex[MAXV];          //存放顶点信息
    16. }MatGraph;                         //图的邻接矩阵类型
    18. //------------------------------定义邻接表类型-------------------------------------------------
    19. typedef struct ArcNode{
    20.     int adjvex;                    //该边邻接点编号
    21.     ArcNode* nextarc;              //指向下一条边的指针
    22.     int weight;                    //该边的相关信息：权重
    23. }ArcNode;                          //边节点类型
    25. typedef struct VNode{
    26.     InfoType info;                 //顶点信息
    27.     int count;                     //顶点入度
    28.     ArcNode * firstarc;            //指向第一条边
    29. }VNode;                            //邻接表表头类型
    31. typedef struct{
    32.     VNode adjlist[MAXV];           //邻接表表头数组
    33.     int n,e;                       //图的顶点数和边数
    34. }AdjGraph;                         //图的邻接表类型
    36. //-------------------------邻接矩阵的基本操作------------------------------------------------
    37. void CreateMatGraph(MatGraph &g,int A[MAXV][MAXV],int n,int e){       //创建邻接矩阵
    38.     g.n=n;
    39.     g.e=e;
    40.     for(int i=0;i<g.n;i++){
    41.         for(int j=0;j<g.n;j++){
    42.              g.edges[i][j]=A[i][j];
    43.         }
    44.     }
    45. }
    47. void DispMatGraph(MatGraph g)         //输出邻接矩阵
    48. {
    49.     for(int i=0;i<g.n;i++){
    50.         for(int j=0;j<g.n;j++)
    51.           {
    52.              if(g.edges[i][j]!=INF)
    53.                 printf("%4d",g.edges[i][j]);
    54.              else
    55.                 printf("%4s","   ∞");
    56.           }
    57.           printf("\n");
    58.     }
    59. }
    61. //-------------------------邻接表的基本操作--------------------------------------------------
    62. void CreateAdjGraph(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)     //创建图的邻接表
    63. {
    64.     ArcNode *p;
    65.     G=(AdjGraph*)malloc(sizeof(AdjGraph));
    66.     for(int i=0;i<n;i++){
    67.         G->adjlist[i].firstarc=NULL;                                //给邻接表中所有头结点的额指针域设置初值
    68.     }
    69.     for(int i=0;i<n;i++){
    70.         for(int j=n-1;j>=0;j--){                                    //存在一条有向图边<i,j>，从i->j做一遍，如果是无向图的边(i,j),必须从j->i再做一边
    71.             if(A[i][j]!=0&&A[i][j]!=INF){
    72.                    p=(ArcNode*)malloc(sizeof(ArcNode));             //创建一个节点P
    73.                    p->adjvex=j;
    74.                    p->weight=A[i][j];
    75.                    p->nextarc=G->adjlist[i].firstarc;               //采用头插法插入节点P,插到i结点后面
    76.                    G->adjlist[i].firstarc=p;                       
    77.             }
    78.         }
    79.     }
    80.     G->n=n;
    81.     G->e=n;
    82. }
    84. void DispAdjGraph(AdjGraph *G)                                     //输出邻接表
    85. {
    86.     ArcNode *p;
    87.     for(int i=0;i<G->n;i++){
    88.         p=G->adjlist[i].firstarc;
    89.         printf("%3d",i);
    90.         while(p!=NULL){
    91.             printf("%3d[%d]->",p->adjvex,p->weight);
    92.             p=p->nextarc;
    93.         }
    94.         printf("^\n");
    95.     }
    96. }
    98. void DestroyAdjGraph(AdjGraph *&G){                                  //销毁图的邻接表
    99.      ArcNode * pre,*p;
    100.      for(int i=0;i<G->n;i++){                                        //扫描所有的单链表
    101.          pre=G->adjlist[i].firstarc;                                 //p指向第i个单链表的首结点
    102.          if(pre!=NULL){
    103.               p=pre->nextarc;
    104.          while(p!=NULL){
    105.               free(pre);                                             //释放第i个单链表的所有边结点
    106.               pre=p;
    107.               p=p->nextarc;
    108.          }
    109.          free(pre);
    110.         }
    111.     }
    112.     free(G);                                                        //释放头结点数组
    113. }

    操作：

    #include"graph.cpp"
int main(){
    MatGraph g;
    AdjGraph * G;
    int A[MAXV][MAXV]={
        {0,5,INF,7,INF,INF},
        {INF,0,4,INF,INF,INF},
        {8,INF,0,INF,INF,9},
        {INF,INF,5,0,INF,6},
        {INF,INF,INF,5,0,INF},
        {3,INF,INF,INF,1,0}
    };
    int n=6,e=10;
    CreateMatGraph(g,A,n,e);
    printf("(1)图G的邻接矩阵:\n");
    DispMatGraph(g);
    CreateAdjGraph(G,A,n,e);
    printf("(2)图G的邻接表:\n");
    DispAdjGraph(G);
    printf("(3)销毁图G的邻接表\n");
    DestroyAdjGraph(G);
    return 1;   
}

    运行结果：
    image.png