程序举例：
#include "stdio.h"
#define MAX_VERTEX_NUM 20 /*图中最多顶点数*/
typedef enum {DG,DN,UDG,UDN} GraphKind;
/* DG：有向图,DN：有向网,UDG：无向图,UDN：无向网*/
typedef char VertexType; /*假定顶点数据类型为字符*/
typedef struct { /*定义存储图的数据类型*/
VertexType vexs[MAX_VERTEX_NUM+1]; /*顶点数组*/
int arcs[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1]; /*邻接矩阵*/
int vexnum; /*顶点数*/
GraphKind kind; /*图类型：DG,DN,UDG,UDN */
} MGraph;
/*******************************************************************
** 功能：生成有向图和无向图 **
** 　 输入：图类型的数据指针，有向图或无向图标识 **
** 输出：生成的图类型的数据 　 **
*******************************************************************/
void Create1(MGraph *G,GraphKind kind)
{
int i,j;
printf("\ninput vertex numbers?");
scanf("%d",&G->vexnum); /*确定顶点数*/
for(i=1;i<=G->vexnum;i++) /*输入顶点数组元素*/
{printf("\nvertex No.%d:",i);
scanf("%1s",&G->vexs[i]);
}
for(i=1;i<=MAX_VERTEX_NUM;i++) /*邻接矩阵初始化*/
for(j=1;j<=MAX_VERTEX_NUM;j++)
G->arcs[i][j]=0;
printf("\ninput edges,");
scanf("%d%d",&i,&j); /*输入边或弧对应的两顶点序号，以0结束*/
while (i!=0 &&j!=0)
{
G->arcs[i][j]=1; /*存储顶点i到顶点j的关系*/
if (kind==UDG) G->arcs[j][i]=1;/*无向图时，存储顶点j到顶点i的关系*/
printf("\ninput edges,");
scanf("%d%d",&i,&j);
}
}
/*******************************************************************
** 功能：控制生成有向图、有向网、无向图和无向网 **
** 　 输入：图类型的数据指针 **
** 输出：生成的图类型的数据 　 **
*******************************************************************/
void CreateGraph(MGraph *G)
{
printf("input graph kind,0,有向图 1,有向网,\n");
printf(" 2,无向图 3,无向网\n");
scanf("%d",&G->kind);
switch (G->kind)
{
case DG,Create1(G,DG);break; /*生成有向图*/
/* case DN,CreateDN(G);*/ /*生成有向网*/
case UDG,Create1(G,UDG);break; /*生成无向图*/
/* case UDN,CreateUDN(G);*/ /*生成无向网*/
}
}
/*******************************************************************
** 功能：求有向图和无向图的顶点的度数 **
** 　 输入：图类型的数据指针，顶点序号 **
** 输出：顶点的度数 　 **
*******************************************************************/
int TD(MGraph *G,int n)
{
int i,s=0;
if (n>G->vexnum || n<=0) /*判断序号的合法性*/
{printf("error vertex number!"); return -1;}
for(i=1;i<=G->vexnum;i++)
{ s+=G->arcs[n][i]; /*统计第n行的1的数目，有向图时为出度*/
if (G->kind==DG) /*有向图时，还需统计第n列的1的数目（入度）*/
s+=G->arcs[i][n];
}
return s;
}
/********************下列程序完成对图的遍历*********************/
int visited[MAX_VERTEX_NUM+1]; /*顶点访问标记数组，1：已访问，0：未访问 */
/*******************************************************************
** 功能：求与有向图和无向图的某顶点相邻的第一个顶点 **
** 　 输入：图类型的数据指针，顶点序号 **
** 输出：相邻的第一个顶点序号 　 **
*******************************************************************/
int FirstAdjVex(MGraph *G,int v)
{
int i;
for(i=1;i<=G->vexnum;i++)
if (G->arcs[v][i]) return i;
return 0;
}
/*******************************************************************
** 功能：求与有向图和无向图的某顶点相邻的顶点序列 **
** 某顶点的后继顶点 **
** 　 输入：图类型的数据指针，顶点序号，相邻的顶点序号 **
** 输出：相邻顶点后继顶点序号 　 **
*******************************************************************/
int NextAdjVex(MGraph *G,int v,int w)
{
int i;
for(i=w+1;i<=G->vexnum;i++)
if (G->arcs[v][i]) return i;
return 0;
}
/*******************************************************************
** 功能：从图的某顶点开始深度优先遍历算法 **
** 　 输入：图类型的数据指针，起始顶点序号 **
** 输出：遍历序列 　 **
*******************************************************************/
void DFS(MGraph *G,int v)
{
int w;
visited[v]=1;
printf("%c",G->vexs[v]); /* 访问起始顶点*/
for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
if (!visited[w]) DFS(G,w);
}
/*******************************************************************
** 功能：对整个图深度优先遍历算法 **
** 　 输入：图类型的数据指针，起始顶点序号 **
** 输出：遍历序列 　 **
*******************************************************************/
void DFSTraverse(MGraph *G)
{
int i;
for(i=1;i<=G->vexnum;i++) /*顶点访问标记数组初始化*/
visited[i]=0;
for(i=1;i<=G->vexnum;i++) /*调用遍历算法*/
if (!visited[i]) DFS(G,i);
}
/*******************************************************************
** 功能：对整个图宽度优先遍历算法 **
** 　 输入：图类型的数据指针，起始顶点序号 **
** 输出：遍历序列 　 **
*******************************************************************/
void BFSTraverse(MGraph *G)
{
int i,u,w;
/*用数组Q表示一队列，front:头指示,rear：尾指示*/
int Q[MAX_VERTEX_NUM+1],front=0,rear=0;
for(i=1;i<=G->vexnum;i++) /*顶点访问标记数组初始化*/
visited[i]=0;
for(i=1;i<=G->vexnum;i++)
if (!visited[i])
{visited[i]=1; /*从顶点i开始进行宽度优先遍历*/
printf("%c",G->vexs[i]); /* 访问顶点i*/
Q[++rear]=i; /* 顶点i进队*/
while(front!=rear) /*队列非空*/
{u=Q[++front]; /*出队列，顶点序号赋u*/
/*依次访问顶点u的所有未访问过的相邻顶点*/
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if (!visited[w])
{visited[w]=1;
printf("%c",G->vexs[w]);
Q[++rear]=w; /*相邻顶点序号进队*/
}
}
}
}
/*主函数，负责定义图类型数据对象*/
main()
{
MGraph G1,G2; /*定义图类型数据对象G1，G2*/
int i;
clrscr();
CreateGraph(&G1);
for(i=1;i<=G1.vexnum;i++)
printf("\nTD(%c)=%d",G1.vexs[i],TD(&G1,i));
BFSTraverse(&G1);
}