程序举例: #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] /*顶点数组*/ arcs[ MAX VERTEX NUM+1 MAX VERTEX NUM1];/*邻接矩阵*/ int vexnu, /*顶点数*/ GraphKind kind /*图类型:DG,DN,UDG,UDN*/ 1 MGraph ★功能:生成有向图和无向图 来输入:图类型的数据指针,有向图或无向图标识 输出:生成的图类型的数据 ***家本*家*亲*家*家容****本**家***家*/ void Createl(MGraph *G, graphkind kind) printf( \input vertex numbers?") scanf(%d",&G->vexnum /*确定顶点数*/ for (i=l; ivexnum; i++) /*输入顶点数组元素*/ Printf( "\vertex No %d: i) scanf(%1s",&G->vexsliD) for(i=l; iarcs[i][j]=0 printf( \input edges:") scanf(%d%d", &i, &j) /*输入边或弧对应的两顶点序号,以0结束* ile(i!=0 &&j! G->arcs[i][j]=l /*存储顶点i到顶点j的关系*/ if(kind=UDG)G->arcs[j][i]=1;/*无向图时,存储顶点j到顶点i的关系*/ rinf(\input edge scanf(%d%d", &i, &j)
程序举例： #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;ivexnum;i++) /*输入顶点数组元素*/ {printf("\nvertex No.%d:",i); scanf("%1s",&G->vexs[i]); } for(i=1;iarcs[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") intf( 2.无向图3.无向网\n") ("%d",&G->kind) switch (G->kind) case DG: Createl(G, DG):break /*生成有向图*/ /*k case DN: CreateDN(G): * /*生成有向网* case UDG: Createl(G, UDG); break /*生成无向图*/ /*k case UDN: CreateUDN(G); * /*生成无向网*/ *功能:求有向图和无向图的顶点的度数 输入:图类型的数据指针,顶点序号 *输出:顶点的度数 **家*亲本*家*家*亲本*******家本*亲**亲本*本**家*幸本****本*率***本*/ int TD (MGraph * G, int n) int i s=0 if(n>G-> vexnum|nvexnum; i++) s+=G->arcs[n][i];/统计第n行的1的数目,有向图时为出度*/ if(G-kind==DG)/*有向图时,还需统计第n列的1的数目(入度)* S+=G->arcs[i][n] return s
/******************************************************************* ** 功能：控制生成有向图、有向网、无向图和无向网 ** ** 输入：图类型的数据指针 ** ** 输出：生成的图类型的数据 ** *******************************************************************/ 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 || nvexnum;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 1. for (i=l; ivexnum; i++) if (G->arcs [v][il)return i return 0 /*本*****幸本幸本*率本***幸*幸布春*幸本**率本幸率布容春***** 功能:求与有向图和无向图的某顶点相邻的顶点序列 某顶点的后继顶点 输入:图类型的数据指针,顶点序号,相邻的顶点序号 *输出:相邻顶点后继顶点序号 int NextAdjVex(MGraph *G, int v, int w) int 1 for(i=w+l; ivexnum; i++) if (G->arcs [ v][i]) return i return 0 水水亦水常水水*称水水*客水本水*水水**水*客水客水水客水客水客水凇水水水水客水*本市*客客水*水水水水 ★功能:从图的某顶点开始深度优先遍历算法 六输入:图类型的数据指针,起始顶点序号 输出:遍历序列 *客*涂布客客水**客**客水*水客宗*客水*客水客本客*称**水*水布客水客水*客本客 void DFS (MGraph *G, int v) visited[v]=l printf("%c", G->vexs[v]) /*访问起始顶点* for(w=FirstAd jVex(G, v): w; w=NextAd jVex(G, v, w)
/********************下列程序完成对图的遍历*********************/ int visited[MAX_VERTEX_NUM+1]; /*顶点访问标记数组，1：已访问，0：未访问 */ /******************************************************************* ** 功能：求与有向图和无向图的某顶点相邻的第一个顶点 ** ** 输入：图类型的数据指针，顶点序号 ** ** 输出：相邻的第一个顶点序号 ** *******************************************************************/ int FirstAdjVex(MGraph *G,int v) { int i; for(i=1;ivexnum;i++) if (G->arcs[v][i]) return i; return 0; } /******************************************************************* ** 功能：求与有向图和无向图的某顶点相邻的顶点序列 ** ** 某顶点的后继顶点 ** ** 输入：图类型的数据指针，顶点序号，相邻的顶点序号 ** ** 输出：相邻顶点后继顶点序号 ** *******************************************************************/ int NextAdjVex(MGraph *G,int v,int w) { int i; for(i=w+1;ivexnum;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 1. for(i=l;i vexnum;i++)/*顶点访问标记数组初始化*/ visited[i]=0 for(i=l;i vexnum;i++)/*调用遍历算法*/ if (!visited[il DFS(G, i) 功能:对整个图宽度优先遍历算法 输入:图类型的数据指针,起始顶点序号 输出:遍历序列 void BFSTraverse (MGraph *G) int lu.w /*用数组Q表示一队列, front:头指示,rear:尾指示* It Q [ MAX VERTEX NUM+1], front=0, rear=0 for(i=l;i vexnum;i++)/*顶点访问标记数组初始化*/ visited [i]=0 for(i=l; ivexnum; i++) if (!visited liD Ivisitedli]=l /*从顶点i开始进行宽度优先遍历*/ printf(%c", G->vexs[i]) /*访问顶点i Q[++rear]=i /*顶点i进队 while( front!=rear)/*队列非空*/ {u=Q[++ front];/*出队列,顶点序号赋u /*依次访问顶点u的所有未访问过的相邻顶点* for(w=FirstAdjVex(, u); w; w=NextAd jVex(G, u, w)) f(!visited lw]) visited[w=l printf("%c", G->vexs [w]) Q[++rear]= /*相邻顶点序号进队*/
if (!visited[w]) DFS(G,w); } /******************************************************************* ** 功能：对整个图深度优先遍历算法 ** ** 输入：图类型的数据指针，起始顶点序号 ** ** 输出：遍历序列 ** *******************************************************************/ void DFSTraverse(MGraph *G) { int i; for(i=1;ivexnum;i++) /*顶点访问标记数组初始化*/ visited[i]=0; for(i=1;ivexnum;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;ivexnum;i++) /*顶点访问标记数组初始化*/ visited[i]=0; for(i=1;ivexnum;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*/ nt 1 clrscro CreateGraph(&G1) for(i=l; i<=GI. vexnum: i++) printf("\nTD(%c)=%d", Gl. vexs [i], TD(&Gl, i)) BFSTraverse(&G1)
} } } /*主函数，负责定义图类型数据对象*/ 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); }