描述
图(graph)是数据结构 G=(V,E)，其中V是G中结点的有限非空集合,结点的偶对称为边(edge)；E是G中边的有限集合。设V={0,1,2,……,n-1}，图中的结点又称为顶点(vertex)，有向图(directed graph)指图中代表边的偶对是有序的，用<u，v>代表一条有向边（又称为弧），则u称为该边的始点（尾），v称为边的终点（头）。无向图(undirected graph)指图中代表边的偶对是无序的，在无向图中边(u，v )和(v，u)是同一条边。
输入边构成无向图，求以顶点0为起点的宽度优先遍历序列。
输入
第一行为两个整数n、e，表示图顶点数和边数。以下e行,每行两个整数，表示一条边的起点、终点，保证不重复、不失败。1≤n≤20，0≤e≤190
输出
前面n行输出无向图的邻接矩阵，最后一行输出以顶点0为起点的宽度优先遍历序列，对于任一起点，按终点序号从小到大的次序遍历每一条边。每个序号后输出一个空格。
样例输入
4 5
0 1
0 3
1 2
1 3
2 3
样例输出
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
0 1 3 2
代码：
#include<stdio.h> #include<malloc.h> typedef struct graph //图的结构体 { int Vertices; int **A; }Graph; void CreateGraph(Graph *g,int n) //创建一个有n个顶点的图g { int i,j; g->Vertices = n; g->A = (int**)malloc(n*sizeof(int*)); for(i = 0;i < n;i++) { g->A[i] = (int*)malloc(n*sizeof(int)); for(j = 0;j < n;j++) g->A[i][j] = 0; } } int Add(Graph *g,int u,int v) //向图g中添加一条边(u,v) { int n = g->Vertices; if(u<0||v<0||u>n-1||v>n-1||g->A[u][v]!=0) { return 0; } g->A[u][v]=1; return 1; } int Exist(Graph g,int u,int v) //判断图g中是否存在边(u,v) { int n; n = g.Vertices; if(u<0||v<0||u>n-1||v>n-1||g.A[u][v]==0) return 0; return 1; } void BFS(Graph g,int v,int *visited) //宽度优先遍历图g，这里是用了数组进行遍历，没有使用队列 { int a[20],i=0,j=0,k; int w; visited[v]=1; printf("%d ",v); a[i++]=v; while(j!=i) { w=a[j++]; for(k=0;k<g.Vertices;k++) { if(Exist(g,w,k)&&visited[k]!=1) { visited[k]=1; printf("%d ",k); a[i++]=k; } } } } int main() { int enumber,vnumber,one,two,i,j; Graph g; int visited[20]; scanf("%d %d",&vnumber,&enumber); //vnumber为顶点数，enumber为边的条数 if(1<=vnumber<=20&&0<=enumber<=190) { CreateGraph(&g,vnumber); } else return 0; for(i=0;i<enumber;i++) //向图中添加边 { scanf("%d %d",&one,&two); Add(&g,one,two); Add(&g,two,one); } for(i=0;i<vnumber;i++) //把图的邻接矩阵输出 { for(j=0;j<vnumber;j++) { if(Exist(g,i,j)) printf("%d ",1); else printf("%d ",0); } printf("\n"); } for(i=0;i<g.Vertices;i++) //初始化每个顶点标志位矩阵 { visited[i]=0; } for(i=0;i<g.Vertices;i++) { if(visited[i]!=1) BFS(g,i,visited); //宽度优先遍历图 } printf("\n"); return 1; }