無向圖的鄰接表具體代碼

#include <iostream>

using namespace std;
const int MAXVEX=100;
typedef struct EdgeNode        /*鄰接表邊結(jié)點(diǎn)*/
{
    int adjvex;
    EdgeNode *next;
}EdgeNode; 
typedef struct VertexNode    /*鄰接表頂點(diǎn)結(jié)點(diǎn)*/
{
    int data;
    EdgeNode* firstedge;
}VertexNode,AdjList[MAXVEX];
typedef struct               /*鄰接表邏輯結(jié)構(gòu)*/
{
    AdjList adjList;
    int numVertexes,numEdges;
}GraphAdjList;
void CreateGraph(GraphAdjList *G)    /*創(chuàng)建鄰接表，在這里我覺得指針就像是規(guī)劃了一塊地，我只需要在這塊地里建造就可以了*/
{
    int i,j;
    cout<<"請輸入圖的頂點(diǎn)個(gè)數(shù)與邊的個(gè)數(shù)："<<endl;
    cin>>G->numVertexes>>G->numEdges;
    for(i=0;i<G->numVertexes;i++)    /*在鄰接表中頂點(diǎn)表中存放頂點(diǎn)信息*/
    {
        cin>>G->adjList[i].data;
        G->adjList[i].firstedge=NULL;
    }
    for(int k=0;k<G->numEdges;k++)    /*使用頭插法構(gòu)造鄰接表*/
    {
        cout<<"請輸入邊的兩個(gè)頂點(diǎn)："<<endl;
        cin>>i>>j;
        EdgeNode *e=new EdgeNode;           
        e->adjvex=j;
        e->next=G->adjList[i].firstedge;
        G->adjList[i].firstedge=e;
        EdgeNode *x=new EdgeNode;
        x->adjvex=i;
        x->next=G->adjList[j].firstedge;
        G->adjList[j].firstedge=x;          //因?yàn)槭菬o向圖，所以出現(xiàn)了一條邊表示了兩次。我們將頂點(diǎn)信息存放到數(shù)組中，以數(shù)組坐標(biāo)來代替頂點(diǎn)信息
    }
}
void Print(GraphAdjList *G)   /*輸出鄰接表信息*/
{
    for(int i=0;i<G->numVertexes;i++) 
    {
        EdgeNode *p=G->adjList[i].firstedge;
        while(p!=NULL)    //當(dāng)p為空時(shí)，說明以i為頂點(diǎn)的邊已經(jīng)查找完畢了。
        {
            cout<<"該邊信息為:"<<G->adjList[i].data<<'\t'<<p->adjvex<<endl;
            p=p->next;
        }
    }
}
int main()
{
    GraphAdjList* p=new GraphAdjList;
    CreateGraph(p);
    Print(p);
    return 0;
}

鄰接表實(shí)例.png

鄰接表.png

鄰接表中的頂點(diǎn)表的建立一般沒什么問題，而邊表中是需要輸入邊的兩個(gè)頂點(diǎn)的，其中一個(gè)點(diǎn)是用來說明現(xiàn)在的邊統(tǒng)屬于哪個(gè)頂點(diǎn)，另外一個(gè)是說明邊的另一端的頂點(diǎn)。還有就是無向，因而i,j該邊被頭插了兩次。