컴퓨터 과학에서 그래프 란 무엇이며 사용되는 것 에 대한? 평신도의 용어로 바람직합니다.
Wikipedia 에서 정의를 읽었습니다.
컴퓨터 과학에서 그래프는 수학에서 그래프와 하이퍼 그래프 개념을 구현하기위한 추상 데이터 유형입니다.
그래프 데이터 구조는 유한 (그리고 변경 가능할 수 있음)으로 구성됩니다. ) 노드 또는 정점이라고하는 특정 엔티티의 정렬 된 쌍 집합 (가장자리 또는 호라고 함). 수학에서와 같이 가장자리 (x, y)는 x에서 y로 향하거나 이동한다고합니다. 노드는 그래프 구조의 일부일 수 있습니다. , 또는 정수 인덱스 또는 참조로 표현되는 외부 엔티티 일 수 있습니다.
하지만 덜 형식적이고 이해하기 쉬운 정의를 찾고 있습니다.
댓글
- 데이터 구조를 그래프로 표시하는 것입니까?
- 예, 죄송합니다. 여기에 설명 된 그래프 en.wikipedia.org/wiki/Graph_ (abstract_data_type) , 나는 ' 만 찾고 있습니다. 덜 형식적이고 이해하기 쉬운 정의입니다.
- @ Justin984 위키 백과는 괄호로 묶인 링크 (그 중 너무 많음)는 작동하지 않습니다. '는 작동하지 않습니다. ' 링크의 마크 다운 형식과 잘 어울리지 않습니다. 이제 나중에 참조 할 수 있도록 댓글이 아닌 질문 자체의 질문에 대한 설명을 추가하세요. ' 표시되지 않으며 '는 놓치기 쉽습니다. ' 질문에서 위의 설명을 편집하겠습니다 …
- @ Justin984 또한 컴퓨터 과학 Stack Exchange 는 프로그래머보다 이와 같은 질문에 좀 더 적합 할 수 있습니다. ' 오해하지 마세요. 질문은 여기 주제와 완벽하게 관련되어 있으며 훌륭한 답변을 얻었지만 ' ' 우리보다 핵심 컴퓨터 과학 개념에 조금 더 초점을 맞춘 커뮤니티를 확인했습니다 (같은 질문을 게시하지 마세요 ' 그러나 잘못된 사이트에 게시하는 경우 자동으로 올바른 사이트로 이동할 수 있습니다.
답변
완벽한 평신도 “의 예는 Facebook 일 수 있습니다. 나와 친구, 그리고 친구 등을 통칭하여 소셜 그래프 .
이 “그래프”에서 사람 은 그래프의 노드 및
가장자리 는 우정 링크 .
Facebook에서 친구 는 양방향 관계 (A는 B의 친구 => B는 A의 친구)이므로 그래프는 무 방향 그래프 . Google+ 또는 Twitter와 같은 네트워크는 여기서 관계의 방향이 의미가 있으므로 방향 그래프 로 간주됩니다.
노드 간의 관계가주기를 형성 할 수 있으므로 이러한 모든 그래프를 순환 그래프라고합니다. . 반면 패밀리 트리 는 특히 비순환 가계도 관계에주기가있을 수 없기 때문입니다. (방향성 및 비순환 성 모두에서 기술적으로 방향성 비순환 그래프 (DAG) 라고합니다.)
여기에는 그래프와 관련된 모든 기본 전문 용어가 포함되어야하므로 이제 현장의 나머지 자료를 따를 수 있습니다.
댓글
- 믿을 수 ' ' 페이스 북 그래프 API라고하는 '는 나에게 발생하지 않습니다. 좋은 예입니다!
- 가계도가 주기적이지 않습니까? '이어서는 안되지만 안타깝게도 …
- @MarjanVenema, 가계도는 순환 ? (It ' 유 방향 그래프이므로 방향이주기를 결정하는 데 중요하며 아마도 단계 관계는 그렇지 않습니다. ' 정말 중요하지 않습니다.)
- @dbaupp : 여기에 자세히 설명하고 싶지 않으므로 ' 하나만 언급하겠습니다. 단어 : 근친상간.
- @MarjanVenema, 당신은 ' 내 요점을 놓치고 있습니다.방향 그래프의주기는
A -> B -> C -> A(예 : 화살표 원)와 같은 패턴이며 근친상간은A -> B -> C및A -> D -> C(예 : 다이아몬드). 가계도의주기에는 시간 여행이 필요합니다.
답변
그래프는 가장 중요한 수학적 개념 중 하나입니다. 컴퓨터 과학에 사용됩니다.
그래프를 여러 번 보았습니다. 한 도시에서 다른 도시로 비행기를 타는 것을 상상해보십시오. 좌석에있는 항공사에서 멋진 광택 잡지를 필연적으로 찾을 수 있습니다. 당신 앞에 주머니. 잡지 뒷면 근처에서 거의 항상 해당 항공사가 서비스하는 도시를 원으로 표시하고 해당 도시를 연결하는 항공편을 곡선으로 표시 한지도를 찾을 수 있습니다. 이것이 바로 그래프입니다. 원으로 표시된 도시는이 그래프의 노드이고 곡선으로 표시된 항공편은 가장자리입니다. 그래프는 노드를 연결하는 노드와 가장자리가있는 것입니다.
이러한 간단한 그래프를 다양한 방법으로 꾸밀 수 있습니다.지도를 볼 때 원과 선만보고 싶지는 않습니다. 이러한 도시에는 이름이 있습니다. 해당 도시에 레이블을 지정하면 레이블이있는 그래프가 생성됩니다. 예를 들어, 비행 1234와 같이 가장자리에 레이블을 지정합니다. 컴퓨터 과학은 종종 데이터를 노드와 연결하고 때로는 가장자리와 연결하지만 이는 레이블의 확장 일뿐입니다. 그래도 레이블이 붙은 그래프입니다. 도시 A에서 도시 B로 직접 비행 할 수 있지만 도시 B에서 도시 A로 비행 할 수없는 경우 또 다른 장식이 나타납니다.이를 묘사하는 분명한 방법은 도시를 연결하는 선에 화살표를 놓는 것입니다. 이 단방향 관계를 묘사합니다. 이제 방향성 그래프가 생겼습니다.
연결된 목록, 트리, 상태 전이 다이어그램 및 기타 많은 컴퓨터 과학 데이터 구조가 모두 그래프의 예입니다. 개념.
댓글
- 나는 ' 실제로이 예제를 확장하여 모든 예제에 설명 된 엔티티는 그래프 (도시, 비행기, 잡지,지도 등)의 정점으로 표시 될 수 있으며지도 자체는 단일 정점 일뿐입니다.
답변
더 나은 질문은 “그래프가 사용되지 않는 이유는 무엇입니까?”입니다. 컴퓨터 과학은 여러 측면에서 그래프 연구입니다.
평신도 용어로 그래프는 연결 지점을 나타내는 “노드”또는 “정점”이라고하는 임의의 추상 개체의 모음입니다. 그런 다음 “경로”또는 “가장자리”를 통해 연결됩니다. 추상 데이터 유형 “그래프”는 수학적 “그래프”의 구현입니다. 따라서 기본적으로 노드와 모서리를 필드로 사용하고 여기에서 수행 할 수있는 다양한 작업을 수행 할 수 있습니다. 예를 들어, 그래프 컬렉션에 새 노드를 추가 할 수 있습니다 (언어에 따라 목록, 배열 또는 기타 구조 일 수 있음). 그런 다음 해당 노드를 기존 노드에 연결할 수 있습니다. 또한 작업에는 그래프 탐색, 두 노드가 에지를 공유하는지 (연결되어 있는지) 확인, 노드 또는 에지에서 값 검색, 그래프에서 노드 또는 에지 삭제가 포함됩니다.
사용에 관한 한 그래프는 모든 곳에서 사용됩니다. 네트워킹은 특히 그것들을 많이 사용하지만 인공 지능, 데이터 마이닝, 게임 개발, 지리 정보학 및 기타 여러 분야에서 발견됩니다. 공식적인 컴퓨터 과학에서는 상태를 나타내는 방법으로 훨씬 더 많이 사용됩니다.
효과적으로 연결 집합으로 나타낼 수있는 모든 것은 그래프로 나타낼 수 있으며 일부에서는 해당 ADT를 통해 구현할 수 있습니다. 양식.
다음은 제가 만든 그래픽의 예입니다.
답변
그래프는 정점이라고하는 선으로 연결된 개체의 모음 일뿐입니다.
“그래프”라는 용어는 많은 것을 추상화하고 일반화 한 것입니다. 소프트웨어 개발에 사용되는 데이터 구조입니다. 연결된 목록, 이진 트리 및 AST “는 모두 그래프입니다.
기본적으로 객체를 서로 연관시키는 포인터가있는 것은 그래프입니다. 그래프가 있으면 그래프 이론 의 원칙을 적용하여 특정 문제를 해결할 수 있습니다. .