用邻接矩阵创建无向图，实现DFS+BFS |
您所在的位置：网站首页 › 邻接矩阵有向图和无向图 › 用邻接矩阵创建无向图，实现DFS+BFS |
|
由于图的复杂结构，其物理位置与逻辑位置并不匹配，不能用一维数组来存储图。可考虑用一维数组来存储图的结点信息，二维数组来存储节点间的关系，这种存储方式就叫做邻接矩阵。 图的结点结构定义： typedef struct { char vexs[ MVNum ] ;//存储结点信息 int arcs[ MVNum ][ MVNum ] ; //存储权值 int vexnum , arcnum ;//定义图的节点个数和边的条数 }AMGraph ; 查找结点元素在vexs[]数组中的下标： int LocateVex( AMGraph G , char ch ) { int i ; for( i = 0 ; i printf( "请输入第%d个结点的信息：" , i+1 ) ; scanf( "%c" , &G->vexs[ i ] ) ; getchar() ; } for( i = 0 ; i vexnum ; i++ ) for( j = 0 ; j vexnum ; j++ ) G->arcs[ i ][ j ] = MaxInt ; printf( "请输入边的条数：" ) ; scanf( "%d" , &G->arcnum ) ; getchar() ; for( i = 0 ; i arcnum ; i++ ) { int w ; char a , b ; printf( "请输入两个结点以及两节点间的边的权值：" ) ; scanf( "%c %c %d" , &a , &b , &w ) ; getchar() ; G->arcs[ LocateVex( *G , a ) ][ LocateVex( *G , b ) ] = w ; G->arcs[ LocateVex( *G , b ) ][ LocateVex( *G , a ) ] = w ; } return OK ; } 邻接矩阵实现DFS算法：DFS就相当于树的前序遍历。 用visited[]数组来标志结点是否已被遍历过。 void DFS( AMGraph G , int i ) { int j ; visited[ i ] = TRUE ; printf( "%c " , G.vexs[ i ] ) ; for( j = 0 ; j char temp ; int i , j ; Queue Q ; InitQueue( &Q ) ; for( i = 0 ; i visited[ i ] = TRUE ; printf( "%c " , G.vexs[ i ] ) ; EnQueue( &Q , G.vexs[ i ] ) ; while( !EmptyQueue( Q ) ) { DeQueue( &Q , &temp ) ; for( j = 0 ; j visited[ j ] = TRUE ; printf( "%c " , G.vexs[ j ] ) ; EnQueue( &Q , G.vexs[ j ] ) ; } } } } } printf( "\n" ) ; }判断队列已满和入队与出队的操作比较简单，这里就不一一列出。 附上源代码： #include #include #define MVNum 100 #define MaxInt 32767 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef char VerTexType ; typedef int ArcType ; typedef int Status ; typedef int Boolean ; typedef struct { VerTexType vexs[ MVNum ] ; ArcType arcs[ MVNum ][ MVNum ] ; int vexnum , arcnum ; }AMGraph ; typedef struct { char *base ; int front ; int rear ; }Queue ; Boolean visited[ MaxInt ] ; Status CreateUDN( AMGraph *G ) ; void DFS( AMGraph G , int i ) ; void DFSTraverse( AMGraph G ) ; int LocateVex( AMGraph G , char ch ) ; void InitQueue( Queue *Q ) ; int EmptyQueue( Queue Q ) ; int EnQueue( Queue *Q , char ch ) ; int DeQueue( Queue *Q , char *ch ) ; void BFSTraverse( AMGraph G ) ; int main( void ) { AMGraph G ; CreateUDN( &G ) ; DFSTraverse( G ) ; BFSTraverse( G ) ; return 0 ; } int LocateVex( AMGraph G , char ch ) { int i ; for( i = 0 ; i printf( "请输入第%d个结点的信息：" , i+1 ) ; scanf( "%c" , &G->vexs[ i ] ) ; getchar() ; } for( i = 0 ; i vexnum ; i++ ) for( j = 0 ; j vexnum ; j++ ) G->arcs[ i ][ j ] = MaxInt ; printf( "请输入边的条数：" ) ; scanf( "%d" , &G->arcnum ) ; getchar() ; for( i = 0 ; i arcnum ; i++ ) { int w ; char a , b ; printf( "请输入两个结点以及两节点间的边的权值：" ) ; scanf( "%c %c %d" , &a , &b , &w ) ; getchar() ; G->arcs[ LocateVex( *G , a ) ][ LocateVex( *G , b ) ] = w ; G->arcs[ LocateVex( *G , b ) ][ LocateVex( *G , a ) ] = w ; } return OK ; } void DFS( AMGraph G , int i ) { int j ; visited[ i ] = TRUE ; printf( "%c " , G.vexs[ i ] ) ; for( j = 0 ; j Q->base = ( char * )malloc( sizeof( char ) * MaxInt ) ; Q->front = Q->rear = 0 ; } int EmptyQueue( Queue Q ) { if( Q.front == Q.rear ) return TRUE ; else return FALSE ; } int EnQueue( Queue *Q , char ch ) { if( ( Q->rear + 1 ) % MaxInt == Q->front ) return ERROR ; else { Q->base[ Q->rear ] = ch ; Q->rear = ( Q->rear +1 ) % MaxInt ; } return OK ; } int DeQueue( Queue *Q , char *ch ) { if( EmptyQueue( *Q ) ) return ERROR ; else { *ch = Q->base[ Q->front ] ; Q->front = ( Q->front + 1 ) % MaxInt ; } return OK ; } void BFSTraverse( AMGraph G ) { char temp ; int i , j ; Queue Q ; InitQueue( &Q ) ; for( i = 0 ; i visited[ i ] = TRUE ; printf( "%c " , G.vexs[ i ] ) ; EnQueue( &Q , G.vexs[ i ] ) ; while( !EmptyQueue( Q ) ) { DeQueue( &Q , &temp ) ; for( j = 0 ; j visited[ j ] = TRUE ; printf( "%c " , G.vexs[ j ] ) ; EnQueue( &Q , G.vexs[ j ] ) ; } } } } } printf( "\n" ) ; } |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |