그래프 표현

그래프를 표현한다는 것은 정점과 모서리를 프로그램에 저장하는 것입니다. 그래프를 저장하는 데이터 구조는 배열 또는 목록입니다. 그래프를 처리하고 조작하는 프로그램을 작성하려면 그래프에 대한 데이터를 컴퓨터에 저장하거나 표현해야 합니다.

정점 표현

정점은 배열이나 목록에 저장될 수 있습니다. 예를 들어, 다음 배열을 사용하여 아래 그림의 그래프에 모든 도시 이름을 저장할 수 있습니다.

String[] vertices = {"시애틀", "샌프란시스코", "로스앤젤레스", "덴버", "캔자스시티", "시카고", "보스턴", "뉴욕", "애틀랜타", " 마이애미', '댈러스', '휴스턴'};

정점은 모든 유형의 객체일 수 있습니다. 예를 들어 도시를 이름, 인구, 시장 등의 정보가 포함된 개체로 간주할 수 있습니다. 따라서 정점을 다음과 같이 정의할 수 있습니다:

도시 city0 = new City("시애틀", 608660, "Mike McGinn");
...
City city11 = new City("Houston", 2099451, "Annise Parker");
도시[] 정점 = {city0, city1, ... , city11};

공공 수업 도시 {
개인 문자열 cityName;
개인 정수 인구;
개인 문자열 시장;

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

n개의 정점에 대한 그래프의 경우 자연수 0, 1, 2, ..., n - 1을 사용하여 정점에 편리하게 레이블을 지정할 수 있습니다. 따라서 vertices[0]은 "시애틀"을 나타내고, vertices[1]은 "샌프란시스코"를 나타냅니다. 아래 그림과 같습니다.

정점은 이름이나 색인 중 더 편리한 방법으로 참조할 수 있습니다. 분명히 프로그램의 인덱스를 통해 정점에 접근하는 것은 쉽습니다.

모서리 표현: 모서리 배열

가장자리는 2차원 배열을 사용하여 표현할 수 있습니다. 예를 들어, 다음 배열을 사용하여 그림 28.1의 그래프에 있는 모든 간선을 저장할 수 있습니다.

int[][] 가장자리 = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

이 표현을 에지 어레이라고 합니다. 아래 그림 (a)의 꼭지점과 모서리는 다음과 같이 표현할 수 있습니다.

String[] names = {"피터", "제인", "마크", "신디", "웬디"};
int[][] 가장자리 = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

모서리 표현: 모서리 객체

가장자리를 표현하는 또 다른 방법은 가장자리를 객체로 정의하고 java.util.ArrayList에 가장자리를 저장하는 것입니다. Edge 클래스는 다음과 같이 정의할 수 있습니다.

공개 클래스 Edge {
그렇죠;
int v;
공개 Edge(int u, int v) {
this.u = u;
this.v = v;
}
공개 부울 같음(객체 o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
}
}

예를 들어 다음 목록을 사용하여 아래 그림의 그래프에 있는 모든 간선을 저장할 수 있습니다.

java.util.ArrayList 목록 = 새로운 java.util.ArrayList<>();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

Edge 객체를 ArrayList에 저장하는 것은 가장자리를 미리 모르는 경우에 유용합니다.

이전 섹션(가장자리 표현: Edge Array)과 이 섹션 앞부분에서 가장자리 배열 또는 Edge 객체를 사용하여 가장자리를 표현하는 것은 입력에는 직관적일 수 있지만 효율적이지 않습니다. 내부 처리. 다음 두 섹션에서는 인접 행렬과 인접 목록을 사용한 그래프 표현을 소개합니다. 이 두 가지 데이터 구조는 그래프 처리에 효율적입니다.

간선 표현: 인접 행렬

그래프에 n개의 정점이 있다고 가정합니다. adjacencyMatrix와 같은 2차원 n * n 행렬을 사용하여 가장자리를 나타낼 수 있습니다. 배열의 각 요소는 0 또는 1입니다. adjacencyMatrix[i][j]는 정점 i에서 정점 j까지의 간선이 있는 경우 1입니다. 그렇지 않으면 adjacencyMatrix[i][j]는 0입니다. 그래프의 방향이 지정되지 않은 경우 adjacencyMatrix[i][j]는 adjacencyMatrix[j][i]와 동일하므로 행렬은 대칭입니다. 예를 들어, 아래 그림 그래프의 모서리는 인접 행렬을 사용하여 다음과 같이 표현할 수 있습니다.

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // 시애틀
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // 샌프란시스코
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // 로스앤젤레스
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, //덴버
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // 캔자스시티
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // 시카고
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // 보스턴
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // 뉴욕
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // 애틀랜타
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // 마이애미
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // 달라스
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // 휴스턴
};

무방향 그래프의 경우 행렬이 대칭이므로 저장 공간을 절약하기 위해 비정형 배열을 사용할 수 있습니다.

아래 그림 (a)의 유방향 그래프에 대한 인접 행렬은 다음과 같이 나타낼 수 있습니다.

int[][] a = {{0, 0, 1, 0, 0}, // 피터
{0, 0, 1, 0, 0}, // 제인
{0, 0, 0, 0, 1}, // 표시
{0, 0, 0, 0, 1}, // 신디
{0, 0, 0, 0, 0} //웬디
};

간선 표현: 인접 목록

인접 정점 목록이나 인접 가장자리 목록을 사용하여 가장자리를 나타낼 수 있습니다. 정점 i에 대한 인접 정점 목록에는 i에 인접한 정점이 포함되고, 정점 i에 대한 인접 가장자리 목록에는 i에 인접한 가장자리가 포함됩니다. 목록의 배열을 정의할 수 있습니다.
배열에는 n개의 항목이 있고 각 항목은 목록입니다. 정점 i에 대한 인접 정점 목록에는 정점 i에서 정점 j까지의 가장자리가 있는 모든 정점 j가 포함됩니다. 예를 들어 아래 그림의 그래프에서 모서리를 나타내려면 다음과 같이 목록 배열을 만들 수 있습니다.

java.util.List[] neighbor = new java.util.List[12];

neighbors[0]는 정점 0(예: 시애틀)에 인접한 모든 정점을 포함하고, neighbors[1]은 정점 1(예: 샌프란시스코) 등은 아래 그림과 같습니다.

아래 그림의 그래프에 대한 인접 가장자리 목록을 나타내려면 다음과 같이 목록 배열을 생성할 수 있습니다.

java.util.List[] neighbor = new java.util.List[12];

neighbors[0]는 정점에 인접한 모든 가장자리를 포함합니다 0(예: 시애틀), neighbors[1]은 정점에 인접한 모든 가장자리를 포함합니다 1(예: 샌프란시스코) 등은 아래 그림과 같습니다.

인접 행렬이나 인접 목록을 사용하여 그래프를 표현할 수 있습니다. 어느 것이 더 낫습니까? 그래프가 조밀한 경우(즉, 모서리가 많은 경우) 인접 행렬을 사용하는 것이 좋습니다. 그래프가 매우 희박한 경우(예: 가장자리 수가 매우 적은 경우) 인접 행렬을 사용하면 많은 공간이 낭비되므로 인접 목록을 사용하는 것이 더 좋습니다.

인접 행렬과 인접 목록을 모두 프로그램에서 사용하여 알고리즘을 더욱 효율적으로 만들 수 있습니다. 예를 들어, 인접 행렬을 사용하여 두 정점이 연결되어 있는지 확인하는 데 O(1) 일정한 시간이 걸리고, 인접 목록을 사용하여 그래프의 모든 모서리를 인쇄하는 데 선형 시간 O(m)이 걸립니다. 여기서 m은 모서리 수입니다. .

인접 정점 목록은 비가중 그래프를 표현하는 데 더 간단합니다. 그러나 인접 간선 목록은 광범위한 그래프 애플리케이션에 더 유연합니다. 인접 모서리 목록을 사용하면 모서리에 추가 제약 조건을 쉽게 추가할 수 있습니다. 이러한 이유로 이 책에서는 그래프를 표현하기 위해 인접 간선 목록을 사용합니다.

배열, 배열 목록 또는 연결 목록을 사용하여 인접 목록을 저장할 수 있습니다. 목록은 쉽게 확장하여 새 정점을 추가할 수 있으므로 배열 대신 목록을 사용합니다. 또한 우리의 알고리즘은 목록에서 인접한 정점만 검색하면 되므로 연결 목록 대신 배열 목록을 사용할 것입니다. 우리 알고리즘에서는 배열 목록을 사용하는 것이 더 효율적입니다. 배열 목록을 사용하면 아래 그림의 인접 가장자리 목록을 다음과 같이 구성할 수 있습니다.

목록> neighbor = new ArrayList<>();
neighbor.add(new ArrayList());
neighbor.get(0).add(new Edge(0, 1));
neighbor.get(0).add(new Edge(0, 3));
neighbor.get(0).add(new Edge(0, 5));
neighbor.add(new ArrayList());
neighbor.get(1).add(new Edge(1, 0));
neighbor.get(1).add(new Edge(1, 2));
neighbor.get(1).add(new Edge(1, 3));
...
...
neighbor.get(11).add(new Edge(11, 8));
neighbor.get(11).add(new Edge(11, 9));
neighbor.get(11).add(new Edge(11, 10));

위 내용은 그래프 표현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!