데이터 구조 (15): 그림 깊이 우선 옮 겨 다 니 기 (DFS)

/*-----------------------------------------------*/
/*      DFS */
//        (14)           
#include <iostream>
using namespace std;
typedef char VertexType;
typedef int EdgeType;
const int MAXVEX = 100;
const int INFINITY = 65535;

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
} MGraph;

void CreateMGraph(MGraph &G)
{
    int i,j,k,w;
    cout<<"        ：";
    cin>>G.numVertexes>>G.numEdges;

    cout<<"      : "<<endl;
    for(i=0;i<G.numVertexes;i++)
        cin>>G.vexs[i];

    for(i=0;i<G.numVertexes;i++)
        for(j=0;j<G.numVertexes;j++)
            G.arc[i][j] = INFINITY;

    for(k=0;k<G.numEdges;k++)
    {
        cout<<"   (vi,vj)    i,  j  w:"<<endl;
        cin>>i>>j>>w; 

        G.arc[i][j] = w;
        G.arc[j][i] = G.arc[i][j];
    }
}
/*-----------------------------------------------*/
// DFS
bool visit[MAXVEX];         //              
void DFS(MGraph G, int i)   // DFS   
{
    int j;
    visit[i] = true;                        //             
    cout<<G.vexs[i]<<ends;                  //       (       ) 

    for(j=0;j<G.numVertexes;j++)            //                 
        if(G.arc[i][j] == 1 && !visit[j])
            DFS(G,j);                       //    
}
// DFSTraverse 
void DFSTraverse(MGraph G)
{
    int i;
    for(i=0;i<G.numVertexes;i++)            //              
        visit[i] = false;

    for(i=0;i<G.numVertexes;i++)            //               DFS 
        if(!visit[i])
            DFS(G,i);
}

int main()
{
    MGraph G;
    CreateMGraph(G);
    DFSTraverse(G);

    return 0;
}

/*-----------------------------------------------*/
/*     DFS */
//        (14)          
#include <iostream>
using namespace std;
const int MAXVEX = 100;

typedef char VertexType;
typedef int EdgeType;

typedef struct EdgeNode
{
    int adjvex;
    EdgeType weight;
    struct EdgeNode *next;  
} EdgeNode;

typedef struct VertexNode
{
    VertexType data;
    EdgeNode *firstedge;
} VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;
} GraphAdjList;

void CreateALGraph(GraphAdjList &G)
{
    int i,j,k,w;
    EdgeNode *e;
    cout<<"        ：";
    cin>>G.numVertexes>>G.numEdges;

    cout<<"        ："<<endl;
    for(i=0;i<G.numVertexes;i++)
    {
        cin>>G.adjList[i].data;
        G.adjList[i].firstedge = NULL;
    }

    for(k=0;k<G.numEdges;k++)
    {
        cout<<"   (vi,vj)      ："<<endl;
        cin>>i>>j>>w;

        e = new EdgeNode;
        e->adjvex = j;
        e->weight = w;
        e->next = G.adjList[i].firstedge;
        G.adjList[i].firstedge = e;

        e->adjvex = i;
        e->weight = w;
        e->next = G.adjList[j].firstedge;
        G.adjList[j].firstedge = e;
    }
}
/*-----------------------------------------------*/

// DFS
bool visit[MAXVEX];                         //             
void DFS(GraphAdjList GL, int i)            // DFS  
{
    EdgeNode *p;
    visit[i] = true;                        //            
    cout<<GL.adjList[i].data<<ends;         //       (       ) 

    p = GL.adjList[i].firstedge;            //                 
    while(p)
    {
        if(!visit[p->adjvex])               //                    
            DFS(GL,p->adjvex);
        p = p->next;                        //            
    }
}
void DFSTraverse(GraphAdjList GL)
{
    int i;
    for(i=0;i<GL.numVertexes;i++)            //              
        visit[i] = false;       

    for(i=0;i<GL.numVertexes;i++)           //               DFS 
        if(!visit[i])
            DFS(GL,i);
}

int main()
{
    GraphAdjList G;
    CreateALGraph(G);
    DFSTraverse(G);

    return 0;
}