本文共 1616 字，大约阅读时间需要 5 分钟。
图的两种存储方式：邻接矩阵和邻接表；
两种遍历方式：深度优先和广度优先；首先以一个结构体存储一个图：
struct MGraph{ int vertex[maxvertex]; //存顶点 int arc[maxvertex][maxvertex]; //存边（邻接矩阵） int vertexnum,arcnum; //顶点数和边数}; 其次是对图的初始化：
void CreatMGraph(MGraph *&G){ int i,j; cin1>>G->vertexnum>>G->arcnum; //输入顶点数和边数 for(i=0;i vertexnum;i++) //输入每个顶点的值 cin1>>G->vertex[i]; for(i=0;i vertexnum;i++) //初始化邻接矩阵 for(j=0;j vertexnum;j++) G->arc[i][j]=0; for(i=0;i arcnum;i++) { int n,m,w; cin1>>n>>m>>w; //修改邻接矩阵中的值 G->arc[n][m]=w; G->arc[m][n]=w; }} 在此之前需要定义一个全局变量的visited数组：
int visited[maxvertex]; //标记已被访问过的顶点(全局变量)//广度优先遍历void BFS(MGraph *&G,int v){ queue q; int x,j; if(!visited[v]) //即为visited[v]==0，也就是未被访问过 { cout< vertex[v]<<" "; visited[v]=1; q.push(v); //被访问的顶点入队 } while(!q.empty()) //队不空进循环 { x=q.front(); //取队头元素 q.pop(); //队头出队 for(j=0;j vertexnum;j++) if (G->arc[x][j]&&!visited[j]) { cout< vertex[j]<<" "; visited[j]=1; //标记为访问过 q.push(j); //被访问的顶点继续入队 } }}//深度优先遍历void DFS(MGraph *&G,int v){nt j; if(!visited[v]) { cout< vertex[v]<<" "; visited[v]=1; //标记为访问过 } for(j=0;j vertexnum;j++) if (G->arc[v][j]&&!visited[j])//邻接矩阵的第(v,j)元素不为0 { //且未被访问过则递归 DFS(G,j); }} 此为图的邻接矩阵的输出函数：
void Print(MGraph *G){ int i,j; for(i=0;i vertexnum;i++) { for(j=0;j vertexnum;j++) cout< arc[i][j]<<" "; cout< main函数调用上面函数：
int main(){ MGraph *G=new MGraph; CreatMGraph(G); cout<<"输出邻接矩阵:"< 转载地址：http://gpxgi.baihongyu.com/