graph.cpp

图的深度优先遍历和广度优先遍历

#define Max 20 
#include <stdio.h> 
#include <malloc.h> 

typedef struct{ 
    char V[Max]; 
    int arc[Max][Max]; 
    int vexnum; 
}Graph; //图的结构定义

int visited[Max];//访问标记数组为全局变量

void creatg(Graph *g, int n) { 
    int i, j;
	char r1, r2;
    char ch;
    g->vexnum = n; //定点数目
	printf("input the names of all the vertex in a string:\n");
    for(i = 1; i <= n; i++) { 
        ch = getchar();
        g -> V[i] = ch; 
	} //图形定点名称
    for(i = 1;i <= n; i++) 
       for(j = 1; j <= n; j++){ 
          g -> arc[i][j]=0; 
	   } //二维数组初始化
    printf("input the each couple of numbers related(end with '#' '#'):\n");
    
	getchar();
	scanf("%c %c",&r1,&r2); 

	
    while(r1 != '#'&&r2 != '#') { 
		for(i=1;i<=n && g -> V[i] != r1;i++) {
		}

	    for(j=1;j<=n && g -> V[j] != r2;j++) {
		}
        g -> arc[i][j] = 1; 
        g -> arc[j][i] = 1;
		getchar();
        scanf("%c %c", &r1, &r2); 
    } //输入并存储位邻接矩阵
} 

 
int firstadjvex(Graph *g,int vex) {    //找第一个不是0的且没被访问的节点
     int w, i; 
     for(i = 1; i <= g-> vexnum; i++) { 
         if(g -> arc[vex][i] == 1 && visited[i]==0) { 
             w = i; 
             break; 
		 }else { 
             w = 0; 
		 } 
	 } 
     return w; 
} 

void dfs(Graph *g, int vex){ 
    int w; 
    visited[vex] = 1; 
    printf("%c", g -> V[vex]); 
    for(w = firstadjvex(g, vex); w > 0; w = firstadjvex(g, vex)){//深度优先，然后进行平行移动 
        if(!visited[w]){ 
         dfs(g, w); //进行深度递归调用
		} 
	}
} 

void deeptraverse(Graph *g){ //深度优先遍历
    int i; 
    for(i = 1; i <= g-> vexnum; i++) visited[i]=0; 
    for(i = 1; i <= g-> vexnum; i++){ 
        if(!visited[i]){
			dfs(g, i);//找到第一个具有邻接关系的点开始遍历
		}
	}
}   
void widtraverse(Graph *g){ 
    int i, u, w; 
    int q[Max]; 
    int front = 0; 
    int rear = 0;
    for(i = 1; i <= g-> vexnum; i++){ 
        visited[i] = 0; 
	} 
    for(i = 1; i <= g-> vexnum; i++){ 
        if(!visited[i]){ //找到第一个具有邻接关系的顶点
            visited[i] = 1; 
            printf("%c", g->V[i]); 
            q[rear] = i;
	        rear = (rear + 1) % Max;//第一个顶点进队列

         do {//判断队列非空
                u=q[front]; 
		        front= (front + 1) % Max;
                for(w=firstadjvex(g, u); w > 0; w = firstadjvex(g, u)){ //与出队列的顶点有邻接关系且没有访问过的顶点进队列
                    if(!visited[w]){ 
                        visited[w] = 1; 
                        printf("%c", g -> V[w]); //出队列时打印
                        q[rear] = w;
				        rear = (rear + 1) % Max;
					} 
				} 
			} while ( front != rear);
		} 
	} 
} 
void main() 
{ 
    int n; 
    Graph *g=(Graph *) malloc(sizeof(Graph)); 
    printf("input the number of vertex:"); 
    scanf("%d", &n); 
    getchar();
    creatg(g, n);   
    printf("Breadth:\n"); 
    widtraverse(g); //广度优先遍历
    printf("\n");  
    printf("Depth:\n"); 
    deeptraverse(g); //深度优先遍历
    printf("\n");  
}