데이터 구조 (그림) - 인접 행렬

그림 의 저장 구조:
비교적 흔히 볼 수 있 는 두 가지 그림 의 저장 구조:

인접 행렬 표현법 (수조 표현법) 만약 에 그림 G 가 n 개의 정점 을 가 진 무 권 도 라면 G 의 인접 행렬 은 다음 과 같은 성질 을 가 진 n 이다.×행렬 A: A [i, j] = {1 i f (v i, v j) o r < v i, v i, v j > < v j > 다음 에 있 는 V 0 o t h h e r s A [i, j] = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n 개의 정점 을 가 진 네트워크 는 다음 과 같은 성질 을 가 진 n 이다.×행렬 A: A [i, j] = {w i j j i i f (v i, v j) 의 행렬 A: A: [i, j] = {\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ vj > 8712 ° Vothers

인접 표 인접 표 저장 방법 은 순차 적 분배 와 체인 분배 가 결 합 된 저장 방법 입 니 다. 인접 표 에는 그림 의 각 정점 에 하나의 단일 체인 표를 만 들 고, i 번 째 단일 체인 표 의 결점 은 정점 v i v {i} vi 의 변 에 의존 하 는 것 을 표시 합 니 다. 각 단일 체인 표 에는 하나의 표 두 결점 이 첨부 되 어 있 습 니 다. 표 결점 과 표 두 결점 의 구 조 는 다음 과 같 습 니 다. 표 두 결점:

data
firstarc
정점 의 이름 이나 다른 정 보 를 저장 합 니 다.
링크 의 첫 번 째 노드 를 가리킨다.
표 노드:
adjvex
nextarc
info
정점 과 인접 한 점 이 그림 에 있 는 위 치 를 표시 합 니 다.
다음 변 이나 호의 결점 을 가리키다
가중치 등 변 이나 호 와 관련 된 정 보 를 저장 합 니 다.
인접 행렬
다음은 인접 행렬 의 구조 정의 이다.

//    
typedef enum{DG, DN, UDG, UDN} GraphKind;   //   、   、   、   

typedef struct ArcCell{
    VRType adj;         //    ，  0,1
    InfoType *info;     //          
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct 
{
    VertexType vexs[MAX_VERTEX_NUM];        //    
    AdjMatrix arcs;                         //    
    int vexnum, arcnum;                     //      
    GraphKind kind;                         //   
}MGraph;

다음은 인접 행렬 을 이용 한 기본 기능 입 니 다. 그림 만 들 기: 두 가지 방법, 첫 번 째 는 텍스트 읽 기, 두 번 째 는 키보드 입력 입 니 다. 텍스트 에서 첫 번 째 줄 은 결점 개수, 두 번 째 줄 은 결점 명칭, 세 번 째 줄 과 그 아래 는 결점 과 결점 간 의 정보 (가중치) 입 니 다. 두 결점 전에 연락 이 없 으 면 0 입 니 다.

void createGraph_txt(MGraph &G)
{
   ifstream fin("city.txt");	//    
    fin>>G.vexnum;
    for(int i=0;i<G.vexnum;i++){
        fin>>G.vexs[i];
    }
    int edge = 0;
    for(int i =0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            double info;
            fin>>info;
            if(info>0){
                G.arcs[i][j].adj = info;
                edge++;
            }
            else{
                G.arcs[i][j].adj = 0;
            }
        }
    }
    G.arcnum = edge;
}

void createGraph_cin(MGraph &G)
{
    cout<<"       ：";
    int city_num;
    cin>>city_num;
    G.vexnum = city_num;
    cout<<"       ：";
    for(int i=0;i<G.vexnum;i++) cin>>G.vexs[i];
    
    int edge = 0;
    cout<<"            ，         ，   ０"<<endl;
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            double info;
            cin>>info;
            if(info>0){
                G.arcs[i][j].adj = info;
                edge ++;
            }
            else{
                G.arcs[i][j].adj = 0;
            }
        }
    }
    G.arcnum = edge;
}

현재 그림 의 노드 갯 수, 방향 갯 수 가 져 오기

int getNumVertices(MGraph &G)
{
    return G.vexnum;
}

int getNumEdges(MGraph &G)
{
    return G.arcnum;
}

어떤 정점 이 존재 하 는 지 판단 하 다.

bool validVertex(MGraph &G, string v)
{
    int has = 0;
    for(int i=0;i<G.vexnum;i++){
        if(!v.compare(G.vexs[i])){
            has = 1;
            cout<<v<<"    "<<endl;
            break;
        }
    }
    if(has==1) return true;
    else {
        cout<<v<<"     "<<endl;
        return false;
    }
}

두 정점 사이 에 두 개의 정점 이 그림 에 있 는 위 치 를 각각 가 져 올 수 있 는 지 판단 한 다음 에 대응 하 는 < v i, v j > < v {i}, v {j} > < vi, vj > 의 정 보 를 봅 니 다. 0 이 라면 방향 이 존재 하지 않 습 니 다. 여기 uv 는 입력 한 두 정점 이 모두 존재 하 는 지 판단 하 는 데 사 용 됩 니 다. 하나 가 존재 할 때 + 1 을 추가 합 니 다.

bool hasEdge(MGraph &G, string u, string v)
{
    int u_index = -1, v_index = -1;
    int uv = 0;
    for(int i=0;i<G.vexnum;i++){
        if(!u.compare(G.vexs[i])){
            u_index = i;
            uv ++;
            if(uv==2) break;
        }
        else if(!v.compare(G.vexs[i])){
            v_index = i;
            uv ++;
            if(uv==2) break;
        }
    }
    if(G.arcs[u_index][v_index].adj==0||uv!=2){
        cout<<"   "<<u<<" "<<v<<"    "<<endl;
        return false;
    }
    else{
        cout<<"  "<<u<<" "<<v<<"    "<<endl;
        cout<<"   ："<<G.arcs[u_index][v_index].adj<<endl;
        return true;
    }
}

정점 을 추가 할 지 여 부 를 먼저 판단 하고 존재 하면 종료 합 니 다. 존재 하지 않 으 면 추가 합 니 다. 추가 후 나머지 정점 과 그 사이 의 관 계 는 기본적으로 0 입 니 다.

void addVertex(MGraph &G, string u)
{
    if(validVertex(G, u)){
        cout<<"      ，    "<<endl;
        return ;
    }
    else{
        G.vexnum++;
        G.vexs[G.vexnum-1] = u;
        for(int i=0;i<G.vexnum-1;i++) G.arcs[i][G.vexnum].adj = 0;
        for(int i=0;i<G.vexnum;i++) G.arcs[G.vexnum-1][i].adj = 0;
    }
}

사 이 드 추가

void addEdge(MGraph &G, string u, string v, int w)
{
    if(hasEdge(G, u, v)){
        cout<<"       ，    "<<endl;
        return ;
    }
    else{
        int u_index = -1, v_index = -1;
        for(int i=0;i<G.vexnum;i++){
            if(!u.compare(G.vexs[i])){
                u_index = i;
                uv ++;
                if(uv==2) break;
            }
            else if(!v.compare(G.vexs[i])){
                v_index = i;
                uv ++;
                if(uv==2) break;
            }
        }
        G.arcs[u_index][v_index].adj = w;
    }
}

한 쪽 을 삭제 하고 해당 하 는 쪽 정 보 를 0 으로 설정 합 니 다.

void removeEdge(MGraph &G, string u, string v)
{
    int u_index = -1, v_index = -1;
    int uv = 0;
    for(int i=0;i<G.vexnum;i++){
        if(!u.compare(G.vexs[i])){
            u_index = i;
            uv ++;
            if(uv==2) break;
        }
        else if(!v.compare(G.vexs[i])){
            v_index = i;
            uv ++;
            if(uv==2) break;
        }
    }
    if(uv!=2||G.arcs[u_index][v_index].adj==0){
        return ;
    }
    else{
        G.arcs[u_index][v_index].adj = 0;
    }
}

사 이 드 정보 보이 기

void drawGraph(MGraph &G)
{
    for(int i=0;i<G.vexnum;i++){
        cout<<G.vexs[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            cout<<G.arcs[i][j].adj<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}