【正文】 Graph G,int v,int visited[],void Visit(DataType item))//連通圖G以v為初始結點的訪問操作為Visit()的廣度優(yōu)先遍歷//數(shù)組visited標記了相應結點是否已訪問過，0表示未訪問，1表示已訪問{ DataType u,w。 SeqCQueue queue。 Visit([v])。 //訪問結點v visited[v]=1。 //置已訪問標記 QueueInitiate(amp。queue)。 //隊列初始化 QueueAppend(amp。queue,v)。 //初始結點v入隊列 while(QueueNotEmpty(queue)) //隊列非空時 { QueueDelete(amp。queue,amp。u)。 //出隊列 w=GetFistVex(amp。G,u)。 //取結點u的第一個鄰接結點 while(w!=1) //鄰接結點w存在時 { if(!visited[w]) //若沒有訪問過 { Visit([w])。 //訪問結點w visited[w]=1。 //置已訪問標記 QueueAppend(amp。queue,w)。 //結點w入隊列 } w=GetNextVex(amp。G,u,w)。 //取下一個鄰接結點 } }}void BroadFirstSearch(AdjMGraph G,void Visit(DataType item))//非連通圖G訪問操作為Visit()的廣度優(yōu)先遍歷{ int i。 int *visited=(int *)malloc(sizeof(int)*)。 for(i=0。i。i++) visited[i]=0。 for(i=0。i。i++) if(!visited[i]) BroadFSearch(G,i,visited,Visit)。 free(visited)。}(8)/* */includeincludeincludetypedef int DataType。//定義DataType為整形define MaxSize 100define MaxVertices 10define MaxEdges 100define MaxWeight 10000 //定義無窮大的具體值define MaxQueueSize 100include includeincludeincludeincludevoid main(){ AdjMGraph g1。 //定義一個鄰接矩陣存儲結構的圖g1 RowColWeight rcw[MaxEdges]。//定義邊信息數(shù)組 int n,e,i,j。 printf(請輸入有向圖的頂點數(shù):)。 scanf(%d,amp。n)。 printf(請輸入有向圖的邊數(shù):)。 scanf(%d,amp。e)。 DataType a[MaxVertices]。//定義一個數(shù)組存儲頂點字符為整形 printf(該圖的%d個頂點字符分別為:,n)。 //輸出每個頂點字符 for(i=0。in。i++) { a[i]=i。 printf(%2d,a[i])。 } printf(\n)。 //存儲邊的信息 for(i=0。ie。i++) { printf(請輸入一條邊依附的頂點字符v1,v2及權值(v1,v2,w):)。 scanf(%d,%d,%d,amp。rcw[i].row,amp。rcw[i].col,amp。rcw[i].weight)。 } CreatGraph(amp。g1,a,n,rcw,e)。//創(chuàng)建一個鄰接矩陣存儲結構的圖g1 printf(該圖的鄰接矩陣為:\n)。 Print(amp。g1)。//輸出圖g1的鄰接矩陣 //求出鄰接矩陣存儲結構下圖g1的每個頂點的度 MVertices(amp。g1,a)。 AdjLGraph g2。//定義一個鄰接表存儲結構的圖g2 RowCol rwc[MaxEdges]。//定義邊信息數(shù)組 //用鄰接矩陣的信息生成鄰接表 for(i=0。ie。i++) { rwc[i].col=rcw[i].col。 rwc[i].row=rcw[i].row。 } CreatLGraph(amp。g2,a,rwc,)。 //求出鄰接表存儲結構下圖g2每個頂點的度 LVertices(amp。g2,a)。 //判斷圖g1的連通性 printf(圖g1是否為強連通圖:)。 if(LianTong(amp。g2,a)) { printf(YES\n)。 printf(深度優(yōu)先遍歷序列為:)。//對圖g1作DFS遍歷,輸出DFS頂點序列 DepthFirstSearch(g1,Visit)。 printf(\n)。 printf(廣度優(yōu)先遍歷序列為:)。//對圖g1作BFS遍歷,輸出BFS頂點序列 BroadFirstSearch(g1,Visit)。 } else { printf(NO\n)。 printf(深度優(yōu)先遍歷序列為:)。 DepthFirstSearch(g1,Visit)。 printf(\n)。 printf(廣度優(yōu)先遍歷序列為:)。 BroadFirstSearch(g1,Visit)。 } printf(\n)。 //輸入頂點x,查找圖g1:若存在含x的頂點,則刪除該結點及與之相關連的邊, //并作DFS遍歷否則輸出信息無x。 int x。 printf(請輸入要查找的頂點:)。 scanf(%d,amp。x)。 if(ChaZhao(amp。g1,x)) { MDelete(amp。g1,x)。 printf(刪除頂點%d后的圖的鄰接矩陣為:\n,x)。 Print(amp。g1)。 printf(刪除頂點%d后的深度優(yōu)先遍歷序列為:,x)。 DepthFirstSearch(g1,Visit)。 } else printf(不存在頂點%d\n,x)。 }第5章 時間復雜度分析算法的時間復雜度和空間復雜度（1）圖的鄰接矩陣存儲：空間復雜度為O(n2) 時間復雜度都為O(n)。（2）圖的鄰接表表示： 對于有n個頂點，e條邊的圖，該算法的時間性能為O(n+e)（3）深度優(yōu)先遍歷： 假設n為圖中的頂點數(shù)，e為邊數(shù)，則DFS算法的時間復雜性是O(n+e)（4）廣度優(yōu)先遍歷： 遍歷圖的過程實質是對每個頂點查找其鄰接點的過程，因此廣度優(yōu)先遍歷算法的時間復雜度和深度優(yōu)先遍歷算法的時間復雜度相同，也為O(n+e)，兩者的不同之處僅僅在于對頂點的訪問順序不同。參考文獻1. 何明國 Visual Basic Net程序設計—— 詳解2. 宋克 基于Brow ser/Server 結構信息系統(tǒng)的實現(xiàn)26/2