783
圖的鄰接表存儲 c實現
圖的鄰接表存儲 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;
- }
- }
結果
自己也編程試試吧！
接下來圖的遍曆，深度優先遍曆和廣度優先遍曆
最後更新：2017-04-03 12:54:00