無向圖的鄰接表具體代碼
#include <iostream>
using namespace std;
const int MAXVEX=100;
typedef struct EdgeNode /*鄰接表邊結點*/
{
int adjvex;
EdgeNode *next;
}EdgeNode;
typedef struct VertexNode /*鄰接表頂點結點*/
{
int data;
EdgeNode* firstedge;
}VertexNode,AdjList[MAXVEX];
typedef struct /*鄰接表邏輯結構*/
{
AdjList adjList;
int numVertexes,numEdges;
}GraphAdjList;
void CreateGraph(GraphAdjList *G) /*創(chuàng)建鄰接表舀患,在這里我覺得指針就像是規(guī)劃了一塊地,我只需要在這塊地里建造就可以了*/
{
int i,j;
cout<<"請輸入圖的頂點個數與邊的個數:"<<endl;
cin>>G->numVertexes>>G->numEdges;
for(i=0;i<G->numVertexes;i++) /*在鄰接表中頂點表中存放頂點信息*/
{
cin>>G->adjList[i].data;
G->adjList[i].firstedge=NULL;
}
for(int k=0;k<G->numEdges;k++) /*使用頭插法構造鄰接表*/
{
cout<<"請輸入邊的兩個頂點:"<<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; //因為是無向圖气破,所以出現了一條邊表示了兩次聊浅。我們將頂點信息存放到數組中,以數組坐標來代替頂點信息
}
}
void Print(GraphAdjList *G) /*輸出鄰接表信息*/
{
for(int i=0;i<G->numVertexes;i++)
{
EdgeNode *p=G->adjList[i].firstedge;
while(p!=NULL) //當p為空時现使,說明以i為頂點的邊已經查找完畢了低匙。
{
cout<<"該邊信息為:"<<G->adjList[i].data<<'\t'<<p->adjvex<<endl;
p=p->next;
}
}
}
int main()
{
GraphAdjList* p=new GraphAdjList;
CreateGraph(p);
Print(p);
return 0;
}
鄰接表實例.png
鄰接表.png
鄰接表中的頂點表的建立一般沒什么問題,而邊表中是需要輸入邊的兩個頂點的碳锈,其中一個點是用來說明現在的邊統(tǒng)屬于哪個頂點顽冶,另外一個是說明邊的另一端的頂點。還有就是無向售碳,因而i,j該邊被頭插了兩次强重。