1.图的邻接矩阵
/* c7-1.h 图的数组(邻接矩阵)存储表示 */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 26 /* 最大顶点个数 */
typedef enum{DG,DN,UDG,UDN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /* 二维数组 */
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
2.深度优先遍历
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(VertexType); /* 函数变量 */
void DFS(MGraph G,int v)
{ /* 从第v个顶点出发递归地深度优先遍历图G。算法7.5 */
int w;
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vexs[v]); /* 访问第v个顶点 */
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
if(!visited[w])
DFS(G,w); /* 对v的尚未访问的序号为w的邻接顶点递归调用DFS */
}
void DFSTraverse(MGraph G,void(*Visit)(VertexType))
{ /* 初始条件：图G存在，Visit是顶点的应用函数。算法7.4 */
/* 操作结果：从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次 */
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc，使DFS不必设函数指针参数 */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化(未被访问) */
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点v调用DFS */
printf("\n");
}
3.广度优先遍历
void BFSTraverse(MGraph G,void(*Visit)(VertexType))
{ /* 初始条件：图G存在，Visit是顶点的应用函数。算法7.6 */
/* 操作结果：从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数Visit一次且仅一次 */
int v,u,w;
LinkQueue Q; /* 使用辅助队列Q和访问标志数组visited */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++)
if(!visited[v]) /* v尚未访问 */
{
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
Visit(G.vexs[v]);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
for(w=FirstAdjVex(G,G.vexs[u]);w>=0;w=NextAdjVex(G,G.vexs[u],G.vexs[w]))
if(!visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
{
visited[w]=TRUE;
Visit(G.vexs[w]);
EnQueue(&Q,w);
}
}
}
printf("\n");
}
温馨提示：答案为网友推荐，仅供参考