图的邻接表存储 c实2011-10-07 10:34 4047人阅读 评论(2) 收藏 举报
用到的数据结构是
一个是顶点表，包括顶点和指向下一个邻接点的指针
一个是边表， 数据结构跟顶点不同，存储的是顶点的序号，和指向下一个的指针
刚开始的时候把顶点表初始化，指针指向null。然后边表插入进来，是插入到前一个，也就是直接插入到firstedge指向的下一个，而后面的后移
- #define MaxVertexNum 100
- typedef char VertexType;
- typedef struct node //边表节点
- {
- int adjvex;
- node* next;
- }EdgeNode;
- typedef struct //顶点表节点
- {
- VertexType vertex;
- EdgeNode* firstedge;
- }VertexNode;
- typedef VertexNode AdjList[MaxVertexNum];
- typedef struct
- {
- AdjList adjlist;
- int n,e;
- }ALGraph;
以下建立的是无向图的邻接表，有向图的更简单了
- #include <stdio.h>
- #include <stdlib.h>
- #define MaxVertexNum 100
- typedef char VertexType;
- typedef struct node //边表节点
- {
- int adjvex;
- node* next;
- }EdgeNode;
- typedef struct //顶点表节点
- {
- VertexType vertex;
- EdgeNode* firstedge;
- }VertexNode;
- typedef VertexNode AdjList[MaxVertexNum];
- typedef struct
- {
- AdjList adjlist;
- int n,e;
- }ALGraph;
- void create(ALGraph*);
- void main()
- {
- ALGraph* G= (ALGraph*)malloc(sizeof(ALGraph));
- create(G);
- for (int i=0;i< G->n;i++)
- {
- printf("%d->",i);
- while(G->adjlist[i].firstedge!=NULL)
- {
- printf("%d->",G->adjlist[i].firstedge->adjvex);
- G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;
- }
- printf("\n");
- }
- }
- void create(ALGraph* G)
- {
- int i,j,k,w,v;
- EdgeNode *s;
- printf("读入顶点数和边数");
- scanf("%d,%d",&G->n,&G->e);
- for (i=0;i<G->n;i++)
- {
- fflush(stdin);
- printf("建立顶点表");
- G->adjlist[i].vertex=getchar();
- G->adjlist[i].firstedge=NULL;
- }
- printf("建立边表\n");
- for (k=0;k<G->e;k++)
- {
- printf("读入(vi-vj)的顶点对序号");
- scanf("%d,%d",&i,&j);
- s=(EdgeNode*)malloc(sizeof(EdgeNode));
- s->adjvex=j;
- s->next=G->adjlist[i].firstedge; //插入表头
- G->adjlist[i].firstedge=s;
- s=(EdgeNode*)malloc(sizeof(EdgeNode));
- s->adjvex=i;
- s->next=G->adjlist[j].firstedge;
- G->adjlist[j].firstedge=s;
- }
- }
结果
自己也编程试试吧！
接下来图的遍历，深度优先遍历和广度优先遍历
