Code Danh sách kề [Lý thuyết đồ thị]

Trong lý thuyết đồ thị, danh sách kề (tiếng Anh: adjacency list) là danh sách biểu diễn tất cả các cạnh hoặc cung trong một đồ thị.
Nếu đồ thị vô hướng, mỗi phần tử của danh sách là một cặp hai đỉnh là hai đầu của cạnh tương ứng. Nếu đồ thị có hướng, mỗi phần tử là một cặp có thứ tự gồm hai đỉnh là đỉnh đầu và đỉnh cuối của cung tương ứng.
Ví dụ, danh sách {a,b},{a,c},{b,c} mô tả đồ thị vô hướng trong hình dưới đây, trong đó ba đỉnh a, b, c được nối với nhau.

Thông thường, danh sách kề không coi trọng thứ tự giữa các cạnh.

Code danh sách kề

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using GraphUtility;
using System.IO;


namespace Bai1
{
    class Graph
    {
        //input
        List<List<int>> adjList;
        int n;

        //output
        int[] degree;
        public void nhap()
        {
            NumbersFile f = new NumbersFile("DanhSachKe.INP");
            f.ReadNumber(out n);
            adjList = new List<List<int>>();
            for (int i = 0; i < n; i++)
            {
                List<int> t = new List<int>();
                int x;
                do
                {
                    f.ReadNumber(out x);
                    if (x == -1)
                        break;
                    t.Add(x);

                }
                while (x != -1);
                adjList.Add(t);
            }
         
        }
        public void tinhbac()
        {
            degree=new int[n];
            for (int i = 0; i < n; i++)
            {
                degree[i] = adjList[i].Count;
            }
        }
        public void xuat()
        {
            StreamWriter wr = new StreamWriter("DanhSachKe.OUT");
            for (int i = 0; i < n; i++)
                wr.Write(degree[i]+ " ");
            wr.Close();
        }
        static void Main(string[] args)
        {
            Graph g = new Graph();
            g.nhap();
            g.tinhbac();
            g.xuat();
        }
    }
}

Note: khi sử dụng using GraphUtility; bạn phải tạo class GraphUtility.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.IO;
using System.Text.RegularExpressions;

namespace GraphUtility
{
    class NumbersFile
    {
        StreamReader sr;

        public NumbersFile(string fileName)
        {
            sr = new StreamReader(fileName);
        }


        // Đọc 1 dòng trong file
        public string ReadLine()
        {
            string s;
            s = sr.ReadLine();
            return s;
        }

        // Tách thành các từ
        public string[] ReadWords()
        {
            Regex r = new Regex(@"\s+");
            string[] words;
            string s;

            s = sr.ReadLine();
            words = r.Split(s);

            return words;
        }

        // Đọc 1 số nguyên
        string[] words;
        int index;
        public bool ReadNumber(out int num)
        {
            if (words == null || index == words.Length)
            {
                words = ReadWords();
                index = 0;
            }

            num=0;
            if (int.TryParse(words[index], out num) == false)
                return false;
            index++;

            return true;
        }
    }
}