그래프 빌드에 대한 인접리스트

Question

누군가 적절한 노드와 링크가있는 그래프를 만들기 위해 어떤 종류의 인접 목록을 말해 줄 수 있습니까? ajdacency 목록을 정의하기 위해 트리 구조를 만들어야합니까? 아니면 다른 방법이 있습니까?
지금 매트릭스에 관심이 없다, 고마워.

nodes {a,b,c}, connection {{a-c},{b,c}} 

을 내가 가지고 ArrayList에 또는 내 인접리스트 [a[c],b[c],c[a,b]]

Answer 1

:

내가 예를 들어 같은 가지고 가장자리의 다른 노드로 모든 위치 안에 다른 arralists과 ArrayList를 만들 수 있습니다 인접 목록은 노드가 서로 연결되어 있음을 나타냅니다.

다음 노드가 1-4 인 그래프가있는 경우 인접 매트릭스는 다음과 같습니다. '1'은 노드 간의 연결을 나타냅니다.

1 2 3 4 
1 1 1 1 1 
2 1 0 0 0 
3 0 1 0 1 
4 0 1 1 0 

목록은 다음과 같습니다. 4. 당신도 할 수 다른 노드와의 연결을 나타내는 멤버 변수를 가지고 또는 - - 배열에 링크 된 목록을 사용하는 방법에 대한 배열이 포함 된 노드 일 것이다 그래서 위의 지정된 불구하고> 대표 링크

1 -> 1 -> 2 -> 3 -> 4 
2 -> 1 
3 -> 2 -> 4 
4 -> 2 -> 3 

가 되세요 배열의 각 요소 내에 별도의 배열 목록이 있어야합니다.

Answer 2

ArrayList의 ArrayList (또는 더 일반적으로 목록의 목록)는 좋은 방법입니다. 그렇습니다. 그것은 인접 목록의 꽤 표준적인 표현입니다. 그래서 당신의 아이디어는 좋은입니다.

또한 그래프의 크기 (노드 수)를 미리 알고 노드를 생성 한 후에 노드를 추가 할 필요가없는 경우 ArrayList 배열을 사용하면 효율성이 향상됩니다.

Answer 3

Dictionary을 사용하여 인접 목록을 구현할 수 있습니다. 사전의 각 키는 가장자리의 시작 노드를 나타냅니다. 각 값은 객체의 List 일 수 있으며, 각 객체는 가장자리의 대상 노드를 정의합니다.

예를 들어 List을 Tuples의 각 키에 저장할 수 있습니다. Tuple의 첫 번째 항목은 대상 노드를 나타냅니다. 다른 항목은 가장자리의 속성을 정의합니다.

class AdjacencyList 
{ 

    Dictionary<int, List<Tuple<int, int>>> adjacencyList; 

    // Constructor - creates an empty Adjacency List 
    public AdjacencyList(int vertices) 
    { 
     adjacencyList = new Dictionary<int, List<Tuple<int, int>>>(); 
    } 

    // Appends a new Edge to the linked list 
    public void addEdge(int startVertex, int endVertex, int weight) 
    { 
     if (!adjacencyList.ContainsKey(startVertex)) { 
      adjacencyList[startVertex] = new List<Tuple<int, int>>(); 
     } 

     adjacencyList[startVertex].Add(new Tuple<int, int>(endVertex, weight)); 
    } 

    // Removes the first occurence of an edge and returns true 
    // if there was any change in the collection, else false 
    public bool removeEdge(int startVertex, int endVertex, int weight) 
    { 
     Tuple<int, int> edge = new Tuple<int, int>(endVertex, weight); 

     return adjacencyList[startVertex].Remove(edge); 
    } 
}