그래프와 그 표현 TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

그래프 객체 간의 관계 또는 연결을 나타내는 추상 데이터 유형입니다 (예 : 도시가 거친 도로로 연결됨). 그래프와 그 표현에서 기본적으로 관계는 정점 (노드)으로 모서리와 객체로 표시됩니다. 그래프는 유한 한 정점 및 간선 세트로 구성됩니다. 그래프는 비선형 데이터 구조입니다. 예를 들어 보겠습니다. 페이 스북, 우리는 친구들이 Facebook에서 양방향 관계에 있다는 것을 알고 있습니다. A가 B의 친구이면 B도 A의 친구입니다. 각 친구가 나머지 친구의 친구 인 친구 그룹은 Undirected Graph의 예입니다.

핀

차례

그림 1 : 정점 = {1,2,3,4,5,6} 및 가장자리 = {12,14,23,35,45,56}로 구성된 무 방향 그래프

노드 / 정점 : 관계가 가장자리로 정의되는 엔티티와 같습니다.
가장자리 : 노드 / 정점 간의 관계를 나타내는 구성 요소와 같습니다.

그래프 유형

무 방향 그래프 : 본질적으로 양방향 인 모서리로 서로 연결된 객체 (노드 / 정점) 집합입니다 (그림 1 참조).
유향 그래프 : 모든 가장자리가 한 노드에서 다른 노드로 향하는 가장자리로 함께 연결된 개체 (노드 / 정점) 집합입니다 (그림 2 참조).
가중 그래프 : 그래프의 각 가장자리에는 가중치라는 관련 숫자 값이있는 가장자리로 서로 연결된 개체 (노드 / 정점) 집합입니다 (그림 3 참조).

핀 핀

그림 2 : 유 방향 그래프 그림 3 : 가중 그래프

그래프 구현

엣지의 밀도와 수행하려는 작업 유형에 따라 그래프를 최적으로 표현하는 여러 가지 방법이 있습니다.

인접 매트릭스

V * V 크기의 연결 행렬입니다. 여기서 V는 다음 항목 만 포함하는 총 정점 수입니다. 0,1. i가 j에 인접하고 1 <= i, j <= V이면 값은 1이 아니면 0입니다. 인접 행렬의 몇 가지 예를 살펴 보겠습니다.

핀 핀 핀

무 방향 그래프 인접 행렬 방향 그래프 인접 행렬 가중치 그래프 인접 행렬

(그림 1 참조) (그림 2 참조) (그림 3 참조)

알림: 그래프에 자체 루프가 없으면 i = j 인 모든 셀은 0이어야합니다 (위의 행렬 참조).

/*C++ Implementation of adjacency matrix for undirected graph*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    cin>>nodes>>edges;
    int adj_matrix[nodes+1][nodes+1];
    memset(adj_matrix,0,sizeof(adj_matrix));
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        adj_matrix[x][y]=1;
        adj_matrix[y][x]=1;// for directed graph we don't write for y->x;
    }
    /*Print the adjacency matrix*/
    for(int i=1;i<=nodes;i++)
    {
        for(int j=1;j<=nodes;j++)
        {
            cout<<adj_matrix[i][j]<<" ";
        }
        cout<<"\n";
    }
  return 0;
}
/* TIME COMPLEXITY: O(N*N) WHERE N IS THE NUMBER OF NODES IN GRAPH */

인접 목록

N (총 노드) 목록을 포함하는 연결된 표현으로, 각 목록은 그래프에서 정점의 인접 집합을 설명합니다. 목록의 크기 (모든 정점에 대한)는 해당 정점의 정도와 같습니다.

유향 그래프 인접 목록 (그림 2 참조)

/*C++ Implementation of adjacency list for directed graph using STL*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y); /* add v[y].push_back(x) also for undirected graph beacuse edge is bidirectional in nature*/
    }
    /*Print the adjacency matrix*/
    for(int i=1;i<=nodes;i++)
    {
        int degree=v[i].size();
        for(int j=0;j<degree;j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }
  return 0;
}
/* TIME COMPLEXITY: O(V+E) WHERE V IS THE NUMBER OF VERTICES/NODES IN GRAPH AND E IS THE NUMBER OF EDGES */

참고

레퍼런스 1

Twitter Facebook 링크드인 버퍼 레딧 텀블러