写出将一个无向图的邻接矩阵转换成邻接表的算法。
写出将一个无向图的邻接矩阵转换成邻接表的算法。
【正确答案】：算法描述如下： #define vnum 20 typedef struct graph { VertexType vexs[vnum]； ／／顶点信息 int arcs[-vnum_][_vnum]； ／／邻接矩阵 int vexnum，arcnum； ／／顶点数，弧(边)数 ｝GraphTp_Mat； typedef struct arcnode { int adj vex； ／／下一条弧(边)的弧头(始点)编号 struct arcnode*nextarc； ／／指向下一条弧(边)的指针 ｝ArcNodeTp； typedef struct vexnode {int vertex； ／／顶点编号 ArcNodeTp*firstarc； ／／指向第一条弧(边)的指针 ｝AdjList[vnum]； typedef struct graph ｛ AdjList adjlist； int vexnum，arcnum； ／／顶点和弧(边)的个数 ｝GraphTp—Adj； void Matrix_to_Adj list(GraphTp_Mat*ga，GraphTp_Adj*gb) {int i，j； ArcNodeTp*P； gb一>vexnum=ga一>vexnum； ／／读入顶点和边数 gb一>arcnum=ga一>arcnum； for(i=0；ivexnum；i++) { gb一>adjlis[i]．vertex=i； gb一>adjlis[i]．firstarc=NULL； ｝ for(i=0；ivexnum；i++) for(j=0；jvexnum；j++) if(ga一>arcs[i][j]==1) ｛ p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp))； p一>adjvex=j； p m>nextarc=ga一>adj lis Ei-]．firstarc； ga一>adj lis[-i]．firstrarc=P； ｝ ｝
Top
×
×