圖的鄰接表存儲(chǔ)表示示例講解

更新時(shí)間：2013年11月26日 09:36:40 作者：

這篇文章主要介紹了圖的鄰接表存儲(chǔ)表示,大家參考使用

復(fù)制代碼代碼如下:

//---------圖的鄰接表存儲(chǔ)表示-------

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

#define MAX_VERTEXT_NUM 20

typedef int InfoType;
typedef char VertextType;

typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextArc;
    InfoType *info;
}ArcNode;

typedef struct VNode
{
VertextType data;
ArcNode *firstArc;
}VNode, AdjList[MAX_VERTEXT_NUM];

typedef struct
{
    AdjList verTices;
    int vexNum;
    int arcNum;
    int kind;
}ALGraph;

void CreateGraph(ALGraph *G);
void DisplayGraph(ALGraph *G);

int main()
{
    ALGraph *Graph = (ALGraph *)malloc(sizeof(ALGraph));
    CreateGraph(Graph);
    DisplayGraph(Graph);

system("pause");
}

void CreateGraph(ALGraph *G)
{
    int i,j,k;
    ArcNode *arcNode;
    printf_s("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");
    scanf_s("%d,%d",&G->vexNum, &G->arcNum);

    //建立頂點(diǎn)表
    printf_s("建立頂點(diǎn)表\n");
    for (i = 0; i < G->vexNum; i++)
    {
        printf_s("請(qǐng)輸入第%d個(gè)頂點(diǎn):", i);
        fflush(stdin);//刷新緩沖區(qū)
        G->verTices[i].data = getchar();
        G->verTices[i].firstArc = NULL;
    }

    //建立邊表
    printf_s("建立邊表\n");
    for (k = 0; k < G->arcNum; k++)
    {
        printf_s("請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)");
        scanf_s("%d,%d", &i, &j);
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex = j;
        arcNode->nextArc = G->verTices[i].firstArc;//插入表頭
        G->verTices[i].firstArc = arcNode;

        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex = i;
        arcNode->nextArc = G->verTices[j].firstArc;//插入表頭
        G->verTices[j].firstArc = arcNode;
    }
}

void DisplayGraph(ALGraph *G)
{
    int i;
    for (i = 0; i < G->vexNum; i++)
    {
        printf_s("%d->", i);
        while (G->verTices[i].firstArc != NULL)
        {
            printf_s("%d->", G->verTices[i].firstArc->adjvex);
            G->verTices[i].firstArc = G->verTices[i].firstArc->nextArc;
        }
        printf_s("\n");
    }
}

復(fù)制代碼代碼如下:

請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：6,7
建立頂點(diǎn)表
請(qǐng)輸入第0個(gè)頂點(diǎn):0
請(qǐng)輸入第1個(gè)頂點(diǎn):1
請(qǐng)輸入第2個(gè)頂點(diǎn):2
請(qǐng)輸入第3個(gè)頂點(diǎn):3
請(qǐng)輸入第4個(gè)頂點(diǎn):4
請(qǐng)輸入第5個(gè)頂點(diǎn):5
建立邊表
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)0,1
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)0,4
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)1,4
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)1,5
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)2,3
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)2,5
請(qǐng)輸入（vi-vj）的頂點(diǎn)對(duì)序號(hào)3,5
0->4->1->
1->5->4->0->
2->5->3->
3->5->2->
4->1->0->
5->3->2->1->
請(qǐng)按任意鍵繼續(xù). . .