[자료구조] 인접리스트 Python C++

인접리스트

인접한 정점에 대한 정보를 리스트 표현

정점이 인접한 정점의 개수에 따라 가변적으로 변할 수 있음 O(deg(V)) 즉, 정점의 차수에 따라 결정됨

 

lists = []
m, e = map(int, input().strip().split())
 
for i in range(m):
    temp = []
    for j in range(m):
        temp.append(0)
    lists.append(temp)
 
for i in range(e):
    a, b = map(int, input().strip().split())
    lists[a - 1][b - 1] = 1
    lists[b - 1][a - 1] = 1
#
for i in range(m):
    for j in range(m):
        print(lists[i][j], end=" ")
    print("")
 
print("\n\n\n인접리스트 O(deg(V))")  # 정점이 인접하는 수에 따라 시간복잡도가 달라질 수 있음
for i in range(len(lists)):         # 인접하는 정점이 가변적인 길이의 리스트로 사용이 가능함.
    print(i+1, ": ", end=" ")       # 현재는 인접하는 정점의 번호를 바로 출력했지만 리스트 append로도 활용 가능함
    for j in range(len(lists[i])):
        if lists[i][j] == 1:
            print(j+1, end=" ")
    print("")

 

 

#include<iostream>
#include<vector>
#include<cstdio>
 
using namespace std;
const int MAX = 10;
 
int main(){
 
    vector <int> myGraph[MAX];
 
    int n, e;
    scanf("%d %d", &n, &e);
 
    for (int i = 0; i < e; i++){
        int a, b;
        scanf("%d %d", &a, &b);
 
        myGraph[a].push_back(b);
        myGraph[b].push_back(a);
    }
 
    for (int i = 1; i <=n; i++){
        printf("%d (%d) :", i + 1, myGraph[i].size());
        for (int j = 0; j < myGraph[i].size(); j++)
            printf("%d ", myGraph[i][j]);
 
        printf("\n");
    }
 
    return 0;
}