描述
图(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 2 3
代码：
#include<stdio.h>
#include<malloc.h> typedef struct graph //图的结构体
{
int Vertices; //顶点数
int **A; //图的二维矩阵
}Graph; void CreateGraph(Graph *g,int n) //创建一个、包含了n个顶点的图
{
int i,j;
g->Vertices = n;
g->A = (int**)malloc(n*sizeof(int*));
for(i = ;i < n;i++)
{
g->A[i] = (int*)malloc(n*sizeof(int));
for(j = ;j < n;j++)
g->A[i][j] = ;
}
} int Add(Graph *g,int u,int v) //在图g中添加一条边(u,v)
{
int n = g->Vertices;
if(u<||v<||u>n-||v>n-||g->A[u][v]!=) //不知道为什么这里不要判断u==v的情况
{
return ;
}
g->A[u][v]=;
return ;
} int Exist(Graph g,int u,int v) //判断图中是否存在边(u,v)
{
int n;
n = g.Vertices;
if(u<||v<||u>n-||v>n-||g.A[u][v]==)
return ;
return ;
} void DFS(Graph g,int v,int *visited) //深度遍历图
{
int w;
visited[v]=;
printf("%d ",v);
for(w=;w<g.Vertices;w++)
{
if(Exist(g,v,w)&&visited[w]!=)
DFS(g,w,visited);
}
} int main()
{
int enumber,vnumber,one,two,i,j;
Graph g;
int visited[]; scanf("%d %d",&vnumber,&enumber); //vnumber为图中顶点的个数，enumber为图中边的条数
if(<=vnumber<=&&<=enumber<=)
{
CreateGraph(&g,vnumber); //创建一个图
}
else
return ; for(i=;i<enumber;i++) //向图中添加边
{
scanf("%d %d",&one,&two);
Add(&g,one,two);
Add(&g,two,one);
} for(i=;i<vnumber;i++) //将图的邻接矩阵输出
{
for(j=;j<vnumber;j++)
{
if(Exist(g,i,j))
printf("%d ",);
else
printf("%d ",);
}
printf("\n");
} for(i=;i<g.Vertices;i++) //visited[]为每个顶点的标志位，用来判断顶点是否被访问过，0表示没有被访问。
{
visited[i]=;
}
for(i=;i<g.Vertices;i++)
{
if(visited[i]!=) //深度遍历图
DFS(g,i,visited);
}
printf("\n");
return ;
}