数据结构-有向图邻接表邻接矩阵

「爱情、让人受尽委屈。」 2023-02-27 08:22 122阅读 0赞

#include "stdio.h"
    #include "malloc.h"
    #define INF	32767
    #define MAXV	100
     
    typedef char InfoType;
     
    typedef struct {
        
    	int		no;
    	InfoType	info;
    } VertexType;
     
    typedef struct {
        
    	int		edges[MAXV][MAXV];
    	int		n, e;
    	VertexType	vexs[MAXV];
    } MatGraph;
     
    typedef struct ANode {
        
    	int		adjvex;
    	struct ANode	* nextarc;
    	int		weight;
    } ArcNode;
     
    typedef struct Vnode {
        
    	InfoType	info;
    	int		count;
    	ArcNode		* firstarc;
    } VNode;
     
    typedef struct {
        
    	VNode	adjlist[MAXV];
    	int	n, e;
    } AdjGraph;
     
    /*
     * 创建图的邻接矩阵
     */
    void CreateMat( MatGraph &g, int A[MAXV][MAXV], int n, int e )
    {
        
    	int i, j;
    	g.n	= n;
    	g.e	= e;
    	for ( i = 0; i < g.n; i++ )
    		for ( j = 0; j < g.n; j++ )
    			g.edges[i][j] = A[i][j];
    }
     
     
    /* 输出邻接矩阵g */
    void DispMat( MatGraph g )
    {
        
    	int i, j;
    	for ( i = 0; i < g.n; i++ )
    	{
        
    		for ( j = 0; j < g.n; j++ )
    			if ( g.edges[i][j] != INF )
    				printf( "%4d", g.edges[i][j] );
    			else
    				printf( "%4s", "∞" );
    		printf( "\n" );
    	}
    }
     
     
    /*
     * 创建图的邻接表
     */
    void CreateAdj( AdjGraph * & G, int A[MAXV][MAXV], int n, int e )
    {
        
    	int	i, j;
    	ArcNode *p;
    	G = (AdjGraph *) malloc( sizeof(AdjGraph) );
    	for ( i = 0; i < n; i++ )
    		G->adjlist[i].firstarc = NULL;
    	for ( i = 0; i < n; i++ )
    		for ( j = n - 1; j >= 0; j-- )
    			if ( A[i][j] != 0 && A[i][j] != INF )
    			{
        
    				p			= (ArcNode *) malloc( sizeof(ArcNode) );
    				p->adjvex		= j;
    				p->weight		= A[i][j];
    				p->nextarc		= G->adjlist[i].firstarc;
    				G->adjlist[i].firstarc	= p;
    			}
    	G->n	= n;
    	G->e	= e;
    }
     
     
    /* 输出邻接表G */
    void DispAdj( AdjGraph *G )
    {
        
    	ArcNode *p;
    	for ( int i = 0; i < G->n; i++ )
    	{
        
    		p = G->adjlist[i].firstarc;
    		printf( "%3d->", i );
    		while ( p != NULL )
    		{
        
    			printf( "[ %d| ]→", p->adjvex);
    			p = p->nextarc;
    		}
    		printf( "∧\n" );
    	}
    }
    
    int main()
    {
        
    	MatGraph	g;
    	AdjGraph	*G;
    
    	int nn=0;
    	printf("input the number of node:\n");
    	scanf("%d",&nn);
    	int A[MAXV][MAXV];
    	printf("input the number of bian:\n");
    	int bian;
    	scanf("%d",&bian);
    	for(int i=0;i<bian;i++){
        
    		printf("input the bian （node:A->node:B）: \n");
    		int o,p;
    		scanf("%d %d",&o,&p);
    		A[o][p]=1;
    
    	}
    	int		n = 6, e = 2;
    	CreateMat( g, A, nn, e );
    	printf( "(1)图G的邻接表：\n" );//无向图 
    	DispMat( g );
    	CreateAdj( G, A, nn, e );
    	printf( "(2)图G的邻接表：\n" );
    	DispAdj( G );
    	printf( "深度优先遍历：\n" );
    	printf( "宽度优先遍历：\n" );
    	return(1);
    }