图的邻接矩阵的建立问题 - 编程论坛

#2

2010-05-24 17:19

typedef struct
{
     VertexType  vexs[MAXNODE];//点集
     EdgeType arcs[MAXNODE][MAXNODE];//弧集
     int vexnum,arcnum;//点数，弧数
}MGgraph;

MGgraph CreatMGgraph()
{
     MGgraph G;
     int i,j;
     VertexType x;
     G.vexnum=0;
     scanf("%c",&x);
     while(x!='#')//用一个字符表示一点
     {
         G.vexnum++;
         G.vexs[G.vexnum]=x;
         scanf("%c",&x);
     }
     G.arcnum=0;
     for(i=1;i<=G.vexnum;i++)
         for(j=1;j<=G.vexnum;j++)
         G.arcs[i][j]=0;
     scanf("%d",&i);
     scanf("%d",&j);
     while(i&&j)//建立无向图
    {
        G.arcs[i][j]=1;
        G.arcs[j][i]=1;
        G.arcnum++;
        scanf("%d",&i);
        scanf("%d",&j);
    }
   //如果建立有向图用下面括号里的算法
  /*（while(i&&j)//i、j同是为0时结束
    {
        G.arcs[i][j]=1;
        G.arcnum++;
        scanf("%d",&i);
        scanf("%d",&j);
    }
   ）*/

    for(i=1;i<=G.vexnum;i++)
    G.arcs[i][i]=0;

    return G;
  }

#3

寒风中的细雨2010-05-30 09:31

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

#define MAX_VERTEX_NUM 20

typedef int Arc_Type;
typedef char VerTex_Type[5];

typedef enum
{
    DG, DN, UDG, UDN
}Graph_Kind;

typedef struct ArcCell
{
    Arc_Type adj;
    //Info_Type *info;
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
    VerTex_Type vexs[MAX_VERTEX_NUM];
    AdjMatrix    arcs;
    int vertex_num;
    int arc_num;
    Graph_Kind kind;
}MGraph;

void Init_MGraph( MGraph &G )
{
    printf("输入图的定点数:");
    scanf("%d", &G.vertex_num );
    printf("输入图的边数:");
    scanf("%d", &G.arc_num );
    printf("输入图的类型(DG:0 DN:1 UDG:2 UDN:3):");
    scanf("%d", &G.kind);
    int i, j;

    printf("输入节点向量(定点之间用空格隔开):");
    for( i=0; i<G.vertex_num; ++i )
        scanf("%s", G.vexs[i] );

    for( i=0; i<G.vertex_num; ++i )
        for( j=0; j<G.vertex_num; ++j )
            G.arcs[i][j].adj = 0;
}

int Get_Vertex_Location( MGraph G, VerTex_Type V )
{
    int i;
    for( i=0; i<G.vertex_num; ++i )
        if( strcmp( V, G.vexs[i] ) == 0 )
            return i;
    exit(0);
}

void Create_MGraph( MGraph &G )
{
    Init_MGraph( G );
    int i, v1_site, v2_site;
    VerTex_Type v1, v2;

    printf("输入与弧相关联的顶点(形如v1 - v2):\n");
    for( i=0; i<G.arc_num; ++i )
    {
        scanf("%s %*s %s", v1, v2 );
        v1_site = Get_Vertex_Location( G, v1 );
        v2_site = Get_Vertex_Location( G, v2 );
        switch( G.kind )
        {
        case DG:
            G.arcs[v1_site][v2_site].adj = 1;
            break;
        case DN:
            printf("输入权值:");
            scanf("%d", &G.arcs[v1_site][v2_site].adj);
            break;
        case UDG:
            G.arcs[v1_site][v2_site].adj = G.arcs[v2_site][v1_site].adj = 1;
            break;
        case UDN:
            printf("输入权值:");
            scanf("%d", &G.arcs[v1_site][v2_site].adj);
            G.arcs[v2_site][v1_site].adj = G.arcs[v1_site][v2_site].adj ;
            break;
        default:
            exit(0);
        }
    }
}

void Print_MGraph( MGraph G )
{
    int i, j;

    printf("输出弧:\n");
    for( i=0; i<G.vertex_num; ++i )
        for( j=0; j<G.vertex_num; ++j )
            if( G.arcs[i][j].adj )
            {
                printf("( %s--", G.vexs[i]);
                printf("%s )\n", G.vexs[j]);
            }
}

void Print_Matrix( MGraph G )
{
    int i, j;
    printf("图的邻接矩阵为:\n");
    for( i=0; i<G.vertex_num; ++i )
    {
        for( j=0; j<G.vertex_num; ++j )
            printf(" %d", G.arcs[i][j].adj );
        printf("\n");
    }
}

int main()
{
    MGraph G;

    Create_MGraph( G );

    Print_MGraph( G );
    Print_Matrix( G );

    return 0;
}

#4

寒风中的细雨2010-05-30 09:52

只有本站会员才能查看附件，请登录

#5

dsgejie2010-12-25 23:07

厉害