圖的鄰接矩陣表示法及廣度優先遍歷

[cpp]
// 廣度優先遍歷.cpp : Defines the entry point for the console application.  
//  
 
#include "stdafx.h"  
#include <iostream>  
#include <list>  
using namespace std; 
#define MAXVEX 10  
#define INFINITY 65535  
typedef struct 
{ 
    char vexs[MAXVEX]; 
    int arc[MAXVEX][MAXVEX]; 
    int numVertexes; 
    int numEdges; 
}MGraph;//圖的數據結構，鄰接矩陣  
void CreateMGraph(MGraph *pGraph,int &numVexs,int &numEdges) 
{ 
    pGraph->numEdges=numEdges; 
    pGraph->numVertexes=numVexs; 
    for(int i=0;i<numVexs;i++) 
    { 
        cout<<"輸入第"<<i+1<<"個頂點:"; 
        cin>>pGraph->vexs[i]; 
    } 
    for(int i=0;i<numVexs;i++) 
    { 
        for(int j=0;j<numVexs;j++) 
            pGraph->arc[i][j]=INFINITY; 
    } 
    for(int i=0;i<numEdges;i++) 
    { 
        int j,k; 
        cout<<"請輸入第"<<i+1<<"條邊的下標:"; 
        cin>>j>>k; 
        pGraph->arc[j][k]=1; 
        pGraph->arc[k][j]=1; 
    } 
} 
void BFSTravers(MGraph &pGraph) 
{ 
    int num=pGraph.numVertexes; 
    list<int> queue; 
    bool *visited=new bool[num]; 
    for(int i=0;i<num;i++) 
        visited[i]=false; 
    for(int i=0;i<pGraph.numVertexes;i++) 
    { 
        if(!visited[i]) 
        { 
            cout<<"訪問頂點"<<pGraph.vexs[i]<<endl; 
            visited[i]=true; 
            queue.push_back(i); 
            while(!queue.empty()) 
            { 
                i=queue.front(); 
                queue.pop_front(); 
                for(int j=0;j<pGraph.numVertexes;j++) 
                { 
                    if(pGraph.arc[i][j]==1&&!visited[j]) 
                    { 
                        cout<<"訪問頂點"<<pGraph.vexs[j]<<endl; 
                        visited[j]=true; 
                        queue.push_back(j); 
                    } 
                } 
            } 
        } 
    } 
    delete []visited; 
} 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    MGraph graph; 
    int numVex; 
    int numEdge; 
    cout<<"輸入圖的頂點數："; 
    cin>>numVex; 
    cout<<"輸入圖的邊數："; 
    cin>>numEdge; 
    CreateMGraph(&graph,numVex,numEdge); 
    BFSTravers(graph); 
    system("pause"); 
    return 0; 
}