邻结矩阵比较简单，， 它的BFS,DFS, 两种遍历也比较简单，一个用队列， 一个用数组即可！！！
但是邻接矩阵极其浪费空间，尤其是当它是一个稀疏矩阵的时候！！！
---------------------------------------------------------------------------------------------------------------------------------------
//邻接矩阵的建立和 其BFS, DFS， 遍历
#include <cstdio>
#include <cstdlib>
//#define _OJ_
int visit[100];
int cnt = 0;
typedef struct Graph1
{
int nv;
int ne;
int a[100][100];
} Graph1, *Graph; //建立一个图含顶点， 边， 和邻接矩阵
Graph
creat_graph(void)
{
Graph g;
int i, j;
int v1, v2;
g = (Graph) malloc (sizeof(Graph1));
scanf("%d %d", &g->nv, &g->ne);
for(i = 0;i < g->nv; i++) {
for(j = 0;j < g->nv; j++) {
g->a[i][j] = 0;
}
} //对邻结矩阵赋初始值
for(i = 0;i < g->ne; i++) {
scanf("%d %d", &v1, &v2);
g->a[v1][v2] = 1;
g->a[v2][v1] = 1;
} //建立一个无向矩阵
return g;
}
void
DFS(Graph g, int i)
{
int j;
// lif(cnt == g->nv - 1)
// printf("%d\n", i);
// else { //此地有一个小技巧就是判断什么时候结束？
// printf("%d ", i); //用一个全局变量cnt 由于每一个点遍历一次
// cnt++; cnt == g->nv - 1 时结束；用此处理最后一个不要空格和换行
// }
printf("%d ", i);
visit[i] = 1;
for(j = 0;j < g->nv; j++) {
if(g->a[i][j] == 1 && visit[j] == 0)
DFS(g, j);
}
}
void
DFS_travers(Graph g)
{
int i;
for(i = 0;i < g->nv; i++)
visit[i] = 0;
for(i = 0;i < g->nv; i++) {
if(visit[i] == 0)
DFS(g, i);
}
}
typedef struct Queue1
{
int top;
int base;
int *elem;
} Queue1, *Queue;
Queue
creat_Queue(void)
{
Queue q;
q = (Queue) malloc (sizeof(Queue1));
q->elem = (int*) malloc (100 * sizeof(int));
q->base = q->top = 0;
return q;
}
int
isempty(Queue q)
{
if(q->base == q->top)
return 1;
else
return 0;
}
void
Enqueue(Queue q, int data)
{
q->elem[q->top++] = data;
}
int
Dequeue(Queue q)
{
return q->elem[q->base++];
}
void
BFS(Graph g, int v)
{
int i, j;
Queue q;
q = creat_Queue();
printf("%d ", v);
visit[v] = 1;
Enqueue(q, v);
while (isempty(q) != 1) {
i = Dequeue(q);
for(j = 0;j < g->nv; j++) {
if(g->a[i][j] && visit[j] == 0 ) {
printf("%d ", j); //把整排先全都遍历完，在遍历其它的
visit[j] = 1; //每次先遍历在入队
Enqueue(q, j);
}
}
}
}
void
BFS_travers(Graph g)
{
int i;
for(i = 0;i < g->nv; i++)
visit[i] = 0;
for(i = 0;i < g->nv; i++) {
if(visit[i] == 0)
BFS(g, i);
}
}
int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
Graph g;
g = creat_graph();
DFS_travers(g);
printf("\n");
BFS_travers(g);
return 0;
}