图的遍历
定义：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次的过程
遍历方法
深度优先遍历（深度优先搜索）：从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。若图中尚有顶点未被访问到，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直至图中所有顶点都被访问到为止。
类似树的前序遍历
适合目标比较明确，以找到目标为主要目的的情况
广度优先遍历（广度优先搜索）：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。
类似树的层序遍历
适合在不断扩大遍历范围是找到相对最优解
最小生成树
普里姆 (Prim ) 算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。
克鲁斯卡尔( Kruskal )算法以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树。
//myGraph.cpp #include #include #include #include #define MAX_VERTEX_NUM 20 typedef int QElemType; typedef int VRType; typedef char VertexType; typedef enum {DG,UDG} GKind; //{有向图,无向图} typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QPtr; typedef struct { QPtr front; QPtr tail; }LinkQueue; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 int vexnum,arcnum; //顶点数和弧数 GKind kind; //图的种类标识 }MGraph; //初始化队列 void InitQ(LinkQueue &Q); //从队尾插入元素 void EnQueue(LinkQueue &Q,QElemType e); //从对首删除元素 void DeQueue(LinkQueue &Q,QElemType &e); //队列是否为空，为空返回1，否则返回0 int QEmpty(const LinkQueue &Q); //选择创建图的类型 void CreatGraph(MGraph &G); //创建无向图 void CreatUDG(MGraph &G); //创建有向图 void CreatDG(MGraph &G); //打印邻接矩阵 void printArcs(const MGraph &G); //返回字符在定点向量中的下标值 int LocateVex(const MGraph &G,VertexType ch); //深度优先遍历函数 void DFSTraverse(const MGraph &G); void DFS(const MGraph &G,int v); //广度优先遍历函数 void BFSTraverse(const MGraph &G); //得到第一个未被访问的相邻节点下标，若无，则返回-1 int firstAjdVex(const MGraph &G,int v); //得到下一个未被访问的相邻节点下标，若无，则返回-1 int nextAjdVex(const MGraph &G,int v,int w); int *visited; //记录顶点是否被访问 //主函数 int main() { MGraph G; CreatGraph(G); printf("\n原始连接矩阵:\n"); printArcs(G); //深度优先遍历结果 printf("\n深度优先遍历:"); DFSTraverse(G); //广度优先遍历结果 printf("\n广度优先遍历:"); BFSTraverse(G); printf("\n"); return 0; } //初始化队列 void InitQ(LinkQueue &Q) { Q.front = Q.tail = (QPtr)malloc(sizeof(struct QNode)); if ( !Q.front ) { printf("InitQ分配内存出错!\n"); return ; } Q.front->next = NULL; } //从队尾插入元素 void EnQueue(LinkQueue &Q,QElemType e) { QPtr q = (QPtr)malloc(sizeof(struct QNode)); if ( !q ) { printf("EnQueue分配内存出错!\n"); return ; } q->data = e; q->next = NULL; Q.tail->next = q; //如果是第一次插入，Q.front->next也指向了q Q.tail = q; } //从对首删除元素 void DeQueue(LinkQueue &Q,QElemType &e) { if ( Q.front == Q.tail ) { printf("DeQueue队列为空，不能删除元素!\n"); return ; } QPtr q = Q.front->next; e = q->data; Q.front->next = q->next; if ( Q.tail == q ) Q.tail = Q.front; free(q); } //队列是否为空，为空返回1，否则返回0 int QEmpty(const LinkQueue &Q) { if ( Q.front == Q.tail ) { return 1; } else { return 0; } } //选择创建图的类型 void CreatGraph(MGraph &G) { int k; printf("---------------------\n创建有向图，输入0;\n创建无\ 向图，输入1;\n并按下确认键.\n---------------------\n输入:"); scanf("%d",&k); switch(k) { case 0: G.kind = DG; CreatDG(G); break; case 1: G.kind = UDG; CreatUDG(G); break; default: printf("图类型输入有误!"); break; } } //创建无向图 void CreatUDG(MGraph &G) { int i,j,k,w; char v1,v2; printf("输入顶点数和边数："); scanf("%d%d",&G.vexnum,&G.arcnum); visited = (int *)malloc(G.vexnum*sizeof(int)); for ( i = 0; i < G.vexnum; i++ ) visited[i] = 0; printf("请按次序输入%d个顶点字母标号(如ABC等)：",G.vexnum); getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 for ( i = 0; i < G.vexnum; i++ ) scanf("%c",&G.vexs[i]); getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 for ( i = 0; i < G.vexnum; ++i ) for ( j = 0; j < G.vexnum; ++j ) {//初始化邻接矩阵 if ( i == j ) G.arcs[i][j] = 0; else G.arcs[i][j] = INT_MAX; } printf("输入边的顶点和权值(如A B 1):\n"); for ( k = 0; k < G.arcnum; k++ ) { scanf("%c %c %d",&v1,&v2,&w); i = LocateVex(G,v1); j = LocateVex(G,v2); G.arcs[i][j] = w; G.arcs[j][i] = w; getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 } } //创建有向图 void CreatDG(MGraph &G) {//和创建无向图类似，只是少了一句将G.arcs[j][i] = w; //因为无向图是对称的，而有向图不是 int i,j,k,w; char v1,v2; printf("输入顶点数和边数："); scanf("%d%d",&G.vexnum,&G.arcnum); visited = (int *)malloc(G.vexnum*sizeof(int)); for ( i = 0; i < G.vexnum; i++ ) visited[i] = 0; printf("请按次序输入%d个顶点字母标号(如ABC等)：",G.vexnum); getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 for ( i = 0; i < G.vexnum; i++ ) scanf("%c",&G.vexs[i]); getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 for ( i = 0; i < G.vexnum; ++i ) for ( j = 0; j < G.vexnum; ++j ) {//初始化邻接矩阵 if ( i == j ) G.arcs[i][j] = 0; else G.arcs[i][j] = INT_MAX; } printf("输入边的顶点和权值(如A B 1):\n"); for ( k = 0; k < G.arcnum; k++ ) { scanf("%c %c %d",&v1,&v2,&w); i = LocateVex(G,v1); j = LocateVex(G,v2); G.arcs[i][j] = w; getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 } } //打印邻接矩阵 void printArcs(const MGraph &G) { int i; int j; for ( i = 0; i < G.vexnum; i++ ) { for ( j = 0; j < G.vexnum; j++ ) { if ( INT_MAX == G.arcs[i][j]) printf("%6s%","INF"); else printf("m",G.arcs[i][j]); } printf("\n"); } } //返回字符在定点向量中的下标值 int LocateVex(const MGraph &G,VertexType ch) { int i; for ( i = 0; G.vexnum; i++ ) if ( ch == G.vexs[i] ) return i; return -1; } //深度优先遍历函数 void DFSTraverse(const MGraph &G) { int i; for ( i = 0; i < G.vexnum; i++ ) visited[i] = 0; //初始化访问标记数组 for ( i = 0; i < G.vexnum; i++ ) if ( !visited[i] ) {//对尚未访问的顶点调用DFS DFS(G,i); } printf("\n"); } void DFS(const MGraph &G,int v) { int w; visited[v] = 1; printf("%-4c",G.vexs[v]); for ( w = firstAjdVex(G,v); w >= 0; w = nextAjdVex(G,v,w) ) if ( !visited[w] ) DFS(G,w); } //广度优先遍历函数 void BFSTraverse(const MGraph &G) { int i,w,v; LinkQueue Q; InitQ(Q); for ( i = 0; i < G.vexnum; i++ ) visited[i] = 0; //初始化访问标记数组 for ( i = 0; i < G.vexnum; i++ ) { if ( !visited[i] ) { visited[i] = 1; printf("%-4c",G.vexs[i]); EnQueue(Q,i); while (!QEmpty(Q)) { DeQueue(Q,v); for ( w = firstAjdVex(G,v); w >= 0; w = nextAjdVex(G,v,w) ) { if ( !visited[w] ) { visited[w] = 1; printf("%-4c",G.vexs[w]); EnQueue(Q,w); } } } } } } //得到第一个未被访问的相邻节点下标，若无，则返回-1 int firstAjdVex(const MGraph &G,int v) { int i; for ( i = 0; i < G.vexnum; i++ ) { if ( !visited[i] && G.arcs[v][i] > 0 && G.arcs[v][i] < INT_MAX) return i; } return -1; } //得到下一个未被访问的相邻节点下标，若无，则返回-1 int nextAjdVex(const MGraph &G,int v,int w) { int i; for ( i = w; i < G.vexnum; i++ ) { if ( !visited[i] && G.arcs[v][i] > 0 && G.arcs[v][i] < INT_MAX) return i; } return -1; }
