graph.cpp

一个关于图的数据结构程序

/*
  function: 图的表示和实现
  file:     graph.cpp
  date:     2008.11
*/
 
#include<stdio.h> 
#include<iostream>
#include"stdlib.h"
#include"string.h"

#define  TRUE      1
#define  FALSE     0
#define   OK       1
#define   ERROR    0
#define   INFEASIBLE   -1
#define    OVERFLOW    -2
#define     INFINITY   INT_MAX
#define    MAX_VERTEX_NUM   20
typedef  int Status,VRType,InfoType;
typedef  char VertexType;
typedef  enum{DG,DN,UDG,UDN} GraphKind;
typedef  struct ArcCell{
         VRType  adj;
         InfoType  *info;
         }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef  struct{
         VertexType vexs[MAX_VERTEX_NUM];
         AdjMatrix   arcs;
         int   vexnum,arcnum;
         GraphKind   kind;
         }MGraph;
//  定位 
Status LocateVex(MGraph G,int u)
{
       int i;
       for(i=1;i<=G.vexnum;i++)
       if(G.vexs[i-1]==u)
       return i-1;
       return -1;
}
//网的打印 
Status Print_Graph(MGraph &G)
{
       int i,j;
       for(i=0;i<G.vexnum;++i)
          {for(j=0;j<G.vexnum;++j)
            {if(G.arcs[i][j].adj!=INFINITY)
             {   printf("%d ",G.arcs[i][j].adj);
              }
             else
              printf("∞ ");
              } 
              printf("\n");
              }
              printf("\n");
			  return OK;
      }
//  图的打印 
Status Print_Graph1(MGraph &G)
{
       int i,j;
       for(i=0;i<G.vexnum;++i)
          {for(j=0;j<G.vexnum;++j)
            {if(G.arcs[i][j].adj!=INFINITY)
             {   printf("%d ",G.arcs[i][j].adj);
              }
             else
              printf("0 ");
              } 
              printf("\n");
              }
              printf("\n");
			  return OK;
      }
//  无向网
Status CreateUDN(MGraph &G)
{
       int v1,v2,w,i;
      printf("请输入顶点数：\n"); 
     scanf("%d",&G.vexnum);
      getchar();
       printf("请输入边数：\n");
        scanf("%d",&G.arcnum);
     
       for(i=0;i<G.vexnum;++i)
       { 
          printf("请输入第%d个的顶点标号：",i+1);
         scanf("%d",&G.vexs[i]);
       
       }
       for(i=0;i<G.vexnum;++i)
         for(int j=0;j<G.vexnum;++j)
              { G.arcs[i][j].adj=INFINITY;
             G.arcs[i][j].info=NULL;
              } 
        for(int k=0;k<G.arcnum;++k)
        {
                int i,j;
                printf("请输入第%d条边的一个顶点标号：",k+1);
                scanf("%d",&v1);
                i=LocateVex(G,v1); 
                printf("请输入与它对应的另一个顶点标号：");
                scanf("%d",&v2); 
                j=LocateVex(G,v2);
                printf("请输入此边的权：");
                scanf("%d",&w); 
              G.arcs[i][j].adj=w;
              G.arcs[j][i]=G.arcs[i][j];
        }
         printf("\n此无向网的邻接矩阵如下：\n");
       Print_Graph(G);
		return OK;
}
//  有向网
Status CreateDN(MGraph &G)
{
       int v1,v2,w,i;
      printf("请输入顶点数：\n"); 
     scanf("%d",&G.vexnum);
      getchar();
       printf("请输入边数：\n");
        scanf("%d",&G.arcnum);
     for(i=0;i<G.vexnum;++i)
       { 
          printf("请输入第%d个的顶点标号：",i+1);
         scanf("%d",&G.vexs[i]);
       
       }
       for(i=0;i<G.vexnum;++i)
         for(int j=0;j<G.vexnum;++j)
              { G.arcs[i][j].adj=INFINITY;
             G.arcs[i][j].info=NULL;
              } 
        for(int k=0;k<G.arcnum;++k)
        {
                int i,j;
                printf("请输入第%d条边的一个顶点标号：",k+1);
                scanf("%d",&v1);
                i=LocateVex(G,v1); 
                printf("请输入与它对应的另一个顶点标号：");
                scanf("%d",&v2); 
                j=LocateVex(G,v2);
                printf("请输入此边的权：");
                scanf("%d",&w); 
              G.arcs[i][j].adj=w;
        }
          printf("\n此有向网的邻接矩阵如下：\n");
        Print_Graph(G);
		return OK;
}
//  有向图
Status CreateDG(MGraph &G)
{
       int v1,v2,w,i;
      printf("请输入顶点数：\n"); 
     scanf("%d",&G.vexnum);
      getchar();
       printf("请输入边数：\n");
        scanf("%d",&G.arcnum);
     
       for(i=0;i<G.vexnum;++i)
       { 
          printf("请输入第%d个的顶点标号：",i+1);
         scanf("%d",&G.vexs[i]);
       
       }
       for(i=0;i<G.vexnum;++i)
         for(int j=0;j<G.vexnum;++j)
              { G.arcs[i][j].adj=INFINITY;
             G.arcs[i][j].info=NULL;
             
              } 
        for(int k=0;k<G.arcnum;++k)
        {
                int i,j;
                printf("请输入第%d条边的一个顶点标号：",k+1);
                scanf("%d",&v1);
                i=LocateVex(G,v1); 
                printf("请输入与它对应的另一个顶点标号：");
                scanf("%d",&v2); 
                j=LocateVex(G,v2);
              G.arcs[i][j].adj=1;
        }
        printf("\n此有向图的邻接矩阵如下：\n");
      Print_Graph1(G);
		return OK;
}
//  无向图
Status CreateUDG(MGraph &G)
{
       int v1,v2,w,i;
      printf("请输入顶点数：\n"); 
     scanf("%d",&G.vexnum);
      getchar();
       printf("请输入边数：\n");
        scanf("%d",&G.arcnum);
      for(i=0;i<G.vexnum;++i)
       { 
          printf("请输入第%d个的顶点标号：",i+1);
         scanf("%d",&G.vexs[i]);
       
       }
       for(i=0;i<G.vexnum;++i)
         for(int j=0;j<G.vexnum;++j)
              { G.arcs[i][j].adj=INFINITY;
             G.arcs[i][j].info=NULL;
             
              } 
        for(int k=0;k<G.arcnum;++k)
        {
                int i,j;
                printf("请输入第%d条边的一个顶点标号：",k+1);
                scanf("%d",&v1);
                i=LocateVex(G,v1); 
                printf("请输入与它对应的另一个顶点标号：");
                scanf("%d",&v2); 
                j=LocateVex(G,v2);
              G.arcs[i][j].adj=1;
              G.arcs[j][i]=G.arcs[i][j];
        }
        printf("\n此无向图的邻接矩阵如下：\n");
      Print_Graph1(G); 
		return OK;
}
//    选择图的方式 
Status CreateGraph(MGraph &G)
{
     printf("请做选择：1-有向图，2-有向网，3-无向图，4-无向网\n");
       printf("请输入要执行的方法的标号："); 
     scanf("%d",&G.kind); getchar();
        switch(G.kind-1){
           case DG:return CreateDG(G);
           case DN:return CreateDN(G);
           case UDG:return CreateUDG(G);
           case UDN:return CreateUDN(G);
           default:return ERROR;               
       }
       return OK;
}
//  主函数     
int main()
{
    MGraph g;
  CreateGraph(g);
  system("pause");
  return 0;
}