【文章內容簡介】 printf(請輸入邊的信息 (輸入格式為 :v1,v2,w)： \n)。 for (k=1。k=。k++) { scanf(\n%c,%c,%d,amp。v1,amp。v2,amp。w)。 //輸入一條邊依附的頂點和權值 j= LocateVexG(G,v2)。 i= LocateVexG(G,v1)。 //確定 v1 和 v2 在 G 中的位置 s=(ArcNode*)malloc(sizeof(ArcNode))。 sadjvex=j。 sweight=w。 snextarc=[i].firstarc。 [i].firstarc=s。//將下標為 j 的結點連接在下標為 i 的結點 后面 p=(ArcNode*)malloc(sizeof(ArcNode))。 padjvex=i。 pweight=w。 pnextarc=[j].firstarc。 [j].firstarc=p。 //將下標為 i 的結點連接在下標為 j 的結點后面 } return OK。 } Display(MGraph G,AdjMatrix GA) void Display(MGraph G,AdjMatrix GA) { //鄰接 矩陣的輸出 int i,j。 for(i=1。i=。i++) printf([%d]=%c\n,i,[i])。 //輸出頂點向量 printf(鄰接矩陣 :\n)。 for(i=1。i=。i++) { for(j=1。j=。j++) 圖的遍歷和生成樹求解 8 printf(%5d,GA[i][j].adj)。 printf(\n)。 } } DisplayG(ALGraph G) void DisplayG(ALGraph G) {//鄰接表的輸出 int i。 ArcNode *p。 for(i=1。 i=。 i++) { p=[i].firstarc。 printf((%d | %c) ,i,[i].data)。 while(p) { if(pnextarc) printf([%d,%c,%d],padjvex,[padjvex].data,pweight)。 else printf([%d,%c,%d]/\\,padjvex,[padjvex].data,pweight)。 p=pnextarc。 } printf(\n)。 } } 鄰接矩陣圖進行深度優(yōu)先遍歷 DFS1(MGraph G,int n,int v) int visited[MAX_VERTEX_NUM]。 //初始化標志數組 Status DFS1(MGraph G,int n,int v) {//基于鄰接矩陣，對圖 G 進行深度優(yōu)先搜索 int j。 AdjMatrix A。 圖的遍歷和生成樹求解 9 printf(%3d,v)。 printf(%c,[v])。 visited[v]=1。 for(j=1。j=n。j++) if(A[v][j].adj!=0amp。amp。!visited[j]) DFS1(G,n,j)。 return OK。 } InitQueue (LinkQueue amp。Q) Status InitQueue (LinkQueue amp。Q) {//建立一個空隊列 ==(QueuePtr)malloc(sizeof(QNode))。 if(!) return ERROR。 next=NULL。 return OK。 } QueueEmpty (LinkQueue Q) int QueueEmpty (LinkQueue Q) {//判斷隊列是否為空 if(==) return 1。 return 0。 } EnQueue (LinkQueue amp。Q,int e) Status EnQueue (LinkQueue amp。Q,int e) {//結點 進隊 QNode *p。 p=(QNode*)malloc(sizeof(QNode))。 if(!p) return ERROR。 pdata=e。 圖的遍歷和生成樹求解 10 pnext=NULL。 next=p。 =p。 return OK。 } DeQueue (LinkQueue amp。Q,int amp。e) int DeQueue (LinkQueue amp。Q,int amp。e) {//結點 出隊 if(==) printf(隊列為空！ \n)。 QNode *p。 p=(QNode*)malloc(sizeof(QNode))。 if(!p) return ERROR。 p=next。 e=pdata。 next=pnext。 if(==p) =。 free(p)。 return OK。 } BFS(ALGraph G,int v) int visited1[MAX_VERTEX_NUM]。//初始化標志數組 Status BFS(ALGraph G,int v) {//基于鄰接表，對 無向圖 G 進行 廣度優(yōu)先搜索 int u, w。 LinkQueue Q。 InitQueue(Q)。