图的遍历ywc.cpp

只要就是用来实现图的遍历的功能

#include<iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include<iomanip.h>

#define MaxQueue 100 // 队列的最大容量  

struct node    // 图形的顶点结构
{
    int vertex;    //顶点资料 
    struct node *nextnode; //指向下一顶点的指针
};
typedef struct node *graph; // 与顶点相关的图形的指针
struct node head[60]; // 图形顶点的结构数组 
int visited[60]; //遍历记录数组 

int queue[MaxQueue]; // 队列的数组
int front = -1; // 队列的前端 
int rear = -1; // 队列的后端 

/* ---------------------------------------- */
/*               建立图形                   */
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
    graph newnode; // 新顶点指针
    graph ptr;
    int from; // 边的起点 
    int to; // 边的终点
    int i;
    for ( i = 0; i < num; i++ ) // 将顶点相连
	{
        from = node[i*2]; //边的起点 
        to = node[i*2+1]; //边的终点 
        newnode = ( graph ) malloc(sizeof(struct node));  // 建立新顶点
        newnode->vertex = to; // 建立顶点内容 
        newnode->nextnode = NULL; // 设定指针初值 
        ptr = &(head[from]); // 顶点位置 
        while ( ptr->nextnode != NULL ) // 遍历至链表尾
        ptr = ptr->nextnode; // 下一个顶点 
        ptr->nextnode = newnode; // 插入表尾
	}
}


/* ---------------------------------------- */
/*           图形的深度优先遍历             */
/* ---------------------------------------- */
void DFS(int current)
{
    graph ptr;
    visited[current] = 1; // 记录已遍历过的顶点
    cout<<current<<"->"; // 印出遍历顶点
    ptr = head[current].nextnode; // 顶点位置 

    while ( ptr != NULL ) // 遍历至链表尾 
	{

        if ( visited[ptr->vertex] == 0 ) // 如果没遍历过 
            DFS(ptr->vertex); // 递归访问此顶点 
        ptr = ptr->nextnode; // 下一个顶点 
	}
}



/* ---------------------------------------- */
/*           图形的广度优先遍历             */
/* ---------------------------------------- */

int EnQueue(int value)   // 入队操作
{
   if ( rear >= MaxQueue ) // 检查队列是否全满 
         return -1;      // 队满将无法存入 
    rear++;        // 后端指针往前移 
    queue[rear] = value;   // 存入队列 
    return 1;
}

int DeQueue()   //出队操作
{
    if ( front == rear ) // 检查队列是否是空 
        return -1; // 无法取出 
    front++; // 前端指针往前移 
    return queue[front]; // 出列 
}

void BFS(int current)
{
   graph ptr;
   EnQueue(current); // 将顶点存入队列 
   visited[current] = 1; // 记录已遍历过的顶点 
   cout<<current<<" ->"; // 印出遍历顶点 

   while ( front != rear ) // 队列是否是空 
   {
       current = DeQueue(); // 将顶点从队列取出 
       ptr = head[current].nextnode; // 顶点位置 

       while ( ptr != NULL ) // 遍历至链表尾 
	   {
           if ( visited[ptr->vertex] == 0 ) // 如果没遍历过 
		   {
               EnQueue(ptr->vertex); // 顶点入队 
               visited[ptr->vertex] = 1; // 记录已遍历过
              cout<<ptr->vertex<<" ->";// 印出遍历顶点 
		   }
           ptr = ptr->nextnode; // 下一个顶点 
	   }
   }
}

/* ---------------------------------------- */
/* 主程式: 建立图形后,将遍历内容印出.       */
/* ---------------------------------------- */
void main()
{
    while(1)
	{
        char c,a;
        graph ptr;
        int i;
        int node[60][2] = { {1, 10}, {10, 1},    // 边线数组 
		{2, 10}, {10, 2},{2, 3}, {3, 2},{3, 4}, {4, 3},
		{3, 12}, {12, 3},{4, 13}, {13, 4},{4, 5}, {5, 4},
		{5, 6}, {6, 5},{5, 7}, {7, 5},{7, 8}, {8, 7},
		{9, 10}, {10, 9},{10, 11}, {11, 10},{11, 14}, {14, 11},
		{11, 12}, {12, 11},{12, 15}, {15, 12},{12, 13}, {13, 12},
		{13, 16}, {16, 13},{14, 17}, {17, 14},{14, 18}, {18, 14},
		{15, 19}, {19, 15},{16, 20}, {20, 16},{17, 18}, {18, 17},
		{18, 23}, {23, 18},{18, 19}, {19, 18},{19, 23}, {23, 19},
		{19, 24}, {24, 19},{19, 20}, {20, 19},{20, 21}, {21, 20},
		{22, 23}, {23, 22},{24, 25}, {25,24}
		};
cout<<"/*------------------------------------------------*/\n";
cout<<"/*          图遍历的演示程序 (7.6书本最短路径)    */\n";
cout<<"/*------------------------------------------------*/\n";
cout<<"\n\n";
cout<<"以 下 为 各 城 市 的 代 码:\n\n";
cout<<"  1:乌鲁木齐;  2:呼和浩特;   3:北京;    4:天津;   5:沈阳;\n";
cout<<"  6:大连;      7:长春;       8:哈尔滨;  9:西宁;  10:兰州;\n";
cout<<" 11:西安;     12:郑州;      13:徐州;   14:成都;  15:武汉;\n";
cout<<" 16:上海;     17:昆明;      18:贵阳;   19:株州;  20:南昌;\n";
cout<<" 21:福州;     22:南宁;      23:柳州;   24:广州;  25:深圳;  \n";cout<<"\n\n";
for (i=1;i<=25;i++ )
		{
            head[i].vertex=i; // 各个顶点值 
            head[i].nextnode=NULL; 
            visited[i]=0;  // 设定遍历初值 
		}

        creategraph(&node[0][0],60); // 建立图形 

       cout<<"请问是否打印图形的邻接链表内容?(Y/N?)"<<endl;
       c=getch();
       cout<<"图 形 的 邻 接 链 表 内 容(即各城市的相连情况):"<<endl;
	    if(c=='y'||c=='Y')
		{
            for (i=1;i<=25;i++)
			{
              cout<<"顶点:"<<head[i].vertex<<"=>"; // 顶点值 
		        ptr=head[i].nextnode; // 顶点位置 
                while(ptr!=NULL) // 遍历至链表尾 
				{
                  cout<<ptr->vertex<<"=>";// 印出顶点相连情况 
                  ptr=ptr->nextnode; //下一个顶点 
				}
		        cout<<endl;
		}
	}
        cout<<endl;
        cout<<"请 选 择 你 需 要 的 操 作"<<endl;
        cout<<"1、图形的深度优先遍历请输入:'D'或'd':"<<endl;
        cout<<"2、图形的广度优先遍历请输入:'B'或'b':"<<endl;
    	c=getch();
        switch(c)
		{
            case'D':case'd':
                cout<<"\n请 输 入 起 始 顶 点:"<<endl;
                cin>>i;
                cout<<endl<<endl;
                cout<<"图 形 的 深 度 优 先 遍 历 的 内 容 为:\n";
                DFS(i); 
                cout<<endl;
                break;

             case'B':case'b':
                 cout<<"请 输 入 起 始 顶 点:"<<endl;
                 cin>>i;
                 cout<<endl;
                 cout<<"图 形 的 广 度 优 先 遍 历 的 顶 点 内 容:"<<endl;
                 BFS(i); 
                 cout<<endl; 
                 break;
		}
	    cout<<"\n请 问 你 是 否 要 继 续:(y/n)";
        cout<<"\n\n";
        a=getch();
        if(a!='y'&&'Y')
		 exit(0);
        
    }
}