本程序用邻接矩阵表示法存储图。基本操作有

//产生图的邻接矩阵
//输出图的邻接矩阵
//广度优先输出邻接矩阵
//向图中插入一条弧
 

#include <stdio.h>
#define status int
#define OK 1
#define ERROR 0
#define maxsize 100
#define elemtype char
typedef struct vertex
{
 int num;
 char date;
 
} Gnode;
typedef struct graph
{
 int n;
 int e;
 Gnode ver[maxsize];
 int edges[maxsize][maxsize];
}adjmatrix;

typedef struct queue
{
 elemtype qu[maxsize];
 int head,rear;//head指向头元素，rear指向尾元素的下一个位置
}Queue;

void initqueue(Queue &Q)
{// 初始化队列
 Q.head=0;
 Q.rear=0;
}
status qempty(Queue Q)
{//判空
 if(Q.head ==Q.rear)
  return OK;
 else
  return ERROR;
}
status qfull(Queue Q)
{
 if((Q.rear+1)%maxsize==Q.head)
  return OK;
 else
  return ERROR;
}
status insertq(Queue &Q,elemtype e)
{//向对中插入元素
 if(qfull(Q))
 {
  printf("队已满\n");
  return ERROR;
 }
 else
 {
  Q.qu[Q.rear]=e;
  Q.rear=(Q.rear+1)%maxsize;
  return OK;
 }
}
elemtype dequeue(Queue &Q,elemtype &e)
{//队首出队列，并用e返回队首值
 if(qempty(Q))
  return ERROR;
 else
 {
  e=Q.qu[Q.head];
  Q.head=(Q.head+1)%maxsize;
  return OK;
 }
}

status creatgraph(adjmatrix &adj)
{//生成一个无向图的邻接矩阵
 int i,j,k,n,e;
 elemtype begin,end;
 printf("请输入顶点数n=");scanf("%d",&n);
 printf("请输入边数e=");scanf("%d",&e);
 adj.n=n;adj.e=e;
 for(i=1;i<=n;i++)//输入顶点值,从1号下表开始存储
 {
  printf("请输入第%d个顶点的值：",i);
  scanf("%s",&adj.ver[i].date);
  adj.ver[i].num=i;//顶点序号
 }
 for(i=1;i<=n;i++)//初始化边值为0
  for(j=1;j<=n;j++)
   adj.edges[i][j]=0;
 for(k=1;k<=e;k++)//向邻接矩阵内填写边的信息
 {
  printf("请输入第%d条边连接的两个顶点的值\n",k);
  printf("   第一个顶点(或起点)的值：");scanf("%s",&begin);
  printf("   第二个顶点(或终点)的值：");scanf("%s",&end);
  //寻找起点和终点的序号
  for(i=1;i<=n&&adj.ver[i].date!=begin;i++);
  if(i>n)
  {
   printf("起点不存在\n");
   return ERROR;
  }
  for(j=1;j<=n&&adj.ver[j].date!=end;j++);
  if(j>n)
  {
   printf("终点不存在\n");
   return ERROR;
  }
  adj.edges[i][j]=1;
  adj.edges[j][i]=1;
 }
 return OK;
}

status output(adjmatrix adj)
{//输出有向图邻接矩阵
 int i,j;
 printf("图的邻接矩阵如下:\n");
 printf("   ");
 for(i=1;i<=adj.n;i++)
  printf("%3d",i);printf("\n");
 for(i=1;i<=adj.n;i++)
 {
  printf("%3d",i);
  for(j=1;j<=adj.n;j++)
   printf("%3d",adj.edges[i][j]);
  printf("\n");
 }
 return OK;
}

status DFSvisit(adjmatrix adj,int k) //广度优先遍历图
{//adj为要遍历的临界表，k为第一个遍历元素的序号
 elemtype elem;
 int i,j,visited[maxsize];
 Queue Q;
 for(j=1;j<=adj.n;j++)//初始化visited
 {
  visited[j]=0;
 }
 initqueue(Q);
 if(visited[k]==0)
  insertq(Q,adj.ver[k].date);
 while(!(qempty(Q)))
 {
  dequeue(Q,elem);
  printf("%c",elem);
  for(i=1;i<=adj.n&&adj.ver[i].date!=elem;i++);//寻找elem的序号
  k=i;
  visited[k]=1;
  for(j=1;j<=adj.n;j++)
   if(adj.edges[k][j]==1&&visited[j]==0)
    insertq(Q,adj.ver[j].date);
 }
 return OK;
}

status insertedge(adjmatrix &adj)//向图中插入插入一条弧
{
 int i,j;
 elemtype begin,end;
 adj.e++;
 printf("请输入新插入的边(即第%d条边)连接的两个顶点的值\n",adj.e);
 printf("   第一个顶点(或起点)的值：");scanf("%s",&begin);
 printf("   第二个顶点(或终点)的值：");scanf("%s",&end);
 for(i=1;i<=adj.n&&adj.ver[i].date!=begin;i++);
 if(i>adj.n)
 {
  printf("起点不存在\n");
  return ERROR;
 }
 for(j=1;j<=adj.n&&adj.ver[j].date!=end;j++);
 if(j>adj.n)
 {
  printf("终点不存在\n");
  return ERROR;
 }
 adj.edges[i][j]=1;
 adj.edges[j][i]=1;
 return OK;
}

void main()
{
 adjmatrix adj;
//产生图的邻接矩阵
 creatgraph(adj);
//输出图的邻接矩阵
 output(adj);
//广度优先输出邻接矩阵
 DFSvisit(adj,1);printf("\n");
//向图中插入一条弧
 insertedge(adj);
 output(adj);
}