图的建立——邻接表表示（C语言+VC6.0平台）

图是一种重要而且相对复杂的数据结构，在实际编程中非常有用。邻接表是图的主要表示形式之一，是一种链接表表示方法。

#include<stdio.h>

#include<stdlib.h>

#define MAX 10//令图的最大顶点个数为10

typedef struct node//边表结点（弧）

{

         int adjvex;//相连顶点的编号

         int weight;//边权

         struct node *pnext;//指向下一个边表结点

}edgenode;

typedef struct vertexnode//顶点表结点

{

         int adjvex;//顶点号

         edgenode *pfirst;//边表头指针

}vertexnode;

typedef vertexnode adj_list[MAX]; //表头数组

typedef struct adjlist_graph//图的邻接表结构

{

         int cnt_edges; //边数

         int cnt_nodes; //顶点数

         adj_list adjlist;//图的邻接表头

}adjlist_graph;

void create_graph(adjlist_graph* graph)//以邻接表方式创建图

{

         edgenode* pnewnode;//新的边表结点

         int i,j,k;

         printf("输入图的顶点数和边数：\n");

         scanf("%d%d",&graph->cnt_nodes,&graph->cnt_edges);

         printf("图的顶点有%d个，边数有%d个\n",

                   graph->cnt_nodes,graph->cnt_edges);

         for(i=0;i<graph->cnt_nodes;i++)//初始化图的邻接表顶点

         {

                   graph->adjlist[i].adjvex=i;

                   graph->adjlist[i].pfirst=NULL;

         }

         for(k=0;k<graph->cnt_edges;k++)//循环输入图各条边

         {                              //无向图情形

                   printf("输入一条新的边:\n");

                   scanf("%d%d",&i,&j);

                   pnewnode=(edgenode*)malloc(sizeof(edgenode));

                   pnewnode->adjvex=j;

                   pnewnode->weight=0;

                   pnewnode->pnext=graph->adjlist[i].pfirst;

                   graph->adjlist[i].pfirst=pnewnode;

                   //无向图情形,具有对称性

                   pnewnode=(edgenode*)malloc(sizeof(edgenode));

                   pnewnode->adjvex=i;

                   pnewnode->weight=0;

                   pnewnode->pnext=graph->adjlist[j].pfirst;

                   graph->adjlist[j].pfirst=pnewnode;

         }

}

void show_adjlist_graph(adjlist_graph* graph)//显示图中的顶点及其相关联的所有边

{

         int i;

         edgenode* pnode;

         for(i=0;i<graph->cnt_nodes;i++)

         {

                   pnode=graph->adjlist[i].pfirst;

                   printf("\n顶点编号%d:",graph->adjlist[i].adjvex);

                   while(pnode!=NULL)

                   {

                            printf(" 边:%d<->%d ",graph->adjlist[i].adjvex,pnode->adjvex);

                            pnode=pnode->pnext;

                   }

                   printf("\n");

         }

}

int main(void)

{

         adjlist_graph *pgraph;

         pgraph=(adjlist_graph*)malloc(sizeof(adjlist_graph));

         create_graph(pgraph);

         show_adjlist_graph(pgraph);

}