데이터 구조 실험 4 도 에 관 한 조작

실험 4 도 에 관 한 조작
목적 요구:
  1. 그림 의 저장 사상 과 저장 실현 을 파악 한다.
  2. 그림 의 깊이, 넓이 를 파악 하여 알고리즘 사상 과 절 차 를 우선 적 으로 옮 겨 다 닌 다.
  3. 그림 에서 흔히 볼 수 있 는 응용 알고리즘 의 사상 과 절차 실현 을 파악 한다.
실험 내용:
    1. 키보드 가 데 이 터 를 입력 하고 그림 에 대한 인접 표를 만 듭 니 다.
    2. 이 인접 표를 출력 합 니 다.
  *3. 그림 이 없 는 십자 링크 를 만 듭 니 다.
   4. 그림 의 인접 표를 바탕 으로 각 정점 의 도 를 계산 하고 출력 한다.
   5. 그림 에 대한 인접 표를 바탕 으로 토폴로지 정렬 순 서 를 출력 합 니 다.
  *6. 인접 행렬 로 방향 도 를 저장 하고 출력 단일 원점 에서 다른 정점 까지 의 가장 짧 은 경 로 를 저장 합 니 다.
   7. 인접 표 저장 소 를 이용 하여 무 방향 그림 의 깊이 를 우선 시 하고 재 귀적 으로 옮 겨 다 니 지 않 습 니 다.
   8. 인접 표 저장 소 를 이용 하여 무방 향도 의 넓이 를 우선적으로 옮 겨 다 닌 다.
  *9. 인접 행렬 저장 소 를 이용 하여 무방 향도 의 최소 생 성 트 리 를 구현 하 는 PRIM 알고리즘.
  *10. 그림 의 임의의 두 정점 사이 에 경로 가 있 는 지 판단 하고 출력 경로 의 정점 서열 이 있 으 면 판단 한다.
    11. 주 함수 에서 간단 한 메뉴 를 설계 하여 상기 알고리즘 을 각각 디 버 깅 합 니 다.
  *12. 종합 훈련: 컴퓨터 학과 의 교육 계획 을 설계 하기 위해 4 학년, 학년 마다 2 학기, 50 개의 과정 을 개설 하고 매 학기 에 개설 하 는 과정 문 수 는 최대한 균형 을 이 루 며 과정의 배정 은 반드시 선행 관 계 를 만족 시 켜 야 한다.
코드 구현:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define Maxsize 200

using namespace std;

int indegree[Maxsize],outdegree[Maxsize];

typedef char InfoType;///         
typedef char VertexType; ///        
typedef struct ArcNode ///   
{
    int adjvex; ///       
    struct ArcNode *nextarc;///            
    InfoType *info;///    
} ArcNode;
typedef struct VNode ///   
{
    VertexType data;
    ArcNode *firstarc;
} VNode,AdjList[Maxsize];
typedef struct ///   
{
    AdjList vertices;
    int vexnum,arcnum;///           
    int kind; ///kind==0     ，kind==1     
} ALGraph;

int visited[Maxsize];

void Create(ALGraph &G)
{
    char ch1,ch2;
    int k1,k2;
    printf("Please Input the Vexnum & Arcnum:
");
    scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("Please Input the Vexnums:
");
    for(int i=1; i<=G.vexnum; i++) ///       1   
    {
        scanf(" %c",&G.vertices[i].data);
        G.vertices[i].firstarc=NULL;
    }
    printf("Please Input the Arcnums:
");
    for(int i=1; i<=G.arcnum; i++)
    {
        scanf(" %c %c",&ch1,&ch2);
        for(int p=1; p<=G.arcnum; p++)
        {
            if(G.vertices[p].data==ch1)
            {
                k1=p;
                break;
            }
        }
        for(int p=1; p<=G.arcnum; p++)
        {
            if(G.vertices[p].data==ch2)
            {
                k2=p;
                break;
            }
        }
        ArcNode *pp;///             ,  ，    
        pp=(ArcNode*)malloc(sizeof(ArcNode));
        pp->adjvex=k2;
        pp->nextarc=G.vertices[k1].firstarc;
        G.vertices[k1].firstarc=pp;
    }
}

void Dfs(ALGraph G,VertexType x)///  ,      x    
{
    //ALGraph G=GG;
    int k1;
    for(int i=1; i<=G.vexnum; i++)
    {
        if(G.vertices[i].data==x)
        {
            k1=i;
            break;
        }
    }
    printf("%c ",G.vertices[k1].data);
    visited[k1]=1;
    ArcNode *p;
    p=G.vertices[k1].firstarc;
    while(p)///            
    {
        if(visited[p->adjvex]==0) ///             
        {
            Dfs(G,G.vertices[p->adjvex].data); ///                    
        }
        p=p->nextarc;///    ，             ，  p    
    }
}

void Bfs(ALGraph G,VertexType x)///           G
{
    struct
    {
        ArcNode *Q[Maxsize];
        int front,rear;
    } QQ; ///             
    ArcNode *p;
    QQ.front=QQ.rear=0;///     
    int k1;
    for(int i=1; i<=G.vexnum; i++)
    {
        if(G.vertices[i].data==x) ///           x  ，     k1
        {
            k1=i;
            break;
        }
    }
    visited[k1]=1;
    printf("%c ",G.vertices[k1].data);
    QQ.rear=(QQ.rear+1)%Maxsize;
    QQ.Q[QQ.rear]=G.vertices[k1].firstarc;
    while(QQ.rear!=QQ.front)
    {
        QQ.front=(QQ.front+1)%Maxsize;
        p=QQ.Q[QQ.front];
        while(p)
        {
            if(visited[p->adjvex]==0)///visited[]             ，         
            {
                visited[p->adjvex]=1;
                printf("%c ",G.vertices[p->adjvex].data);
                QQ.rear=(QQ.rear+1)%Maxsize;
                QQ.Q[QQ.rear]=G.vertices[p->adjvex].firstarc;
            }
            p=p->nextarc;
        }
    }
}

void Output(ALGraph G)
{
    for(int i=1; i<=G.vexnum; i++)
    {
        printf("%c ",G.vertices[i].data);
        ArcNode *pp;
        pp=G.vertices[i].firstarc;
        while(pp)
        {
            printf("%c ",G.vertices[pp->adjvex].data);
            pp=pp->nextarc;
        }
        printf("
");
    }
}

void Degree(ALGraph G)
{
    ArcNode *pp=NULL;
    for(int i=1; i<=G.vexnum; i++)
    {
        pp=G.vertices[i].firstarc;
        while(pp)
        {
            indegree[pp->adjvex]++;
            outdegree[i]++;
            pp=pp->nextarc;
        }
    }
}

int TopologicalSort(ALGraph G)
{
    int S[Maxsize];
    int top=0;
    for(int i=1; i<=G.vexnum; i++)
    {
        if(indegree[i]==0)
        {
            top++;
            S[top]=i;
        }
    }
    int countt=0;
    int ii=1;
    ArcNode *pp=NULL;
    while(top!=0)
    {
        ii=S[top];
        top--;
        printf("%d %c     ",ii,G.vertices[ii].data);
        countt++;
        for(pp=G.vertices[ii].firstarc; pp; pp=pp->nextarc)
        {
            int k=pp->adjvex;
            indegree[k]--;
            if(indegree[k]==0)
            {
                top++;
                S[top]=k;
            }
        }
    }
    if(countt<G.vexnum)
        return -1;
    else return 1;
}

int main()
{
    ALGraph G;
    char chx;
    Create(G);
    printf("The Adjacency List is:
");
    Output(G);
    memset(indegree,0,sizeof(indegree));
    memset(outdegree,0,sizeof(outdegree));
    Degree(G);
    cout<<"The List of Indegree:"<<endl;
    for(int i=1; i<=G.vexnum; i++)
    {
        printf("%d ",indegree[i]);
    }
    cout<<endl;
    cout<<"The List of Outdegree:"<<endl;
    for(int i=1; i<=G.vexnum; i++)
    {
        printf("%d ",outdegree[i]);
    }
    cout<<endl;

    int flag=0;
    printf("The List of Topological are:
");
    flag=TopologicalSort(G);
    printf("
");
    if(flag==-1)
    {
        printf("Can not TopologicalSort!
");
    }
    else
    {
        printf("Topo Over!
");
    }

    memset(visited,0,sizeof(visited));
    printf("Please Input the Start Data of the DFS:
");
    while(scanf(" %c",&chx)!=EOF)
    {
        if(chx=='0') break;///        '0' ，         
        printf("The List of Dfs :
");
        Dfs(G,chx);
        cout<<endl;
        memset(visited,0,sizeof(visited));
    }
    cout<<"DFS OVER!"<<endl;
    memset(visited,0,sizeof(visited));
    printf("Please Input the Start Data of the BFS:
");
    while(scanf(" %c",&chx)!=EOF)
    {
        if(chx=='0') break;///        '0' ，         
        printf("The List of Bfs :
");
        Bfs(G,chx);
        cout<<endl;
        memset(visited,0,sizeof(visited));
    }
    cout<<"BFS OVER!"<<endl;
    return 0;
}

///*    
4 4
A B C D
A B
A D
B C
D B
*///