Apa yang dimaksud dengan grafik dalam istilah awam

18

Apa itu grafik, dalam ilmu komputer, dan untuk apa grafik itu? Dalam istilah awam lebih disukai.

Saya telah membaca definisi di Wikipedia :

Dalam ilmu komputer, grafik adalah tipe data abstrak yang dimaksudkan untuk mengimplementasikan konsep grafik dan hypergraph dari matematika.

Struktur data grafik terdiri dari sekumpulan pasangan berurutan yang terbatas (dan mungkin bisa berubah-ubah), yang disebut tepi atau busur, dari entitas tertentu yang disebut simpul atau simpul. Seperti dalam matematika, suatu edge (x, y) dikatakan menunjuk atau beralih dari x ke y. Node dapat menjadi bagian dari struktur grafik, atau mungkin entitas eksternal yang diwakili oleh indeks integer atau referensi.

tapi saya mencari definisi yang kurang formal, lebih mudah dimengerti.

ConditionRacer
sumber
Apakah maksud Anda membuat grafik struktur data?
Sistem Down
1
Ya maaf. Grafik seperti dijelaskan di sini en.wikipedia.org/wiki/Graph_(abstract_data_type) , hanya saya mencari definisi yang kurang formal, lebih mudah dimengerti.
ConditionRacer
@ Justin984 Wikipedia tautan dengan tanda kurung (dan ada banyak dari mereka) tidak berfungsi, tanda kurung tidak cocok dengan format Markdown untuk tautan. Sekarang, untuk referensi di masa mendatang, silakan tambahkan klarifikasi apa pun pada pertanyaan Anda di dalam pertanyaan itu sendiri, bukan dalam komentar, itu tidak terlihat dan mudah untuk dilewatkan. Saya akan mengedit komentar Anda di atas dalam pertanyaan ...
yannis
@ Justin984 Perhatikan juga bahwa Computer Science Stack Exchange mungkin sedikit lebih tepat untuk pertanyaan seperti ini daripada Pemrogram. Jangan salah paham, pertanyaannya sempurna pada topik di sini, dan mendapat jawaban yang bagus, tetapi tidak ada salahnya jika Anda memeriksa komunitas yang sedikit lebih fokus pada konsep ilmu komputer inti daripada kita (jangan posting pertanyaan yang sama di beberapa situs, jika Anda mempostingnya di situs yang salah, kami dapat memindahkannya ke yang benar secara otomatis).
yannis

Jawaban:

26

Contoh awam yang sempurna mungkin adalah Facebook . Jaringan Anda, teman Anda, dan teman mereka dll, secara kolektif disebut sebagai grafik sosial .

Dalam "grafik" ini orang dianggap sebagai simpul grafik dan ujungnya adalah tautan pertemanan .

Di Facebook teman adalah hubungan dua arah (A adalah B Teman => B adalah teman A) sehingga grafiknya adalah Grafik Tidak Terarah . Jaringan seperti Google+ atau Twitter akan dianggap sebagai Sutradara Grafik karena arah hubungan memiliki arti di sini.

Semua grafik ini disebut sebagai grafik siklik , karena hubungan antar node dapat membentuk siklus. Sebuah Family Tree , di sisi lain, adalah jenis khusus dari grafik yang, antara lain, adalah Acyclic karena tidak mungkin ada siklus di relatioship pohon keluarga. (Secara teknis disebut Directed Acyclic Graph (DAG) karena diarahkan dan asiklik)

Ini harus mencakup semua jargon dasar yang melibatkan grafik, jadi sekarang Anda harus dapat mengikuti sisa materi di lapangan.

Karthik T
sumber
1
Tidak percaya tidak terpikir oleh saya bahwa itu disebut api facebook graph. Contoh yang baik!
ConditionRacer
4
Pohon keluarga bukan siklik? Seharusnya tidak, tapi sayangnya ...
Marjan Venema
1
@ Marsjanen, pohon keluarga adalah siklik ? (Ini adalah grafik yang diarahkan, jadi arahnya penting dalam menentukan siklus, dan mungkin langkah hubungan tidak benar-benar diperhitungkan.)
huon
@dbaupp: Saya tidak punya keinginan untuk masuk ke detail di sini, jadi saya hanya akan menyebutkan satu kata: incest.
Marjan Venema
5
@MarjanVenema, Anda kehilangan maksud saya. Siklus dalam grafik terarah adalah pola seperti A -> B -> C -> A(yaitu lingkaran panah), inses hanya memberi A -> B -> Cdan A -> D -> C(yaitu berlian). Sebuah siklus dalam silsilah keluarga membutuhkan perjalanan waktu.
huon
16

Grafik adalah salah satu konsep matematika paling penting yang digunakan dalam ilmu komputer.

Anda telah melihat grafik berulang kali. Bayangkan Anda naik pesawat dari satu kota ke kota lain. Anda pasti akan menemukan majalah mengkilap bagus dari maskapai di saku kursi di depan Anda. Di dekat bagian belakang majalah itu, Anda hampir selalu dapat menemukan peta yang menggambarkan kota-kota yang dilayani oleh maskapai yang direpresentasikan sebagai lingkaran, dengan penerbangan yang menghubungkan kota-kota tersebut diwakili sebagai garis lengkung. Itu sebuah grafik! Kota-kota, yang direpresentasikan sebagai lingkaran, adalah titik-titik pada grafik ini dan penerbangan, yang direpresentasikan sebagai garis lengkung, adalah ujung-ujungnya. Grafik hanyalah hal-hal dengan node dan tepi yang menghubungkan node.

Anda dapat memperindah grafik sederhana itu dengan berbagai cara. Anda tidak ingin melihat hanya sekelompok lingkaran dan garis ketika Anda melihat peta itu. Kota-kota itu memiliki nama. Memberi label pada kota-kota tersebut menghasilkan grafik berlabel. (Anda juga dapat memberi label pada tepi, misalnya, penerbangan 1234). Ilmu komputer sering mengaitkan data dengan node, terkadang dengan tepi, tetapi itu hanya perpanjangan label. Itu masih berupa label berlabel. Hasil perhiasan lain jika Anda dapat terbang langsung dari kota A ke kota B, tetapi tidak dari kota B ke kota A. Cara yang jelas untuk menggambarkan ini adalah dengan meletakkan panah pada garis yang menghubungkan kota-kota untuk menggambarkan hubungan satu arah ini. Sekarang Anda memiliki grafik yang diarahkan.

Daftar tertaut, pohon, diagram transisi negara, dan banyak struktur data sains komputer lainnya adalah contoh grafik. Ini adalah konsep yang sangat kuat.

David Hammen
sumber
Saya sebenarnya akan memperluas contoh itu untuk mencatat bahwa semua entitas yang dijelaskan dalam contoh Anda dapat digambarkan sebagai simpul dalam grafik (kota, pesawat, majalah, peta, dll), peta itu sendiri hanya menjadi satu simpul tunggal.
Demian Brecht
14

Pertanyaan yang lebih baik adalah "Untuk apa grafik tidak digunakan?". Ilmu Komputer, dalam banyak hal, adalah studi tentang Grafik.

Grafik, dalam istilah awam, adalah kumpulan objek abstrak sewenang-wenang yang disebut "simpul" atau "simpul" yang mewakili titik-titik koneksi. Mereka kemudian terhubung melalui "jalur" atau "tepi". Tipe data abstrak "Grafik" adalah implementasi dari "Grafik" matematika. Jadi pada dasarnya Anda memiliki simpul dan tepi sebagai bidang Anda dan berbagai operasi yang dapat Anda lakukan pada mereka. Anda dapat, misalnya, menambahkan simpul baru ke koleksi grafik (ini bisa berupa daftar atau larik atau struktur lain tergantung pada bahasanya). Anda kemudian dapat menautkan simpul itu ke simpul yang ada. Operasi juga akan mencakup melintasi grafik, memeriksa apakah dua node berbagi tepi (terhubung), mengambil nilai dari node atau tepi, dan penghapusan node atau tepi dari grafik.

Sejauh pemanfaatan berjalan, Grafik digunakan di semua tempat. Jaringan sangat banyak menggunakan mereka tetapi mereka ditemukan dalam Kecerdasan Buatan, Penambangan Data, Pengembangan Game, Geoinformatika, dan sejumlah disiplin ilmu lainnya. Dalam Ilmu Komputer formal, mereka melihat lebih banyak menggunakan, yaitu sebagai cara untuk mewakili negara.

Secara efektif apa pun yang Anda dapat wakili sebagai satu set koneksi dapat direpresentasikan sebagai grafik dan diimplementasikan melalui ADT itu dalam beberapa bentuk.

Berikut ini contoh grafik yang saya buat:

Contoh Grafik

Insinyur Dunia
sumber
3

Grafik hanyalah kumpulan benda yang dihubungkan bersama oleh garis yang disebut simpul.

Istilah "grafik" adalah abstraksi dan generalisasi dari banyak struktur data yang digunakan dalam pengembangan perangkat lunak. Daftar tertaut, pohon biner dan AST adalah semua grafik.

Pada dasarnya, setiap kumpulan objek yang memiliki pointer yang menghubungkan objek satu sama lain adalah grafik. Setelah Anda memiliki grafik, Anda dapat menerapkan prinsip-prinsip teori grafik untuk itu, untuk memecahkan masalah tertentu .

Robert Harvey
sumber