求邻接表的算法问题，高手请进 - 编程论坛

#2

xichong2010-05-29 21:09

#include <stdio.h>
#include <stdlib.h>
typedef int VertexType;
typedef struct ArcNode//表结点
{
    int adjvex;//弧所指向的顶点的位置
    struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode//头结点
{
    VertexType data;//顶点信息
    ArcNode *firstarc;//指向第一条依附该弧的顶点指针
}VNode,*AdjList;
typedef struct
{
    AdjList vertices;
    int vexnum;//图的**当前**顶点数
}ALGraph;

/////创建图的邻接矩阵
void CreatAjacentMatrix(int *array,int n)//创建邻接矩矩阵(n行n列)
{
    int a;
    int i,j,flag=0;
    printf("请输入一个%d行%d列的关于图的邻接矩阵:\n",n,n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&a);
            *(array+i*n+j)=a;
        }
}
void PrintAjacentMatrix(int *array,int n)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            printf("%5d ",*(array+i*n+j));
        printf("\n");
    }
}

////将邻接矩阵导出为图的邻接表形式
void CreatAdjList(int *array,int n,ALGraph *G)
{
    int i,j;
    ArcNode *p;//表结点
    G->vexnum=n;//初始化顶点数
    G->vertices=(VNode *)malloc((n+1)*sizeof(VNode));//头结点数组,开辟n+1长度的数组空间
    for(i=1;i<=n;i++)//初始化头结点数组
    {
        G->vertices[i].data=i;
        G->vertices[i].firstarc=NULL;
    }
    //////////
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(*(array+i*n+j)==1)
            {
                p=(ArcNode *)malloc(sizeof(ArcNode));
                p->adjvex=j+1;
                p->nextarc=G->vertices[i+1].firstarc;
                G->vertices[i+1].firstarc=p;
            }
        }
}

void main()
{
    int n;
    int *A;
    ALGraph G;
    printf("请输入你想创建的邻接矩矩阵的行列数(即顶点数):\n");
    scanf("%d",&n);
    A=(int *)malloc(n*n*sizeof(int));
    CreatAjacentMatrix(A,n);
    printf("请输出图的邻接矩阵A:\n");
    PrintAjacentMatrix(A,n);
    CreatAdjList(A,n,&G);
}

#3

寒风中的细雨2010-05-30 11:10

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

#define MAX_VERTEX_NUM 20

typedef char Vertex_Type[5];

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

typedef struct Arc_Node
{
    int adjvex;//表示邻接顶点在向量表中的位置
    struct Arc_Node *next_arc;
    int weight;//表示权
}Arc_Node;

typedef struct Vertex_Node
{
    Vertex_Type data;
    Arc_Node *first_arc;
}Vertex_Node;

typedef struct
{
    Vertex_Node        vertexs_vectors[MAX_VERTEX_NUM];
    int vertex_num;
    int arc_num;
    Graph_Kind kind;
}ALGraph;

//初始化图中的有关信息
void Init_ALGraph( ALGraph &G )
{
    printf("输入图的类型(DG:0 DN:1 UDG:2 UDN:3): ");
    scanf("%d", &G.kind );
    printf("输入图的顶点数:");
    scanf("%d", &G.vertex_num );
    printf("输入图的边数:");
    scanf("%d", &G.arc_num );
    int i;

    printf("输入定点向量:");
    for( i=0; i<G.vertex_num; ++i )
    {
        scanf("%s", G.vertexs_vectors[i].data);
        G.vertexs_vectors[i].first_arc = NULL;
    }
}
//获取定点在定点向量中的位置如果出错就终止运行
int Get_Vertex_Location( ALGraph G, Vertex_Type V )
{
    int i;
    for( i=0; i<G.vertex_num; ++i )
        if( strcmp( V, G.vertexs_vectors[i].data ) == 0 )
            return i;
    exit(0);
}

void Greate_ALGraph( ALGraph &G )
{
    Init_ALGraph( G );

    Vertex_Type vertex_1, vertex_2;
    int i, v1_site, v2_site;

    printf("输入图的弧(形如 v1 - v2):\n");
    for( i=0; i<G.arc_num; ++i )
    {
        scanf("%s %*s %s", vertex_1, vertex_2);
        v1_site = Get_Vertex_Location( G, vertex_1 );
        v2_site = Get_Vertex_Location( G, vertex_2 );

        Arc_Node *p1, *p2;
        p1 = (Arc_Node *) malloc (sizeof(Arc_Node));
        p1->adjvex = v2_site;
        p1->weight = 0;//初始化权值为零
        p1->next_arc = G.vertexs_vectors[v1_site].first_arc;
        G.vertexs_vectors[v1_site].first_arc = p1;
        switch( G.kind )
        {
        case DG:
            break;
        case DN:
            printf("输入权值:");
            scanf("%d", &p1->weight );
            break;
        case UDG:
            p2 = (Arc_Node *) malloc (sizeof(Arc_Node));
            p2->adjvex = v1_site;
            p2->weight = 0;//初始化权值为零
            p2->next_arc = G.vertexs_vectors[v2_site].first_arc;
            G.vertexs_vectors[v2_site].first_arc = p2;//头插入
            break;
        case UDN:
            printf("输入权值:");
            scanf("%d", &p1->weight );
            p2 = (Arc_Node *) malloc (sizeof(Arc_Node));
            p2->adjvex = v1_site;
            p2->weight = p1->weight;//初始化权值为零
            p2->next_arc = G.vertexs_vectors[v2_site].first_arc;
            G.vertexs_vectors[v2_site].first_arc = p2;//头插入
            break;
        default:
            exit(0);
        }
    }
}

void Print_ALGraph( ALGraph G )
{
    int i;
    for( i=0; i<G.vertex_num; ++i )
    {
        Arc_Node *p = G.vertexs_vectors[i].first_arc;
        while( p )
        {
            switch( G.kind )
            {
            case UDG:
                printf("( %s --", G.vertexs_vectors[i].data);
                printf(" %s )", G.vertexs_vectors[p->adjvex].data);break;
            case UDN:
                printf("( %s --", G.vertexs_vectors[i].data);
                printf(" %s , %d )", G.vertexs_vectors[p->adjvex].data, p->weight);break;
            case DG:
                printf("< %s ->", G.vertexs_vectors[i].data);
                printf(" %s >", G.vertexs_vectors[p->adjvex].data);break;
            case DN:
                printf("< %s ->", G.vertexs_vectors[i].data);
                printf(" %s , %d >", G.vertexs_vectors[p->adjvex].data, p->weight);break;
            default:
                exit(0);
            }
            p = p->next_arc;
            printf("\n");
        }
    }
}

int main()
{
    ALGraph G;

    Greate_ALGraph( G );

    Print_ALGraph( G );
    return 0;
}

#4

寒风中的细雨2010-05-30 11:10

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

#5

qq88011032010-06-01 19:52

谢谢了请问你的编译工具是什么可以共享一下吗

#6

寒风中的细雨2010-06-01 23:42

Visual C++ 6.0
随便下载就可以