将无向图的邻接矩阵转为对应邻接表

wuchangjian2021-11-03 21:18:09编程学习
//以下定义邻接矩阵类型  
typedef struct                  
{
	int vexs[MAXV];      		 
    int arcs[MAXV][MAXV];       
    int vexnum,arcnum;          
} MGraph;                       
//以下定义邻接表类型
typedef struct ANode            
{
    int adjvex;                 
    struct ANode *nextarc;        
} ArcNode;
typedef struct Vnode           
{
    int data;                
    ArcNode *firstarc;         
} VNode;
typedef struct
{
    VNode vertices[MAXV];            
    int vexnum,arcnum;               
} ALGraph;                      
void MatToList(MGraph g,ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{
    int i,j;
    ArcNode *p,*s;
    G=(ALGraph *)malloc(sizeof(ALGraph));
    for (i=0; i<g.vexnum; i++)             
        G->vertices[i].firstarc=NULL;
    for (i=0; i<g.vexnum; i++)    
        for (j=0; j<g.vexnum; j++)
            if (g.arcs[i][j]!=0) 
            {
	 			p=(ArcNode *)malloc(sizeof(ArcNode)); 
	            p->adjvex=j; p->nextarc=NULL;
				if(!G->vertices[i].firstarc)
					G->vertices[i].firstarc=p;
				else{
					s=G->vertices[i].firstarc;
					while(s->nextarc) s=s->nextarc;
					s->nextarc=p;
				}
            }
    G->vexnum=g.vexnum;
    G->arcnum=g.arcnum;
}

相关文章

Streaming Systems 笔记一

Part 1 The Beam Model CHAPTER 1 Streaming 1...

时间序列预测的7种Python工具包,总有一款适合你

时间序列预测的7种Python工具包,总有一款适合你

欢迎关注我,IT界搬运喵专注Python!   时间...

Java如何实现线程唤醒与阻塞

转自:微点阅读(www.weidianyuedu.com&#...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。