#include?
#include?
typedef?int?InfoType;
#define	MAXV?100				/*最大頂點個數*/
/*以下定義鄰接矩陣類型*/
typedef?struct?
{??	
	int?no;						/*頂點編號*/
	InfoType?info;				/*頂點其他信息*/
}?VertexType;					/*頂點類型*/

typedef?struct??				/*圖的定義*/
{??	
	int?edges[MAXV][MAXV];?		/*鄰接矩陣*/
???	int?vexnumarcnum;???		/*頂點數，弧數*/
	VertexType?vexs[MAXV];		/*存放頂點信息*/
}?MGraph;						/*圖的鄰接矩陣類型*/

/*以下定義鄰接表類型*/
typedef?struct?ANode???????????	/*弧的結點結構類型*/
{	
	int?adjvex;??????????????	/*該弧的終點位置*/
???	struct?ANode?*nextarc;?		/*指向下一條弧的指針*/
???	InfoType?info;???????????	/*該弧的相關信息這里用于存放權值*/
}?ArcNode;

typedef?int?Vertex;

typedef?struct?Vnode??????		/*鄰接表頭結點的類型*/
{	
	Vertex?data;????????????	/*頂點信息*/
????ArcNode?*firstarc;?????		/*指向第一條弧*/
}?VNode;

typedef?VNode?AdjList[MAXV];	/*AdjList是鄰接表類型*/
typedef?struct?
{	
	AdjList?adjlist;?????????	/*鄰接表*/
????int?ne;?????????????????	/*圖中頂點數n和邊數e*/
}?ALGraph;???????????????????	/*圖的鄰接表類型*/

#define?INF?32767???????/*INF表示∞*/

void?MatToList（MGraph?gALGraph?*&G）
/*將鄰接矩陣g轉換成鄰接表G*/
{
	int?ijk=0n=g.vexnum;					/*n為頂點數*/?
	ArcNode?*p;
	G=（ALGraph?*）malloc（sizeof（ALGraph））;
	for?（i=0;i		G->adjlist[i].firstarc=NULL;

	for?（i=0;i		for?（j=n-1;j>=0;j--）?//?j?from?0?to?n-1;
			if?（g.edges[i][j]!=0）				/*鄰接矩陣的當前元素不為0*/
			{???
			???	p=（ArcNode?*）malloc（sizeof（ArcNode））;	/*創建一個結點*p*/
				p->adjvex=j;
				p->info=g.edges[i][j];
				p->nextarc=G->adjlist[i].firstarc;		/*將*p鏈到鏈表后*/
				G->adjlist[i].firstarc=p;
				k++;
				printf（“?邊?k=%d[%d%d]?“kijp->info）;
				printf（“\n“）;????/*?換行*/
			}
			
	G->n=n;
	G->e=g.arcnum;
}