【锐格】数据结构-实验-图

7039

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX_NUM=100;

int w;
int mark[MAX_NUM];

typedef int EdgeData;

typedef struct Node
{
    int dest;
    EdgeData weight;//边权
    struct Node *next;//next route
}EdgeNode;

typedef struct
{
    char data;
    EdgeNode *point;
}VerNode;

typedef struct
{
    VerNode VList[MAX_NUM];
    int n,e;//图中顶点个数与边数
}Graph;

void createGraph(Graph &G)
{
    int tail, head;
    cin>>G.n>>G.e;
    for(int i=1;i<=G.n;i++)
    {
        cin>>G.VList[i].data;
        G.VList[i].point=NULL;
    }
    for(int i=1;i<=G.e;i++)
    {
        cin>>tail>>head;
        EdgeNode *p=new EdgeNode ;
        p->dest=head;
        p->next=G.VList[tail].point;
        G.VList[tail].point=p;
    }
}

void showGraph(Graph G)
{
    for(int i=1;i<=G.n;i++)
    {
        cout<<G.VList[i].data<<":";
        EdgeNode *p=G.VList[i].point;
        while(p!=NULL)
        {
            cout<<p->dest<<" ";
            p=p->next;
        }
        cout<<endl;
    }
}

void DFS(Graph G,int v)
{
    cout<<v<<" ";
    mark[v]=1;
    EdgeNode *p=G.VList[v].point;
    while(p!=NULL)
    {
        w=p->dest;
        if(!mark[w]) DFS(G, w);
        p=p->next;
    }
}

int main()
{
    Graph G;
    createGraph(G);
    showGraph(G);
    DFS(G, 1);
    return 0;
}

7040

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int MAX_NUM=110;

int in[MAX_NUM],out[MAX_NUM];

typedef struct VerNode{
    int adjvex;
    struct VerNode * nextarc;
}VerNode;

typedef struct VNode{
    int data;
    VerNode *firstarc;
}VNode,AdjList[MAX_NUM];

typedef struct{
    AdjList verlist;
    int vexnum,arcnum;
}Graph;

void createGraph(Graph &G){
    cin>>G.vexnum>>G.arcnum;
    for(int i=1;i<=G.vexnum;i++){
        cin>>G.verlist[i].data;
        G.verlist[i].firstarc=NULL;
    }
    for(int i=1;i<=G.arcnum;i++){
        int x,y;cin>>x>>y;

        VerNode * p1= new VerNode;

        p1->adjvex=y;
        p1->nextarc=G.verlist[x].firstarc;
        G.verlist[x].firstarc=p1;
    }
}

void GetVec(Graph G){
    for(int i=1;i<=G.vexnum;i++){
        VerNode* p=G.verlist[i].firstarc;
        while(p!=NULL){
            out[i]++;
            in[p->adjvex]++;
            p=p->nextarc;
        }
    }
}


int main(){
    Graph G;
    createGraph(G);
    GetVec(G);
    for(int i=1;i<=G.vexnum;i++){
        cout<<i<<":"<<in[i]<<" "<<out[i]<<" "<<in[i]+out[i]<<endl;
    }
    return 0;
}