目錄

1.鄰接表相關(guān)知識補充

?2. 圖的鄰接存儲表示

3.測試輸入與輸出樣例

4.代碼實現(xiàn)

4.1 創(chuàng)建無向圖鄰接表

4.2 輸入無向圖的鄰接表

---

1.鄰接表相關(guān)知識補充

定義：

對于圖中每個頂點 vi，把所有鄰接于 vi的頂點（對有向圖是將從vi出發(fā)的弧的弧頭頂點鏈接在一起）鏈接成一個帶頭結(jié)點的單鏈表，將所有頭結(jié)點順序存儲在一個一維數(shù)組中。

示例：下面左圖G2對應(yīng)的鄰接表如右邊所示。

?2. 圖的鄰接存儲表示

#define MAXVEX 20 /*最大頂點數(shù)*/
typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向圖，有向網(wǎng)，無向圖，無向網(wǎng)*/
typedef struct ENode /*表結(jié)點類型*/
{
    int adjvex;
    struct ENode *nextarc;
    int weight;
}ENode;
typedef int VexType;
typedef struct VNode /*頭結(jié)點類型*/
{
    VexType vex;
    ENode *firstarc;
}VNode, AdjList[MAXVEX]; /*鄰接表類型定義*/
typedef struct
{
    AdjList vertices; /*用鄰接表存儲頂點集合及邊集合*/
    int vexnum,edgenum;
    GraphKind kind;
}ALGraph; /*鄰接表存儲的圖的類型定義*/

3.測試輸入與輸出樣例

測試輸入：

2 5 6

0 1 0 3 1 2 1 4 2 3 2 4

預(yù)期輸出：

0->3->1

1->4->2->0

2->4->3->1

3->2->0 4->2->1

4.代碼實現(xiàn)

這里主要寫了兩個函數(shù)，一個用于生成無向圖的鄰接表，一個用于輸出其鄰接表

4.1 創(chuàng)建無向圖鄰接表

void CreateUDG_ALG(ALGraph &g) /*構(gòu)造無向圖的鄰接表*/
{
    int kind,dot,edges;
    scanf("%d %d %d",&kind,&dot,&edges);
    g.vexnum=dot;g.edgenum=edges;g.kind=(GraphKind)kind;
/*這里有關(guān)枚舉的類型再賦值問題(g.kind)，枚舉變量的再賦值不能直接是數(shù)字，如果是數(shù)字的話需要一個枚舉/類型的強制轉(zhuǎn)換*/
    VNode*pn=NULL;
    for(int i=0;i<dot;i++) //創(chuàng)建六個頭結(jié)點
    {
        pn=new VNode;
        pn->vex=i;// VexType類型就是int類型
        pn->firstarc=NULL;//初始化置空
        g.vertices[i]=*pn;   //vertices數(shù)組類型是頭結(jié)點類型
    }
    int x,y;
    ENode *en=NULL;ENode *tn=NULL; //都是邊結(jié)點類型
    for(int j=0;j<edges;j++) //6個變，所以循環(huán)6次 開始創(chuàng)建鄰接表
    {
        en= new ENode;    //邊結(jié)點指針
        // scanf("%d",&x);  //第一個點
        // scanf("%d",&y);  //第二個點
        scanf("%d%d",&x,&y);  //也可以寫在一起

        //將輸入的信息添加到邊結(jié)點上去，采用鏈表頭插法的方式不停改變我們的指針
        en->adjvex=y;en->weight=0;en->nextarc=g.vertices[x].firstarc;
        g.vertices[x].firstarc=en;

        //下面這段代碼也是一樣的,采用鏈表頭插法的方式        
        tn= new ENode;    //邊結(jié)點指針
        tn->adjvex=x;tn->weight=0;tn->nextarc=g.vertices[y].firstarc;
        g.vertices[y].firstarc=tn;
    } 
}

4.2 輸入無向圖的鄰接表

void PrintAdjList(ALGraph g) /*輸出鄰接表*/
{
    ENode *sn;//定義一個邊結(jié)點指針，用于移動改變輸出的邊結(jié)點
    for(int i=0;i<g.vexnum;i++)
    {
        sn=g.vertices[i].firstarc;//初始化為每個頂點的第一條邊的地址
        printf("%d",i);
        while(sn!=NULL)//循環(huán)輸出我們的每個頂點的邊結(jié)點信息
        {
            printf("->%d",sn->adjvex);

//每輸出完一個邊結(jié)點就移動至下一個邊結(jié)點，直到最后一個邊結(jié)點為止，也就是指針為空的時候
            sn=sn->nextarc;
        }
        printf("\n");//完成一個頂點的全部邊結(jié)點輸出后，換行
    }
}

整體就是采用循環(huán)的方式，頭插法創(chuàng)建我們的無向圖的鄰接表，關(guān)鍵在于其中我們指針的移動。文章來源地址http://www.zghlxwxcb.cn/news/detail-754975.html

到了這里，關(guān)于C/C++語言 數(shù)據(jù)結(jié)構(gòu) 創(chuàng)建鄰接表存儲的無向圖及其鄰接表的輸出的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！