无向图的邻接表具体代码
#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) /*创建邻接表,在这里我觉得指针就像是规划了一块地,我只需要在这块地里建造就可以了*/
{
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;
}
邻接表中的顶点表的建立一般没什么问题,而边表中是需要输入边的两个顶点的,其中一个点是用来说明现在的边统属于哪个顶点,另外一个是说明边的另一端的顶点。还有就是无向,因而i,j该边被头插了两次。