그림 인접 행렬 의 c 언어 구현 graphadj_matrix.cpp

#include 
#include 
#include 
using namespace std;

#define  Vertex_MAX 15
#define  Edge_MAX 15*(15-1)
typedef int elemtype;
//typedef float elemtype;
int Vertex_n = 0;
int Edge_n = 0;

struct graph
{
    elemtype V[Vertex_MAX+1];   //  
    elemtype arcs[Vertex_MAX+1][Vertex_MAX+1];  // (i,j)
};

//     
char visited[Vertex_MAX+1] = {0};

//         
void UDcreatadj_matrix(graph& g)
{
    int i,j,k;
    //           
    printf("       ：");
    cin>>Vertex_n;
    printf("       ：");
    cin>>Edge_n;
    //      
    for (k = 1; k <= Vertex_n; k++) 
    {  
        printf("   %d   , %d   : ",Vertex_n,k);
        cin>>g.V[k];
    }
    //     
    for (i = 1; i <= Vertex_n; i ++)
    {
        for (j = 1; j <= Vertex_n; j++ )
        {
            g.arcs[i][j] = 0;
        }
    }
    //   (i,j)
    for (k = 1; k <= Edge_n; k++)    
    {
        printf("   %d  , %d  （i j）: ",Edge_n,k);
        cin>>i>>j;
        g.arcs[i][j] = 1;
        g.arcs[j][i] = 1;
    }
    //    
    for (i = 1; i <= Vertex_n; i ++)
    {
        for (j = 1; j <= Vertex_n; j++ )
        {
            printf("%d  ",g.arcs[i][j]);
        }
        printf("
");
    }
}

//      ，        ，      ，    
void UDdfs_adj_matrix(graph& g , int onevertex,int vertex_n)
{
    int j;
    cout<//         
    visited[onevertex] = 1;     //   1
    for (j = 1; j<= vertex_n; j++)
    {
        if (g.arcs[onevertex][j] == 1 && !visited[j])   //        
        {
            //cout<
            UDdfs_adj_matrix(g,j,vertex_n);
        }
    }
}

//        ，      
void UDdfs_all_adj_matrix(graph& g , int vertex_n)
{
    for (int kk = 1; kk <= vertex_n; kk ++ )
    {
        if (!visited[kk])
        {
            UDdfs_adj_matrix(g , kk , vertex_n);//           
        }

    }
}

//      ，        ，      ，    
void UDbfs_adj_matrix(graph& g , int onevertex,int vertex_n)
{
    //int Q[Vertex_MAX + 1];
    int *Q = new int[vertex_n + 1]; //Q   
    memset(Q,0,sizeof(int)*(vertex_n + 1)); 
    int f , r, j;   //f,r      ，   
    f = r = 0;
    cout<//      
    visited[onevertex] = 1; //       
    r++; 
    Q[r] = onevertex;   //   
    while(f < r)
    {
        f++;
        onevertex = Q[f];   //   
        for (j=1; j<=vertex_n; j++)
        {
            if ((g.arcs[onevertex][j] == 1) && (!visited[j]))
            {
                cout<1;
                r++;
                Q[r] = j;
            }
        }
    }
    if (Q != NULL)
    {
        delete [] Q;
        Q = NULL;
    }

}
//        ,      
void UDbfs_all_adj_matrix(graph& g , int vertex_n)
{
    for (int kk = 1; kk <= vertex_n; kk ++ )
    {
        if (!visited[kk])
        {
            UDbfs_adj_matrix(g ,kk,vertex_n);
        }

    }
}
//         
void Dcreateadj_matrix(graph& g)
{
    int i , j, k;
    //           
    printf("       ：");
    cin>>Vertex_n;
    printf("       ：");
    cin>>Edge_n;
    //      
    for (i = 1; i <= Vertex_n; i ++)
    {
        printf("   %d   , %d   : ",Vertex_n,i);
        cin>>g.V[i];
    }
    //     
    for (i = 1; i <= Vertex_n; i ++)
    {
        for (j = 1; j <= Vertex_n; j++)
        {
            g.arcs[i][j] = 0;
        }
    }
    //   
    for (k = 1; k <= Edge_n; k++)
    {
        printf("   %d  , %d  （i j）: ",Edge_n,k);
        cin>>i>>j;
        g.arcs[i][j] = 1;
    }
    //    
    for (i = 1; i <= Vertex_n; i ++)
    {
        for (j = 1; j <= Vertex_n; j++ )
        {
            printf("%d  ", g.arcs[i][j]);
        }
        printf("
");
    }
}

//          
void UDNetcreatadj_matrix(graph& g)
{
    int i,j,k;
    //  
    int w;
    //           
    printf("       ：");
    cin>>Vertex_n;
    printf("       ：");
    cin>>Edge_n;
    //      
    for (k = 1; k <= Vertex_n; k++) 
    {  
        printf("   %d   , %d   : ",Vertex_n,k);
        cin>>g.V[k];
    }
    //     
    for (i = 1; i <= Vertex_n; i ++)
    {
        for (j = 1; j <= Vertex_n; j++ )
        {
            if (i == j)
            {
                g.arcs[i][j] = 0;
            }
            else g.arcs[i][j] = 65536; //        
        }
    }
    //   (i,j)   
    for (k = 1; k <= Edge_n; k++)    
    {
        printf("   %d  , %d     (i j w): ",Edge_n,k);
        cin>>i>>j>>w;
        g.arcs[i][j] = w;
        g.arcs[j][i] = w;
    }
    //    
    for (i = 1; i <= Vertex_n; i ++)
    {
        for (j = 1; j <= Vertex_n; j++ )
        {
            printf("%d      ",g.arcs[i][j]);
        }
        printf("
");
    }
}



int main()
{

    graph g;
    UDcreatadj_matrix(g);
    //Dcreateadj_matrix(g);
    //UDNetcreatadj_matrix(g);
    UDdfs_adj_matrix(g, 1,Vertex_n);
    //UDbfs_adj_matrix(g,1,Vertex_n);
    system("pause");
    return 0;
}