数据结构C语言版 图的邻接表存储表示和实现

    数据结构C语言版 图的邻接表存储表示和实现

    P163 

    编译环境：Dev-C++ 4.9.9.2

    日期：2011年2月15日 

*/

#include

// 图的邻接表存储表示 

#define MAX_NAME 3                    // 顶点字符串的最大长度+1 

#define MAX_VERTEX_NUM 20

typedef int InfoType;                // 存放网的权值 

typedef char VertexType[MAX_NAME];    // 字符串类型 

typedef enum{DG,DN,AG,AN}GraphKind; // {有向图,有向网,无向图,无向网} 

typedef struct ArcNode

{

    int adjvex;                    // 该弧所指向的顶点的位置 

    struct ArcNode *nextarc;    // 指向下一条弧的指针 

    InfoType *info;                // 网的权值指针） 

}ArcNode;    // 表结点 

typedef struct VNode

{

    VertexType data;            // 顶点信息 

    ArcNode *firstarc;            // 第一个表结点的地址,指向第一条依附该顶点的弧的指针 

 }VNode,AdjList[MAX_VERTEX_NUM];// 头结点 

typedef struct

{

    AdjList vertices;

    int vexnum,arcnum;    // 图的当前顶点数和弧数 

    int kind;            // 图的种类标志 

}ALGraph;

typedef int QElemType; // 队列类型 

//  单链队列－－队列的链式存储结构 

typedef struct QNode

{

    QElemType data;        //数据域

    struct QNode *next;    //指针域

}QNode,*QueuePtr;

typedef struct

{

    QueuePtr front,    //队头指针，指针域指向队头元素

        rear;        //队尾指针，指向队尾元素

}LinkQueue;

// 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 

int LocateVex(ALGraph G,VertexType u)

{

    int i;

for(i=0;i        if(strcmp(u,G.vertices[i].data)==0)

            return i;

    return -1;

}

// 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。

int CreateGraph(ALGraph *G)

{

    int i,j,k;

    int w;        // 权值 

    VertexType va,vb;

    ArcNode *p;

    printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");

    scanf("%d",&(*G).kind);

    printf("请输入图的顶点数和边数:（空格）\\n");

    scanf("%d%d", &(*G).vexnum, &(*G).arcnum);

    printf("请输入%d个顶点的值(<%d个字符):\\n",(*G).vexnum,MAX_NAME);

for(i = 0; i < (*G).vexnum; ++i)    // 构造顶点向量 

    {

        scanf("%s", (*G).vertices[i].data);

        (*G).vertices[i].firstarc = NULL;

    }

    if((*G).kind == 1 || (*G).kind == 3) // 网 

        printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\\n");

    else // 图 

        printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\\n");

for(k = 0;k < (*G).arcnum; ++k)    // 构造表结点链表 

    {

        if((*G).kind==1||(*G).kind==3) // 网 

            scanf("%d%s%s",&w,va,vb);

        else            // 图 

            scanf("%s%s",va,vb);

        i = LocateVex(*G,va); // 弧尾 

        j = LocateVex(*G,vb); // 弧头 

        p = (ArcNode*)malloc(sizeof(ArcNode));

     p->adjvex = j;

        if((*G).kind == 1 || (*G).kind == 3) // 网 

        {

         p->info = (int *)malloc(sizeof(int));

         *(p->info) = w;

        }

        else

         p->info = NULL; // 图 

     p->nextarc = (*G).vertices[i].firstarc; // 插在表头 

        (*G).vertices[i].firstarc = p;

     if((*G).kind >= 2) // 无向图或网,产生第二个表结点 

        {

            p = (ArcNode*)malloc(sizeof(ArcNode));

         p->adjvex = i;

            if((*G).kind == 3) // 无向网 

            {

             p->info = (int*)malloc(sizeof(int));

             *(p->info) = w;

            }

            else

             p->info = NULL; // 无向图 

         p->nextarc = (*G).vertices[j].firstarc; // 插在表头 

            (*G).vertices[j].firstarc = p;

        }

    }

    return 1;

}

// 销毁图G。

void DestroyGraph(ALGraph *G)

{

    int i;

    ArcNode *p,*q;

for(i = 0;i < (*G).vexnum; ++i)

    {

        p = (*G).vertices[i].firstarc;

        while(p)

        {

         q = p->nextarc;

            if((*G).kind%2) // 网 

             free(p->info);

            free(p);

            p=q;

        }

    }

    (*G).vexnum=0;

    (*G).arcnum=0;

 }

// 返回v的值。

VertexType* GetVex(ALGraph G,int v)

{

if(v>=G.vexnum||v<0)

        exit(0);

    return &G.vertices[v].data;

}

// 对v赋新值value。

int PutVex(ALGraph *G,VertexType v,VertexType value)

{

    int i;

    i=LocateVex(*G,v);

if(i > -1) // v是G的顶点 

    {

        strcpy((*G).vertices[i].data,value);

        return 1;

    }

    return 0;

}

// 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。

int FirstAdjVex(ALGraph G,VertexType v)

{

    ArcNode *p;

    int v1;

    v1 = LocateVex(G,v); // v1为顶点v在图G中的序号 

    p = G.vertices[v1].firstarc;

    if(p)

     return p->adjvex;

    else

        return -1;

}

// 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个

// 邻接点,    则返回-1。

int NextAdjVex(ALGraph G,VertexType v,VertexType w)

{

    ArcNode *p;

    int v1,w1;

    v1 = LocateVex(G,v); // v1为顶点v在图G中的序号 

    w1 = LocateVex(G,w); // w1为顶点w在图G中的序号 

    p = G.vertices[v1].firstarc;

while(p&&p->adjvex != w1) // 指针p不空且所指表结点不是w 

     p = p->nextarc;

if(!p||!p->nextarc) // 没找到w或w是最后一个邻接点 

        return -1;

else // p->adjvex==w

        // 返回v的(相对于w的)下一个邻接顶点的序号 

     return p->nextarc->adjvex;

}

// 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)。

void InsertVex(ALGraph *G,VertexType v)

{   

    strcpy((*G).vertices[(*G).vexnum].data,v); // 构造新顶点向量 

    (*G).vertices[(*G).vexnum].firstarc=NULL;

    (*G).vexnum++; // 图G的顶点数加1 

}

// 删除G中顶点v及其相关的弧。

int DeleteVex(ALGraph *G,VertexType v)

{

    int i,j;

    ArcNode *p,*q;

    j=LocateVex(*G,v);    // j是顶点v的序号 

if(j < 0 )            // v不是图G的顶点 

        return 0;

    p = (*G).vertices[j].firstarc;    // 删除以v为出度的弧或边 

    while( p )

    {

        q = p;

     p = p->nextarc;

        if((*G).kind % 2)    // 网 

         free(q->info);

        free(q);

        (*G).arcnum--;        // 弧或边数减1 

    }

    (*G).vexnum--;    // 顶点数减1 

for(i = j; i < (*G).vexnum; i++)    // 顶点v后面的顶点前移 

        (*G).vertices[i] = (*G).vertices[i+1];

    // 删除以v为入度的弧或边且必要时修改表结点的顶点位置值

for(i = 0; i < (*G).vexnum; i++)

    {

        p = (*G).vertices[i].firstarc; // 指向第1条弧或边 

        while(p) // 有弧 

        {

         if(p->adjvex == j)        // 是以v为入度的边。

            {

                if(p == (*G).vertices[i].firstarc) // 待删结点是第1个结点 

                {

                 (*G).vertices[i].firstarc = p->nextarc;

                    if((*G).kind % 2)    // 网 

                     free(p->info);

                    free(p);

                    p = (*G).vertices[i].firstarc;

                 if((*G).kind < 2)    // 有向 

                        (*G).arcnum--;    // 弧或边数减1 

                }

                else

                {

                 q->nextarc = p->nextarc;

                    if((*G).kind%2)    // 网 

                     free(p->info);

                    free(p);

                 p = q->nextarc;

                 if((*G).kind < 2)    // 有向 

                        (*G).arcnum--;    // 弧或边数减1 

                }

            }

            else

            {

             if(p->adjvex > j)

                 p->adjvex--; // 修改表结点的顶点位置值(序号) 

                q = p;

             p = p->nextarc;

            }

        }

    }

    return 1;

}

// 在G中增添弧,若G是无向的,则还增添对称弧。

int InsertArc(ALGraph *G,VertexType v, VertexType w)

{

    ArcNode *p;

    int w1,i,j;

    i=LocateVex(*G,v); // 弧尾或边的序号 

    j=LocateVex(*G,w); // 弧头或边的序号 

if(i < 0 || j < 0)

        return 0;

    (*G).arcnum++;    // 图G的弧或边的数目加1 

    if((*G).kind%2) // 网 

    {

        printf("请输入弧(边)%s→%s的权值: ",v,w);

        scanf("%d",&w1);

    }

    p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

    if((*G).kind%2) // 网 

    {

     p->info=(int*)malloc(sizeof(int));

     *(p->info)=w1;

    }

    else

     p->info = NULL;

p->nextarc = (*G).vertices[i].firstarc; // 插在表头 

    (*G).vertices[i].firstarc = p;

if((*G).kind >= 2)    // 无向,生成另一个表结点 

    {

        p = (ArcNode*)malloc(sizeof(ArcNode));

     p->adjvex = i;

        if((*G).kind == 3) // 无向网 

        {

         p->info = (int*)malloc(sizeof(int));

         *(p->info) = w1;

        }

        else

         p->info=NULL;

     p->nextarc=(*G).vertices[j].firstarc; // 插在表头 

        (*G).vertices[j].firstarc=p;

    }

    return 1;

}

// 在G中删除弧,若G是无向的,则还删除对称弧。

int DeleteArc(ALGraph *G,VertexType v,VertexType w)

{

    ArcNode *p,*q;

    int i,j;

    i = LocateVex(*G,v); // i是顶点v(弧尾)的序号 

    j = LocateVex(*G,w); // j是顶点w(弧头)的序号 

if(i < 0 || j < 0 || i == j)

        return 0;

    p=(*G).vertices[i].firstarc; // p指向顶点v的第一条出弧 

while(p&&p->adjvex!=j) // p不空且所指之弧不是待删除弧

    { // p指向下一条弧 

        q=p;

     p=p->nextarc;

    }

if(p&&p->adjvex==j) // 找到弧

    {

        if(p==(*G).vertices[i].firstarc) // p所指是第1条弧 

         (*G).vertices[i].firstarc=p->nextarc; // 指向下一条弧 

        else

         q->nextarc=p->nextarc; // 指向下一条弧 

        if((*G).kind%2) // 网 

         free(p->info);

        free(p); // 释放此结点 

        (*G).arcnum--; // 弧或边数减1 

    }

if((*G).kind>=2) // 无向,删除对称弧

    {

        p=(*G).vertices[j].firstarc; // p指隙サ鉾的第一条出弧 

     while(p&&p->adjvex!=i) // p不空且所指之弧不是待删除弧

        { // p指向下一条弧 

            q=p;

         p=p->nextarc;

        }

     if(p&&p->adjvex==i) // 找到弧

        {

            if(p==(*G).vertices[j].firstarc) // p所指是第1条弧 

             (*G).vertices[j].firstarc=p->nextarc; // 指向下一条弧 

            else

             q->nextarc=p->nextarc; // 指向下一条弧 

            if((*G).kind==3) // 无向网 

             free(p->info);

            free(p); // 释放此结点 

        }

    }

    return 1;

}

int visited[MAX_VERTEX_NUM];    // 访问标志数组(全局量) 

void(*VisitFunc)(char* v);        // 函数变量(全局量) 

//    算法7.5 P169

//    从第v个顶点出发递归地深度优先遍历图G。

void DFS(ALGraph G,int v)

{

    int w;

    VertexType v1,w1;

    strcpy(v1,*GetVex(G,v));

    visited[v] = 1;    // 设置访问标志为1(已访问) 

    VisitFunc(G.vertices[v].data); // 访问第v个顶点 

for(w = FirstAdjVex(G,v1); w >= 0;

        w = NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))

        if(!visited[w])

            DFS(G,w);    // 对v的尚未访问的邻接点w递归调用DFS 

}

//    算法7.4 P169

//    对图G作深度优先遍历。

void DFSTraverse(ALGraph G,void(*Visit)(char*))

{

    int v;

    // 使用全局变量VisitFunc,使DFS不必设函数指针参数

    VisitFunc = Visit; 

for(v = 0; v < G.vexnum; v++)

        visited[v] = 0;    // 访问标志数组初始化 

for(v = 0; v < G.vexnum; v++)

        if(!visited[v])

            DFS(G,v);        // 对尚未访问的顶点调用DFS 

        printf("\\n");

}

//    构造一个空队列Q。

int InitQueue(LinkQueue *Q)

{

    (*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));    //动态分配一个空间

    if(!(*Q).front)

        exit(0);

(*Q).front->next = NULL;    //队头指针指向空，无数据域，这样构成了一个空队列

    return 1;

}

//     插入元素e为Q的新的队尾元素。

int EnQueue(LinkQueue *Q, QElemType e)

{

    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));

    if( !p )    // 存储分配失败 

        exit(0);

    // 生成一个以为e为数据域的队列元素

p->data = e;

p->next = NULL;

    //将该新队列元素接在队尾的后面

(*Q).rear->next = p;

    (*Q).rear = p;

    return 1;

}

//     若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0。

int DeQueue(LinkQueue *Q,QElemType *e)

{

    QueuePtr p;

    if((*Q).front==(*Q).rear)

        return 0;

p=(*Q).front->next;    //队头元素

*e=p->data;

(*Q).front->next=p->next;

    if((*Q).rear==p)

        (*Q).rear=(*Q).front;

    free(p);

    return 1;

}

//    若Q为空队列,则返回1,否则返回0。

int QueueEmpty(LinkQueue Q)

{

    if(Q.front == Q.rear)

        return 1;

    else

        return 0;

}

//    算法7.6 P170

//    按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。

void BFSTraverse(ALGraph G,void(*Visit)(char*))

{

    int v,u,w;

    VertexType u1,w1;

    LinkQueue Q;

for(v = 0; v < G.vexnum; ++v)

        visited[v]=0;    // 置初值 

    InitQueue(&Q);            // 置空的辅助队列Q 

for(v = 0; v < G.vexnum; v++)    // 如果是连通图,只v=0就遍历全图 

        if(!visited[v])                // v尚未访问 

        {

            visited[v]=1;

            Visit(G.vertices[v].data);

            EnQueue(&Q,v);            // v入队列 

            while(!QueueEmpty(Q))    // 队列不空 

            {

                DeQueue(&Q,&u);        // 队头元素出队并置为u 

                strcpy(u1,*GetVex(G,u));

             for(w = FirstAdjVex(G,u1); w >= 0; w = NextAdjVex(G,

                    u1, strcpy(w1, *GetVex(G,w))))

                    if(!visited[w])    // w为u的尚未访问的邻接顶点 

                    {

                        visited[w] = 1;

                        Visit(G.vertices[w].data);

                        EnQueue(&Q,w);    // w入队 

                    }

            }

        }

        printf("\\n");

}

//    输出图的邻接表G。

void Display(ALGraph G)

{

    int i;

    ArcNode *p;

    switch(G.kind)

    {

    case DG: printf("有向图\\n");

        break;

    case DN: printf("有向网\\n");

        break;

    case AG: printf("无向图\\n");

        break;

    case AN: printf("无向网\\n");

    }

    printf("%d个顶点：\\n",G.vexnum);

for(i = 0; i < G.vexnum; ++i)

        printf("%s ",G.vertices[i].data);

    printf("\\n%d条弧(边):\\n", G.arcnum);

for(i = 0; i < G.vexnum; i++)

    {

        p = G.vertices[i].firstarc;

        while(p)

        {

         if(G.kind <= 1) // 有向 

            {

                printf("%s→%s ",G.vertices[i].data,

                 G.vertices[p->adjvex].data);

                if(G.kind == DN) // 网 

                 printf(":%d ", *(p->info));

            }

            else    // 无向(避免输出两次) 

            {

             if(i < p->adjvex)

                {

                    printf("%s－%s ",G.vertices[i].data,

                     G.vertices[p->adjvex].data);

                    if(G.kind == AN)    // 网 

                     printf(":%d ",*(p->info));

                }

            }

         p=p->nextarc;

        }

        printf("\\n");

    }

}

void print(char *i)

{

    printf("%s ",i);

}

int main()

{

    int i,j,k,n;

    ALGraph g;

    VertexType v1,v2;

    printf("请选择有向图\\n");

    CreateGraph(&g);

    Display(g);

    printf("删除一条边或弧，请输入待删除边或弧的弧尾 弧头：");

    scanf("%s%s",v1,v2);

    DeleteArc(&g,v1,v2);

    Display(g);

    printf("修改顶点的值，请输入原值 新值: ");

    scanf("%s%s",v1,v2);

    PutVex(&g,v1,v2);

    Display(g);

    printf("插入新顶点，请输入顶点的值: ");

    scanf("%s",v1);

    InsertVex(&g,v1);

    Display(g);

    printf("插入与新顶点有关的弧或边，请输入弧或边数目: ");

    scanf("%d",&n);

for(k=0;k    {

        printf("请输入另一顶点的值: ");

        scanf("%s",v2);

        printf("对于有向图，请输入另一顶点的方向(0:弧头 1:弧尾): ");

        scanf("%d",&j);

        if(j)

            InsertArc(&g,v2,v1);

        else

            InsertArc(&g,v1,v2);

    }

    Display(g);

    printf("删除顶点及相关的弧或边，请输入顶点的值: ");

    scanf("%s",v1);

    DeleteVex(&g,v1);

    Display(g);

    printf("深度优先搜索的结果:\\n");

    DFSTraverse(g,print);

    printf("广度优先搜索的结果:\\n");

    BFSTraverse(g,print);

    DestroyGraph(&g);

#if 0 

    printf("请顺序选择有向网,无向图,无向网\\n");

for(i=0;i<3;i++) // 验证另外3种情况 

    {

        CreateGraph(&g);

        Display(g);

        printf("插入新顶点，请输入顶点的值: ");

        scanf("%s",v1);

        InsertVex(&g,v1);

        printf("插入与新顶点有关的弧或边，请输入弧或边数: ");

        scanf("%d",&n);

     for(k=0;k        {

            printf("请输入另一顶点的值: ");

            scanf("%s",v2);

         if(g.kind<=1) // 有向 

            {

                printf("对于有向图或网，请输入另一顶点的方向(0:弧头 1:弧尾): ");

                scanf("%d",&j);

                if(j)

                    InsertArc(&g,v2,v1);

                else

                    InsertArc(&g,v1,v2);

            }

            else // 无向 

                InsertArc(&g,v1,v2);

        }

        Display(g);

        printf("删除顶点及相关的弧或边，请输入顶点的值: ");

        scanf("%s",v1);

        DeleteVex(&g,v1);

        Display(g);

        DestroyGraph(&g);

    }

#endif

    system("pause");

    return 0;

}

/*

输出效果：

请选择有向图

请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 0

请输入图的顶点数和边数:（空格）

3 2

请输入3个顶点的值(<3个字符):

a

b

c

请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):

a b

b c

有向图

3个顶点：

a b c

2条弧(边):

a→b

b→c

删除一条边或弧，请输入待删除边或弧的弧尾 弧头：b c

有向图

3个顶点：

a b c

1条弧(边):

a→b

修改顶点的值，请输入原值 新值: b d

有向图

3个顶点：

a d c

1条弧(边):

a→d

插入新顶点，请输入顶点的值: e

有向图

4个顶点：

a d c e

1条弧(边):

a→d

插入与新顶点有关的弧或边，请输入弧或边数目: 1

请输入另一顶点的值: d

对于有向图，请输入另一顶点的方向(0:弧头 1:弧尾): 1

有向图

4个顶点：

a d c e

2条弧(边):

a→d

d→e

删除顶点及相关的弧或边，请输入顶点的值: c

有向图

3个顶点：

a d e

2条弧(边):

a→d

d→e

深度优先搜索的结果:

a d e

广度优先搜索的结果:

a d e

请按任意键继续. . .

*/