《邻接矩阵的深度优先遍历》由会员分享,可在线阅读,更多相关《邻接矩阵的深度优先遍历(3页珍藏版)》请在金锄头文库上搜索。
1、#include #include using namespace std;#define INFINITY 32767#define MAX_VEX 50#define OK 1#define FALSE 0#define TRUE 1#define ERROR -1bool *visited;/图的邻接矩阵存储结构typedef struct char *vexs; /动态分配空间存储顶点向量int arcsMAX_VEXMAX_VEX; /邻接矩阵int vexnum, arcnum; /图的当前定点数和弧数Graph;/图 G 中查找顶点 c 的位置int LocateVex(Grap
2、h G, char c) for(int i = 0; i G.vexnum G.arcnum;cout G.vexsi;G.vexsG.vexnum = 0; /初始化邻接矩阵for(int i = 0; i a b ;s1 = LocateVex(G,a); /找到 a 和 b 在顶点向量中的位置s2 = LocateVex(G,b);/图 G 中顶点 k 的第一个邻接顶点int FirstVex(Graph G,int k)for(int i = 0; i = 0; w = NextVex(G,v,w)if(!visitedw) DFS(G,w);/深度优先遍历void DFSTraverse(Graph G, int i) for(int j = 0; j G.vexnum; +j) /初始化所有的顶点状态为未被访问visitedj = FALSE; /遍历结点for(; i G.vexnum; +i)if(!visitedi) DFS(G,i);/主函数int main()Graph G;CreateUDN(G);visited = (bool *) malloc(G.vexnum * sizeof(bool);cout endl 深度优先遍历:;DFSTraverse(G,0);cout endl;