基本内容：
输入图的类型、顶点数、弧（边）数、顶点信息、弧（边）信息，建立相应的图(具体类型可以是无向图、有向图、无向网、有向网，采用邻接矩阵存储结构)；分别按深度优先搜索和广度优先搜索遍历图；按某种形式输出图及遍历结果。
代码：
#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 100//循环队列最大值
#define OVERFLOW -2
#define FALSE 0
#define OK 1
#define MAX_VEX_NUM 20//图中最多20个顶点
#define INFINITY 0
typedef int Status;
typedef char ElemType;
typedef struct//图结构
{
ElemType vertex[MAX_VEX_NUM];//存顶点 Status arcs[MAX_VEX_NUM][MAX_VEX_NUM];//存边 Status vex_num,arc_num;// vex_num顶点数，arc_num边数
}Mgraph;
typedef struct//循环队列结构
{
ElemType *base;int front;int rear;
}SqQueue;
//分配数组，将数组中的元素赋值为0
bool visited[MAX_VEX_NUM];//深度优先搜索的辅助数组
bool Qvisited[MAX_VEX_NUM];//广度优先搜索的辅助数组
//定位边的节点
Status LocateVex(Mgraph g,ElemType v)
// 从键盘中输入结点值，定位的作用是找到结点在 vertex数组中的下标
{
Status i;for(i=0;i<g.vex_num;++i)//把所有的顶点循环一次 {
if(g.vertex[i]==v){
return i;//返回下标位置 }}
}
//创建图
void create_UDG(Mgraph &g)
{
Status i,j,k;ElemType v1,v2;//顶点 Status cost;//权值 printf("请输入顶点数,边数：\n");scanf("%d,%d",&g.vex_num,&g.arc_num);getchar();//作用是将回车键吃掉 printf("请输入顶点信息：\n"); //读入顶点 for(i=0;i<g.vex_num;++i){
scanf("%c",&g.vertex[i]);getchar();}
//初始化邻接矩阵（将二维邻接矩阵全部置为正无穷） for(i=0;i<g.vex_num;++i){
for(j=0;j<g.vex_num;++j){
g.arcs[i][j]=INFINITY;}}//构造邻接矩阵printf("请输入边信息：\n");for(k=0;k<g.arc_num;++k){
//输入依附于两个顶点的边scanf("%c,%c,%d",&v1,&v2,&cost);getchar();i=LocateVex(g,v1);//找到v1顶点所在 vertex数组的位置 j=LocateVex(g,v2);//找到v2顶点所在vertex数组的位置 g.arcs[i][j]=cost;//在二维数组中将权值替换g.arcs[j][i]=g.arcs[i][j]; //无向网，对称矩阵} }//输出图，检查图是否创建成功 void out_UDG(Mgraph g){
Status i,j;printf("图的顶点是：\n");for(i=0;i<g.vex_num;i++)//遍历 vertex数组 {
printf("%8c",g.vertex[i]);}printf("\n");printf("图的邻接矩阵是：\n");for(i=0;i<g.vex_num;i++)//遍历 arcs数组 {
for(j=0;j<g.vex_num;j++){
printf("%8d",g.arcs[i][j]);}printf("\n");}}//深度搜索 （递归）
void DFS(Mgraph g, Status v)
{
printf("%8c",g.vertex[v]);//从数组下标为0的结点搜索 visited[v] = 1;//搜索过的标记为1 for(int w = 0; w < g.vex_num; w ++ )if( (g.arcs[v][w] != 0 ) && (!visited[w]))//权值不为0代表有边，visited为0代表没有扫过 DFS(g, w);
}
//创建空队列
Status InitQueue (SqQueue &Q)
{
Q.base=(ElemType*)malloc(MAXQSIZE * sizeof(ElemType));if(!Q.base){
exit(OVERFLOW);}Q.front=Q.rear=0;return OK;
}
//入队
Status EnQueue(SqQueue &Q,ElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front){
return FALSE;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;
}
//出队
Status DeQueue(SqQueue &Q)
{
if(Q.front==Q.rear){
return FALSE;}Q.front=(Q.front+1)%MAXQSIZE;return Q.front-1;
}
//广度搜索
void BFS(Mgraph g,Status v)
{
printf("广度优先搜索结果为：\n"); Status w;printf("%8c",g.vertex[v]);//先将第一个顶点输出 Qvisited[v]=1;//将第一个顶点标记为1 SqQueue Q;InitQueue(Q);//创建队列 EnQueue(Q,g.vertex[v]);//将第一个顶点入队 while(!(Q.rear+1==Q.front))//循环条件是队列不为空 {
v=DeQueue(Q);//出队，并将顶点的下标返回给v for(w=0;w<g.vex_num;w++)//搜索二维数组中的每一行 {
if(g.arcs[v][w]!=0&&Qvisited[w]==0){
Qvisited[w]=1;//将节点的每一个相邻结点标记为1 printf("%8c",g.vertex[w]);//将节点的每一个相邻结点输出 EnQueue(Q,g.vertex[w]);//将子节点入队列 }}}
}
int main()
{
Mgraph g;create_UDG(g);//建图 out_UDG(g);//检验图 printf("深度优先搜索结果：\n"); DFS(g,0);//深搜 printf("\n");BFS(g,0);//广搜 return 0;
}
运行结果：
