【精】图编程总结（编程过程的总结）

编程过程与思维状态

编程是一个需要注意力高度集中的过程，不仅是编码的过程，而且构建算法与数据结构的过程也必须如此。因为整个过程可能有很多状态，稍微不注意就会忽略或陷入混乱。人是高度进化的动物，能够处理很多出乎意料之外的事情，但是计算机却没有办法，如果出现之前未考虑的情况，计算机最可能的反应就是出错与崩溃。

然而就算注意力完全集中，一个人大脑中的缓存也是有限的，不可能同时保持着那么多状态与变量的状态，但人脑不会内存溢出，取而代之的是混乱。我们要清晰编程，而不要混乱编程。因此就必须应用从上至下，逐步求精的过程，先从问题的性质与规律入手，然后进行算法与数据结构的构想，等这一切都无懈可击之后在开始写代码，编码中写好注释，真正的编码时间不应该超过整个过程的百分之三十。尽量在纸张上写出相关的状态与过程，以便于之后的参照。

进一步具体的说一下编程的过程：

1、问题探索过程，观察思考问题的性质，找到问题及其对象中存在的规律，从而找到一种人能够实现的有周期性的解法。

2、算法的求精与数据结构、模块、接口的设计：将抽象性较高的周期性解法转化为计算机能够执行的算法，将程序框架以及具体实现都设计好，最后的代码就是这个过程结果的充实。

3、根据伪代码编码，在写每个块状结构之前都必须注释上这个块状结构的功能与实现。

4、debug与测试。

debug

debug是非常重要的，我总结的常用办法有三个：

1、错误代码段定位，缩小搜索范围是节省时间的重要方法。

2、抓住一些关键的量（状态指示量），将代码的运行状态显示出来。不要让代码成为脱缰的野马，在写代码的时候，每一个结构块之前都要注释这一个结构块的功能实现，在debug的时候，用运行状态变量来保证代码的运行情况在掌握之中。

3、利用大量的多种类型的可能输入进行测试（对于初步运行正常的程序）

虽然debug技非常关键，但是一次性命中仍然是努力的目标，每次写代码都必须努力减少bug出现的几率，一个好的方法是分块分段来写程序，对块段的测试bug的出现，也可以减少debug上的时间。

debugee1：当vertex[n]被声明但n还没定义的时候，DEV并不报错，但运行的时候却有时会出现诡异的错误，也就是vertex的地址发生改变，访问vertex内的元素时出现崩溃。这个bug虽然是被编译器放过而变得很隐蔽，但是仍然不应该困扰那么长时间，因为当系统中某一个环节问题的时候，你必须考虑它所有的元素是否都正常，如果能看到的元素是正常的，就必须考虑那些隐藏的元素。一个变量出现诡异的变化，不仅要看它被调用、修改的过程，也要注意到它的声明与定义的过程。

debugee2：二维数组的传递需要列的信息，为了克服这一问题，用一个指针数组来存储这个各行的头指针。

debugee3:算法与数码实现的代沟，或者说是伪代码与代码之间的代沟，当你用抽象语言来期望完成某个功能的时候，用代码写出来却会出现言不达意的错误。就像这里，原来把if中语句放在for语句的中间期望完成同样的功能，但实际上会出现bug。这类问题的解决方法在于编程过程的把握。

debugee4：debugee5：算法本身的漏洞，没有把问题考虑周全，可能将同一个未访问的顶点多次放入栈中。debugee5中指针指来指去比较复杂，容易出错。这类问题的解决方法在于编程过程的把握。

debugee6：对于向量的应用不是很熟悉，对于迭代子也不了解，很多功能函数是基于向量迭代子的，所以，很多时候用迭代子比较好。但是如果直接用计数变量也可以，因为可以用再一次计数方法来得到相应位置的迭代子。

debugee7：对于指针的new的理解模糊，实际情况是new一个空间，把给定的指针的值改为new空间的首地址。因此，a=b，a=newint这样的行为会使a的值改变，但是不会使b的值改变，这是很明显的。这是指针与普通变量的相似点。

附上代码，代码在DEV下编译通过。（代码有点乱，因为同时用了邻接表与邻接矩阵两种方式来锻炼下。）

/*********************
*这是一个具有一定通用性的程序,具有邻接矩阵和邻接表的双操作，这让我们收获更多。
*带有的功能包括：邻接矩阵与邻接表之间的相互装换与操作、DFS、BFS、最小生成树。
*界面支持有向图、无向图，支持从文件输入，也支持从键盘输入。 
*********************/
#include<iostream>
#include<fstream>
#include<stack>
#include<queue>
#include<vector>
#include<stdlib.h>
#define MAX 100
#define NAME_LENGHT 30
using namespace std;
int n;
int matrix[MAX][MAX];
struct Vertex;
struct Edge{
   int value;
   Vertex *next_ver;
   Edge *next_edge;
};
struct Vertex{
   int num;
   int visited;
   Edge *edge;
};
struct remain{//在PRIM算法中用到的特殊结构 
   int father;
   int self;
   int value;
}; 
struct value_edge{//在去边法中用到的特殊结构 
   int pre_ver;
   int next_ver;
   int value;
}; 

void GetMatrix(int n);
void Transform(Vertex *vertex,int **matrix,const int n);//将邻接矩阵转换为邻接表 
bool isCircuit(int n,Vertex *);//通过邻接表DFS判断是否有回路 
bool isCircuit_by_matrix(int n,int **new_matrix);//通过邻接矩阵DFS判断是否有回路 
Vertex** DFS(int n,Vertex*,int flag);//通过邻接表 ,flag为1如果是用来判断是否有环 
Vertex** BFS(int n,Vertex*,int flag);//通过邻接矩阵 
Vertex* minTree_P(int n,Vertex*);//求最小生成树，P算法 
Vertex* minTree_K(int n,Vertex*);//求最小生成树，K算法 
Vertex* minTree_rP(int n,Vertex*);//求最小生成树，去边法 
int isConnected(int n,Vertex *);//判断图是否连通 
int findposition(vector<remain>,int num,int value);           
int findmin(vector<remain> );
void print_to_matrix(int n,Vertex* vertex); //将邻接表以邻接矩阵方式打印出来 
int main()
{
    int choice,i,j; 
    cout<<"输入1从文件读取，输入2从键盘输入;"<<endl;
    if (!(cin>>choice)) exit(-1); 
    cout<<"请输入邻接矩阵的大小，即n的值："<<endl; 
    if (!(cin>>n)) exit(-1);
    Vertex vertex[n];//邻接表表示法的节点；//debugee1
    
    if (choice==1){
       char filename[NAME_LENGHT];
       to:
       cout<<"please input file name;"<<endl;  
       if (cin>>filename){
          ifstream myfile(filename); 
          if (!myfile){
             cerr<<"no such file in the diretory;"<<endl;
             goto to;            
          }
          else{ //输入到邻接矩阵 
              for (i=0;i<n;i++) 
                  for (j=0;j<n;j++) 
                      myfile>>matrix[i][j]; 
              myfile.close();
          }                  
        }
        else
           exit(-1);
    }
    else if (choice==2){
         cout<<"please key in the matrix;"<<endl;
         GetMatrix(n);
    }
    else
        exit(-1);

    //用邻接矩阵转创建邻接表    
    int *tm[n];
    for (i=0;i<n;i++)
        tm[i]=matrix[i];  //debugee2
    Transform(vertex,tm,n); 
    
    //DFS && BFS 
    Vertex** dfs_finished=DFS(n,vertex,0);
    Vertex** bfs_finished=BFS(n,vertex,0); 
    
    cout<<"DFS深度优先搜索原图的结果，用节点表示/n"; 
    for (i=0;i<n;i++)
        cout<<dfs_finished[i]->num+1<<" ";
    cout<<endl;    
    cout<<"BFS广度优先搜索原图的结果，用节点表示/n";
    for (i=0;i<n;i++)
        cout<<bfs_finished[i]->num+1<<" ";
    cout<<endl;
    
    //求最小生成树，P算法 ,并用广度优先搜索按层输出    
    Vertex* mt1=minTree_P(n,vertex);
    print_to_matrix(n,mt1);
    //求最小生成树，K算法 ,并用广度优先搜索按层输出
    Vertex* mt2=minTree_K(n,vertex);
    print_to_matrix(n,mt2);
    //求最小生成树，破圈法 ,并用广度优先搜索按层输出
    Vertex* mt3=minTree_rP( n,vertex);
    print_to_matrix(n,mt3);
    
    system("pause");
    return 0;
}

void GetMatrix(int n)
{
     int i,j;
     for (i=0;i<n;i++)
         for (j=0;j<n;j++)
             cin>>matrix[i][j];
}

void Transform(Vertex *vertex,int **new_matirx,const int n)
{
     int i,j,first;
     Edge *here;

    
     for (i=0;i<n;i++){
         vertex[i].num=i;
         vertex[i].edge=NULL;
         first=1;
         for (j=0;j<n;j++)
             if (new_matirx[i][j]!=0){
                //creat a edge
                if  (first==1){
                    first=0;
                    here=vertex[i].edge=new Edge;
                }
                else{
                    here=here->next_edge=new Edge;
                }
                here->next_ver=&vertex[j];
                here->value=new_matirx[i][j];
                here->next_edge=NULL;
             }
     }
}

Vertex** DFS(int n,Vertex* vertex,int flag)
{    
    Vertex **finished=new Vertex*[n]; 
      
    stack<Vertex*> vstack;
    int i,time ;
    Edge *edge;
    Vertex *visit;
    for (i=0;i<n;i++) vertex[i].visited=0; 
    
    for (i=0,time=0;i<n;i++){
        if (vertex[i].visited)             //debugee3 
           continue;
        if (flag==2&&i>0)
           return NULL;
           
        vstack.push(&vertex[i]);
        while (!vstack.empty()){
              do {
              visit=vstack.top();
              vstack.pop(); 
              } while (visit->visited&&!vstack.empty()); //debugee4 
              if (vstack.empty()&&visit->visited)
                 break;
                 
              visit->visited=1;
              finished[time]=visit;
              for (edge=visit->edge;edge;edge=edge->next_edge){
                  if (!edge->next_ver->visited)
                      vstack.push(edge->next_ver); 
                  else if (flag==1)
                     return NULL;
              }     
              time++;
        }   
    }
    
    return finished; 
}

Vertex** BFS(int n,Vertex* vertex,int flag)
{
    Vertex **finished=new Vertex*[n]; 
     
    queue<Vertex*> vqueue;
    int i,time ;
    Edge *edge;
    Vertex *visit; 
    for (i=0;i<n;i++) vertex[i].visited=0;  
   
    for (i=0,time=0;i<n;i++){
        if (vertex[i].visited)
           continue;
           
        vqueue.push(&vertex[i]);
        while (!vqueue.empty()){
              do {
              visit=vqueue.front();
              vqueue.pop();
              } while (visit->visited&&!vqueue.empty());
              if (vqueue.empty()&&visit->visited)
                 break;
                 
              if (flag==1)
                 cout<<visit->num+1<<" ";
                 
              visit->visited=1;
              finished[time]=visit;
              for (edge=visit->edge;edge;edge=edge->next_edge)
                  if (!edge->next_ver->visited)
                     vqueue.push(edge->next_ver); 
              time++;
        }   
    }
    if  (flag==1)
        cout<<endl;
    return finished;  
}

bool isCircuit(int n,Vertex *vertex)
{
    if (DFS(n,vertex,1))
       return 0;//无圈 
    else
        return 1;//有圈 
}

Vertex* minTree_P(int n,Vertex *vertex)//求最小生成树，P算法   //debugee5 
{
      int i,j,rp,p;
      vector<remain> remains;
      Vertex* tree=new Vertex[n];
      Edge* edge,**newedge;
      remain  rmin,newrem;
      
      //初始化，并建立生成树的首节点 
      for (i=0;i<n;i++){ 
          tree[i].num=vertex[i].num;
          tree[i].edge=NULL;
          vertex[i].visited=0;
      }  
      vertex[0].visited=1;
      for (edge=vertex[0].edge;edge;edge=edge->next_edge)  {
          newrem.father=0;
          newrem.self=edge->next_ver->num;
          newrem.value=edge->value;
          remains.push_back(newrem);
      }

      for (i=1;i<n;i++){  
          //找到最小代价的相邻节点
          rp=findmin(remains);  
          rmin.father=remains[rp].father;
          rmin.self=remains[rp].self;
          rmin.value=remains[rp].value;
          vector<remain>::iterator  iter ;                 //debugee6
          for (j=0,iter=remains.begin();j<rp;iter++,j++);
          remains.erase(iter);
          //建立相连接的边与初始化数值
          newedge=&tree[rmin.father].edge;               //debugee7 
          while (*newedge)  newedge=&((*newedge)->next_edge);
          *newedge=new Edge;
          (*newedge)->value=rmin.value;
          (*newedge)->next_edge=NULL;
          (*newedge)->next_ver=&tree[rmin.self]; 
          vertex[rmin.self].visited=1;
          //修改vector,将新增加的点周围的visited为0的点加入 
          
          for (edge=vertex[rmin.self].edge;edge;edge=edge->next_edge) 
              if (!edge->next_ver->visited){ 
                 p=findposition(remains,edge->next_ver->num,edge->value);      
                 if (p==-1){//vector中不存在此节点，直接添加 
                     newrem.father=rmin.self;
                     newrem.self=edge->next_ver->num;
                     newrem.value=edge->value;
                     remains.push_back(newrem);
                 }
                 else if (p>=0){ //vector中存在此点，但是距离更大，需要用新的节点连接方式替换原先的连接方式
                     remains[p].father=rmin.self;
                     remains[p].self=edge->next_ver->num;
                     remains[p].value=edge->value;
                 }//若p<-1，则vector中存在此节点，且已存在节点距离更小，无需添加
              }
      }   
      return tree;
}

int findposition(vector<remain> remains,int num,int value)
{ 
    int i;
    for (i=0;i<remains.size();i++){
       if (remains[i].self==num){
          if (value<remains[i].value)
             return i;//返回在向量中位置 ，代表覆盖先前的值 
          else
              return -2;//代表无需放入向量 
       }
    }
    return -1;//代表可以直接放入向量 
}
        
int findmin(vector<remain> remains)
{ 
    int i,minvalue=remains[0].value,minnum=0; 
    for (i=0;i<remains.size();i++){
       if (remains[i].value<minvalue){
          minvalue=remains[i].value;
          minnum=i;
       }
    }
    return minnum;
}

Vertex* minTree_K(int n,Vertex*)//求最小生成树，K算法 
{
      int i,j,k;       
      int new_matrix[n][n]; 
      value_edge temp;
      vector<value_edge>  edge;
      for (i=0;i<n;i++)
          for (j=0;j<n;j++)
              new_matrix[i][j]=0;
              
      //将边初始化到vector中，并将边从小到大排序 
      for (k=0,i=0;i<n;i++)
          for (j=i+1;j<n;j++)
              if (matrix[i][j]>0){
                 temp.pre_ver=i;
                 temp.next_ver=j;
                 temp.value=matrix[i][j];
                 edge.push_back(temp);
                 k++;
              }
      for (i=1;i<edge.size();i++)
          for (j=1;j<edge.size();j++)
              if (edge[j].value< edge[j-1].value){
                 temp=edge[j-1];
                 edge[j-1]=edge[j];
                 edge[j]=temp;
              } 
               
      for (i=0,j=1;j<n;i++){//i是控制vector的指示变量，j是已经连接的边的多少，达到n-1条的时候就退出 
          //添加边到顶点图中
          new_matrix[edge[i].pre_ver][edge[i].next_ver]=edge[i].value;
          //检查是否产生环路，若产生则撤销添加
          int *tm[n]; 
          for (int t=0;t<n;t++)
              tm[t]=new_matrix[t]; 
          if ( isCircuit_by_matrix(n,tm) ){
             new_matrix[edge[i].pre_ver][edge[i].next_ver]=0;
          }
          else
              j++;
       }  

       //调用transform，将用邻接矩阵表示的生成树转换为用邻接表表示的生成树，并且返回
       for (i=0;i<n;i++)
           for (j=i+1;j<n;j++)
               if (new_matrix[i][j]>0)
                  new_matrix[j][i]=new_matrix[i][j];          

       Vertex* tree=new Vertex[n]; 
       int *tm[n];
       for (i=0;i<n;i++)
           tm[i]=new_matrix[i];     
       Transform(tree,tm,n);     

      
       return tree;
}


bool isCircuit_by_matrix(int n,int **new_matrix)//通过邻接矩阵DFS判断是否有回路 
{
     stack<int> vstack;
     int i,j,visit,visited[n],circuit;
     for (i=0;i<n;i++) visited[i]=0;
     
     int new_mat[n][n];
     for (i=0;i<n;i++)
           for (j=i;j<n;j++){
               new_mat[i][j]=new_mat[j][i]=0;
               if (new_matrix[i][j]>0)
                  new_mat[i][j]=new_mat[j][i]=new_matrix[i][j]; 
           }
           
     for (i=0;i<n&&!visited[i];i++)   {
         vstack.push(i);  
         while (!vstack.empty()){
               do {
               visit=vstack.top();
               vstack.pop();
               } while (visited[visit]&&!vstack.empty());
               if (vstack.empty()&&visited[visit])
                  break;
                  
               visited[visit]=1;
               circuit=0;
               for (j=0;j<n;j++)
                   if (new_mat[visit][j]>0){
                      if (visited[j]==0)
                         vstack.push(j);
                      else{
                          circuit++;
                          if (circuit==2)
                             return 1;
                      }                
                   }        
         }
     }
     return 0;
}

Vertex* minTree_rP(int n,Vertex*)//求最小生成树，去边法 
{
      int i,j,k;       
      int new_matrix[n][n]; 
      value_edge temp;
      vector<value_edge>  edge;
      
      //得到一个新的邻接矩阵，值与原来完全相同       
      for (i=0;i<n;i++)
          for (j=0;j<n;j++)
              new_matrix[i][j]=matrix[i][j];
         
      //将边初始化到vector中，并将边从大到小排序 
      for (k=0,i=0;i<n;i++)
          for (j=i+1;j<n;j++)
              if (matrix[i][j]>0){
                 temp.pre_ver=i;
                 temp.next_ver=j;
                 temp.value=matrix[i][j];
                 edge.push_back(temp);
                 k++;
              }
      for (i=1;i<edge.size();i++)
          for (j=1;j<edge.size();j++)
              if (edge[j].value> edge[j-1].value){
                 temp=edge[j-1];
                 edge[j-1]=edge[j];
                 edge[j]=temp;
              }  
              
      for (i=0,j=edge.size()+1;j>n;i++){//i是控制vector的指示变量，j是已经连接的边的多少，达到n-1条的时候就退出 
          //将该边从原图中去除出去 
          temp.value=new_matrix[edge[i].pre_ver][edge[i].next_ver];
          new_matrix[edge[i].pre_ver][edge[i].next_ver]=0;
          new_matrix[edge[i].next_ver][edge[i].pre_ver]=0;
          //检查是否连通，若不连通则撤销去除 
          int *tm[n]; 
          Vertex ver[n];
          for (int t=0;t<n;t++)
              tm[t]=new_matrix[t];          
          Transform(ver,tm,n);
          
          if ( !isConnected(n,ver) ){
             new_matrix[edge[i].pre_ver][edge[i].next_ver]=temp.value;
             new_matrix[edge[i].next_ver][edge[i].pre_ver]=temp.value;
          }
          else
              j--;
       }  
       
       //调用transform，将用邻接矩阵表示的生成树转换为用邻接表表示的生成树，并且返回    
         Vertex* tree=new Vertex[n]; 
         int *tm[n];
         for (i=0;i<n;i++)
             tm[i]=new_matrix[i];     
         Transform(tree,tm,n);  

         return tree;  
} 
int isConnected(int n,Vertex *vertex)
{
    if  (DFS(n,vertex,2))
        return true;
    else
        return false;
}
 
void print_to_matrix(int n,Vertex* vertex)
{
     cout<<"必须为无向简单图,否则将出现预期之外的结果,以下是邻接矩阵输出"<<endl;
     int i,a,b;
     int new_matrix[n][n];
     for (a=0;a<n;a++)
         for (b=0;b<n;b++)
             new_matrix[a][b]=0;
         
     Edge *here;
     for (i=0;i<n;i++) 
         for (here=vertex[i].edge;here;here=here->next_edge){
               new_matrix[i][here->next_ver->num]=here->value;
               new_matrix[here->next_ver->num][i]=here->value;
         }  
     for (a=0;a<n;a++){
         for (b=0;b<n;b++)
             cout<<new_matrix[a][b]<<" ";
         cout<<endl;
     }
}

<!--EndFragment-->