void PrintMGraph(MGraph G) int 1 printf("Output Vertices printf( %os"G vex); printf(n"); printf(" Output AdjMatrix: n") for (i=0 K<G. vexnum; 1++) i for (=0 j <G. vexnum; j++) printf( 94d"G arcsIN printf("In return
void PrintMGraph(MGraph G) { int i,j; printf("Output Vertices:"); printf("%s",G.vexs); printf("\n"); printf("Output AdjMatrix:\n"); for (i=0;i<G.vexnum;i++) { for (j=0;j<G.vexnum;j++) printf("%4d",G.arcs[i][j]); printf("\n"); } return; }
邻接表( Adjacency List)—一种链式存储结构 表结点 头结点 adjvex nextarc info data firstarc 把同一个顶点发出的边链接在同一个边链表 中,链表的每一个结点代表一条边,叫做表结 点(边结点),邻接点域avex保存与该边相 关联的另一顶点的顶点下标,链域nerc存 放指向同一链表中下一个表结点的指针,数 据域i存放边的权。边链表的表头指针存放 在头结点中。头结点以顺序结构存储,其数据 城data存放顶点信息,链城 firestar指向链表 中第一个顶点
邻接表 (Adjacency List)—— 一种链式存储结构 把同一个顶点发出的边链接在同一个边链表 中，链表的每一个结点代表一条边，叫做表结 点（边结点），邻接点域adjvex保存与该边相 关联的另一顶点的顶点下标 ， 链域nextarc存 放指向同一链表中下一个表结点的指针，数 据域info存放边的权。边链表的表头指针存放 在头结点中。头结点以顺序结构存储，其数据 域data存放顶点信息，链域firstarc指向链表 中第一个顶点。 表结点 头结点 adjvex nextarc info data firstarc
存储表示 typedef struct ArcNode( int adver(临接点下标); struct arcNode* nextarc(指针) int info(权值) } ArcNode;边结点类型 typedef struct VNode VertexType data(顶点信息) ArcNode *firstarc(指向第一个结点); 3VNode, AdjList MAX VERTEX NUMI typedef struct( AdjList vertices;接表 int vexnumarcnums JALGraph
存储表示 typedef struct ArcNode{ int adjvex（临接点下标）; struct ArcNode *nextarc（指针）; int info（权值）; }ArcNode; //边结点类型 typedef struct VNode{ VertexType data（顶点信息）; ArcNode *firstarc（指向第一个结点）; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; }ALGraph;
有向图的邻接表和逆邻接表 data adi dest link dest link data adj dest link E 0A 1A 0A B 2∧ B 2|C ∧ 2|C dest link 4∧ 3|D 4 E 0∧ 4E nodef'able出边表 nodet'able入边表 (a)邻接表 b)逆邻接表 在有向图的邻接表中,第i个链表中结点的个 数是顶点的出度。 在有向图的逆邻接表中,第i个链表中结点的 个数是顶点的入度
有向图的邻接表和逆邻接表 在有向图的邻接表中，第i 个链表中结点的个 数是顶点Vi的出度。 在有向图的逆邻接表中，第 i 个链表中结点的 个数是顶点Vi 的入度
带权图的边结点中保存该边上的权值。 顶点V的边链表的头结点存放在下标为i的顶 点数组中。 在邻接表的边链表中,各个边结点的链入顺序 任意,视边结点输入次序而定。 设图中有n个顶点,e条边,则用邻接表表示 无向图时,需要n个顶点结点,2e个边结点; 用邻接表表示有向图时,若不考虑逆邻接表, 只需n个顶点结点,e个边结点。 建立邻接表的时间复杂度为One)。着项点信 息即为顶点的下标,则时间复杂度为Omn+e)
带权图的边结点中info保存该边上的权值。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶 点数组中。 在邻接表的边链表中，各个边结点的链入顺序 任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示 无向图时，需要 n 个顶点结点，2e 个边结点； 用邻接表表示有向图时，若不考虑逆邻接表， 只需 n 个顶点结点，e 个边结点。 建立邻接表的时间复杂度为O(n*e)。若顶点信 息即为顶点的下标，则时间复杂度为O(n+e)