숙제 : 그래프 생성

Question

이산 이벤트 시뮬레이터를 시뮬레이트해야하고 30 개의 노드로 구성된 네트워크를 생성 한 다음 생성 된 그래프가 지시되었는지 확인해야합니다. 아무도 이걸 시작하는 방법에 대한 안내를 해줄 수 있습니까? 나는 이것을하기 위해 boost 라이브러리를 사용하면 안된다. 네,이 과제는 과제부터 시작해야합니다. 그냥 앞으로 나아갈 수있는 몇 가지 포인터가 필요합니다.

#define MAXNODES 30 

struct { 
int p; 
int *incoming; 
int *outgoing; 
} NODE[MAXNODES] 
//The struct defines each node and the neighbors to it. 

위 구조체 정의가 맞습니까?

Answer 1

임의의 임의의 그래프를 생성 할 수 있다고 가정합니다. 또한 그래프의 인접 행렬 표현에 익숙하다고 가정합니다.

이 경우 그래프의 표현은 adjacency matrix입니다. 이것을 표현하기 위해 2D 배열을 사용합니다.

#define MAXNODES 30 
int graph[MAXNODES][MAXNODES]; 

이 그래프가 가중 또는 가중된다

그래서 그래프는 다음과 같이 정의 할 것인가? 가중치가없는 경우 행렬의 각 요소 (예 : graph[3][7])는 0 또는 1을 갖습니다. 0이면 노드 3과 7을 연결하는 가장자리가 없으며 (이 예에서) 1이면 실제로 가장자리가 있습니다.

가중치가 0이면 여전히 가장자리가 없지만 숫자 (1, 9, 234, anything)는 해당 가장자리의 무게를 나타냅니다.

루프를 사용하여 각 배열 요소의 번호를 채울 수 있습니다. 따라서 각 노드 쌍을 통과하여 무작위로 가중치를 할당하십시오 (가장자리가 없으면 0, 가장자리가있는 경우 숫자가 임의로 할당됩니다). weighted-vs-unweighted)

질문에 대답하기 위해 "directedness"를 확인하는 것이 쉽습니다. 그래프가 지정되면 그래프 [3] [7]과 그래프 [7] [3]은 같은 값을 갖게됩니다. 따라서 모든 쌍 (그래프 [i] [j] 및 그래프 [j] [i])을 검사하여 값이 동일한 지 확인할 수 있습니다. 행렬이 symmetric인지 확인하고 있습니다.

대칭이 아닌 경우 ([3] [7]은 0이지만 [7] [3]은 1) 한 방향으로 만 가장자리가 있으므로 방향이 지정됩니다. 그리고 각 쌍에 두 개의 값 ([3] [7] = 5, [7] [3] = 21)이 있으면 이동하는 방향에 따라 가중치가 변경되기 때문에 그래프가 지시됩니다.

Answer 2

먼저 'directedness'의 특정 버전을 정의해야한다고 생각합니다. 한 노드가 다른 노드를 앞서는 지 여부를 결정하는 근거는 무엇입니까? 예를 들어 각 노드에 임의의 번호를 할당 할 것입니까? 그렇다면 구조체가 불완전한 것처럼 보입니다. 그 노드의 위치 값을 유지하기 위해 최소한 여분의 데이터 요소가 필요합니다 ...