/* 图的邻接矩阵的广度优先和深度优先搜索*/
#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 10
typedef struct Graph {
char Point[MAXLEN]; /* 顶点 */
int Edge[MAXLEN][MAXLEN]; /* 邻接矩阵 */
int n; /* 顶点个数 */
int e; /* 边个数 */
int choose; /* 0代表无向图,1代表有向图 */
}Graph;
typedef struct seqQueue {
int data[MAXLEN];
int front, rear;
}seqQueen;
int visited[MAXLEN];
int visited2[MAXLEN];
int graph_Location( Graph *g, char point ) /* 定位顶点位置 */
{
int i;
for ( i = 0; i < g->n; i++ )
{
if ( point == g->Point[i] )
return(i);
}
}
void graph_Create( Graph *g ) /* 图的初始化 */
{
int m = 0, n = 0;
int count = 1;
char head, rear;
int i, j;
for ( i = 0; i < g->n; i++ )
{
printf( "请输入图的顶点:
" );
fflush( stdin );
scanf( "%c", &g->Point[i] );
}
printf( "顶点初始化完毕
" );
for ( m = 0; m < g->n; m++ )
for ( n = 0; n < g->n; n++ ) /* 将邻接矩阵初始化为0 */
{
g->Edge[m][n] = 0;
}
for ( m = 0; m < g->e; m++ )
{
printf( "请输入第%d条弧的弧尾信息:
", count );
fflush( stdin );
scanf( "%c", &rear );
printf( "请输入第%d条弧的弧头信息:
", count );
fflush( stdin );
scanf( "%c", &head );
i = graph_Location( g, rear );
j = graph_Location( g, head );
if ( g->choose == 1 )
{
g->Edge[i][j] = 1;
count++;
}else{
g->Edge[i][j] = 1;
g->Edge[j][i] = 1;
count++;
}
}
printf( "边初始化完毕
" );
}
void graph_Output( Graph *g ) /* 输出所有的边 */
{
int i, j;
for ( i = 0; i < g->n; i++ )
for ( j = 0; j < g->n; j++ )
{
if ( g->Edge[i][j] )
{
printf( "%c-->%c
", g->Point[i], g->Point[j] );
}
}
}
void graph_Output2( Graph *g ) /* 以矩阵的形式输出 */
{
int i, j;
for ( i = 0; i < g->n; i++ )
for ( j = 0; j < g->n; j++ )
{
{
printf( "%d", g->Edge[i][j] );
if ( j == g->n - 1 )
printf( "
" );
}
}
}
void graph_DFS( Graph *g, int i ) /* 深度优先查找 */
{
int j;
visited[i] = 1;
printf( "%c ", g->Point[i] );
for ( j = 0; j < g->n; j++ )
{
if ( g->Edge[i][j] == 1 && visited[j] != 1 )
{
graph_DFS( g, j );
}
}
}
void graph_DFS_Traversal( Graph *g ) /* 深度优先查找遍历 */
{
int i;
for ( i = 0; i < g->n; i++ )
{
visited[i] = 0;
}
for ( i = 0; i < g->n; i++ )
{
if ( !visited[i] )
{
graph_DFS( g, i );
}
}
}
void initQueen( seqQueen *Q ) /* 初始化队列 */
{
Q->front = 0;
Q->rear = 0;
}
int isEmpty( seqQueen *Q ) /* 队列是否为空,空返回1,不空返回0; */
{
if ( Q->front == Q->rear )
{
return(1);
}else{
return(0);
}
}
void inQueen( seqQueen *Q, int e ) /* 进栈 */
{
if ( Q->rear + 1 == MAXLEN )
{
printf( "栈满了
" );
exit( 0 );
}
Q->data[Q->rear] = e;
Q->rear++;
}
int outQueen( seqQueen *Q ) /* 出栈 */
{
int e;
if ( isEmpty( Q ) )
{
printf( "栈为空
" );
exit( 0 );
}
e = Q->data[Q->front];
Q->front++;
return(e);
}
void graph_BFS( Graph *g, int i ) /* 广度优先遍历 */
{
seqQueen Q;
int j, k;
initQueen( &Q );
printf( "%c ", g->Point[i] );
visited2[i] = 1;
inQueen( &Q, i );
while ( !isEmpty( &Q ) )
{
k = outQueen( &Q );
for ( j = 0; j < g->n; j++ )
{
if ( g->Edge[k][j] == 1 && visited2[j] != 1 ) /* 搜索顶点k的邻接顶点 */
{
printf( "%c ", g->Point[j] ); /* 若顶点未访问则访问 */
visited2[j] = 1;
inQueen( &Q, j );
}
}
}
}
void graph_BFS_Travelsal( Graph *g )
{
int i;
for ( i = 0; i < g->n; i++ )
{
visited2[i] = 0;
}
for ( i = 0; i < g->n; i++ )
{
if ( !visited2[i] )
{
graph_BFS( g, i );
}
}
}
int main( void )
{
int n;
int y = 1;
Graph g;
while ( y )
{
printf( " -------图-------
" );
printf( " ---1.建立图---
" );
printf( " ---2.输出所有的边---
" );
printf( " ---3.输出邻接矩阵---
" );
printf( " ---4.深度优先遍历---
" );
printf( " ---5.广度优先遍历---
" );
printf( " ---0.退出---
" );
printf( "请输入你的选择:
" );
scanf( "%d", &n );
switch ( n )
{
case 1: printf( "请选择建立无向图还是有向图(无向图:0,有向图:1)
" );
scanf( "%d", &g.choose );
printf( "请输入顶点个数:
" );
scanf( "%d", &g.n );
printf( "请输入边的条数:
" );
fflush( stdin );
scanf( "%d", &g.e );
graph_Create( &g );
break;
case 2: graph_Output( &g );
break;
case 3: graph_Output2( &g );
break;
case 4: graph_DFS_Traversal( &g );
break;
case 5: graph_BFS_Travelsal( &g ); break;
case 0: y = 0; break;
}
}
return(0);
}