diagram.cpp

图的操作,包括,图的基本存储方法,有关图的操作算法并用C语言编程实现,图的搜索路径的遍历方法,以邻接矩阵和邻接表的方式存储连通图。然后分别用优先深度算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。深

//图
//（1）深度优先遍历算法
typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]； //访问标志向量是全局量
void DFSTraverse(ALGraph *G)
{ //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同
int i；
for(i=0;i<G->n;i++)
visited[i]=FALSE； //标志向量初始化
for(i=0;i<G->n；i++)
if(!visited[i]) //vi未访问过
DFS(G，i)； //以vi为源点开始DFS搜索
}//DFSTraverse
//（2）邻接表表示的深度优先搜索算法
void DFS(ALGraph *G，int i){ 
//以vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode *p；
printf("visit vertex：％c"，G->adjlist[i].vertex)；//访问顶点vi
visited[i]=TRUE； //标记vi已访问
p=G->adjlist[i].firstedge； //取vi边表的头指针
while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex])//若vi尚未被访问
DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索
p=p->next； //找vi的下一邻接点
}
}//DFS
//（3）邻接矩阵表示的深度优先搜索算法
void DFSM(MGraph *G，int i)
{ //以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵
int j；
printf("visit vertex：％c"，G->vexs[i])；//访问顶点vi
visited[i]=TRUE；
for(j=0；j<G->n；j++) //依次搜索vi的邻接点
if(G->edges[i][j]==1&&!visited[j])
DFSM(G，j)//(vi，vj)∈E，且vj未访问过，故vj为新出发点
}