Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

Đề tài: Chuyển dữ liệu từ ma trận kề thành danh sách cạnh & danh sách kề

  1. #1
    Ngày gia nhập
    02 2012
    Bài viết
    3

    Mặc định Chuyển dữ liệu từ ma trận kề thành danh sách cạnh & danh sách kề

    Mình đang làm bài tập này:

    BT. Cho đồ thị vô hướng G =<V,E> gồm N đỉnh và M cạnh. Ta định nghĩa khuôn dạng lưu trữ đồ thị bằngma trận kề, danh sách cạnh, danh sách kề dưới dạng file như sau:
    Khuôn dạng file ma trận kề:
    •Dòng đầu tiên ghi lại số tự nhiên N là số đỉnh của đồ thị;
    • N dòng kế tiếp ghi lại ma trận kề của đồ thị, hai phần tử khác nhau của ma trận kề được ghi cáchnhau bởi một vài ký tự trống.
    Khuôn dạng file danh sách cạnh:
    •Dòng đầu tiên ghi lại số tự nhiên N và M tương ứng với số đỉnh và số cạnh của đồ thị, haisố được ghi cách nhau bởi một vài ký tự trống;
    •M dòng kế tiếp mỗi dòng ghi lại một cạnh của đồ thị, đỉnh đầu và đỉnh cuối của mỗi cạnhđược ghi cách nhau bởi một vài ký tự trống.
    Khuôn dạng file danh sách kề:
    •Dòng đầu tiên ghi lại số tự nhiên N là số đỉnh của đồ thị;
    • N dòng kế tiếp mỗi dòng ghi lại danh sách kề của đỉnh tương ứng. Hai đỉnh trong cùng một danhsách kề được phân biệt với nhau bằng một hoặc vài kí tự trống, đỉnh không có cạnh nối với nó(đỉnh cô lập) được ghi giá trị 0.Cho file mtke.in biểu diễn đồ thị dưới dạng ma trận kề.
    Hãy viết chương trình chuyển đổi biểu diễn đồthị thành các file dưới dạng danh sách cạnh (dscanh.out ) và danh sách kề (dske.out ).
    Ví dụ đồ thị gồm 5 đỉnh, 5 cạnh được biểu diễn trong file mtke.in như dưới đây sẽ cho ta các file dscanh.out và dske.out tương ứng.
    dothi.in
    5
    0 1 1 0 0
    1 0 0 1 0
    1 0 0 0 1
    0 1 0 0 0
    0 0 1 0 0
    canh.out
    5 4
    1 2
    1 3
    2 4
    3 5
    ke.out
    5
    2 3
    1 4
    1 5
    2
    3
    Mong các Pro chỉ cho mình cách biểu diễn matran nhu trên ?

  2. #2
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Lật cuốn sách toán rời rạc, nội dung lý thuyết đồ thị ra mà coi.
    Ma trận a[nxn] :trong đó a[i][j] = 1 nếu tồn tại cạnh (Vi,Vj) và =0 nếu ko tồn tại cạnh đó.
    Um Mani Padme Hum...!!

  3. #3
    Ngày gia nhập
    02 2012
    Bài viết
    3

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Lật cuốn sách toán rời rạc, nội dung lý thuyết đồ thị ra mà coi.
    Ma trận a[nxn] :trong đó a[i][j] = 1 nếu tồn tại cạnh (Vi,Vj) và =0 nếu ko tồn tại cạnh đó.
    Cái này mình hiểu rồi, ở đây mình muốn hỏi thuật toán chuyển sang danh sách cạnh & danh sách đỉnh kề từ matran kia cơ ?

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    12

    một số đoạn code cho bạn
    Code:
    struct DoThi
    {
    	int type;
    	int V;
    	int E;
    	list DSK[MAX];// danh sach ke
    	int MTK[MAX][MAX];// ma tran ke
    	int MTLT[MAX][MAX];// ma tran lien thuoc
    	Array DSC;// danh sach canh
    };
    void Nhap(DoThi &d)
    {
    	fstream file;
    	file.open("dtinput.txt",ios::in);
    	file>>d.type>>d.V>>d.E;
    
    	for(int i=1;i<=d.V;++i)
    	{
    		Khoitao(d.DSK[i]);
    		Node *x=new Node;
    		x=GetNode(i);
    		d.DSK[i].head=d.DSK[i].tail=x;		
    	}
    
    	int a,b;
    	for(int i=1;i<=d.E;++i)
    	{
    		file>>a>>b;
    		AddNode(d.DSK[a],GetNode(b));
    		if (d.type==0)
    			AddNode(d.DSK[b],GetNode(a));
    	}
    	file.close();
    }
    
    void ChuyenSangMaTranLienThuoc(DoThi &d)
    {
    	for(int i=1;i<=d.E;i++)
    		for(int j=1;j<=d.V;++j)
    			d.MTLT[i][j]=0;
    	Node *p=new Node;
    	int j=1;
    	for(int i=1;i<=d.V;++i)
    	{
    		for(p=d.DSK[i].head->next;p!=NULL;p=p->next)
    		{
    			d.MTLT[j][d.DSK[i].head->a]=1;
    				if (d.type==0)
    					d.MTLT[j][p->a]=1;
    				else
    					d.MTLT[j][p->a]=-1;
    			++j;
    		}
    	}
    	delete p;
    	XuatMaTranLienThuoc(d);
    }
    
    void ChuyenSangDanhSachCanh(DoThi &d)
    {
    	Node *p=new Node;
    	int j=1;
    	for(int i=1;i<=d.V;++i)
    	{
    		for(p=d.DSK[i].head->next;p!=NULL;p=p->next)
    		{
    			d.DSC.Dau[j]=d.DSK[i].head->a;
    			d.DSC.Cuoi[j]=p->a;
    			++j;
    			if(!d.type)
    			{				
    				d.DSC.Dau[j]= p->a;
    				d.DSC.Cuoi[j]=d.DSK[i].head->a;
    				++j;
    			}	
    		}
    	}
    	delete p;
    	XuatDanhSachCanh(d);
    }

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Trích dẫn Nguyên bản được gửi bởi tunglm Xem bài viết
    Cái này mình hiểu rồi, ở đây mình muốn hỏi thuật toán chuyển sang danh sách cạnh & danh sách đỉnh kề từ matran kia cơ ?
    Tui tưởng bạn muốn hỏi cái câu cuối cùng trong bài như này
    Mong các Pro chỉ cho mình cách biểu diễn matran nhu trên ?
    Hỏi mà cũng lười nữa
    Có người tốt bụng đưa code cho rồi kìa, lấy về mà xài cho rồi (mà xài chưa được đâu vì ng` ta chỉ đưa cho 2 cái tay thôi, còn mấy bộ phận khác chưa đưa )

    Còn thích thuật toán thì có thuật toán:
    DS Cạnh
    C++ Code:
    1.   duyệt ma trận tam giác phía trên của đường chéo
    2.   {
    3.        if (a[i][j]==1)
    4.        {
    5.             Có đỉnh i, có đỉnh j. In ra ngoài hay thích làm gì đó thì làm;
    6.             xuống dòng;
    7.        }
    8.   }
    DS kề
    C++ Code:
    1.  duyệt theo từng hàng
    2.  {  
    3.      int sodinhke=0;
    4.      duyệt theo từng vị trí của phần tử trong hàng
    5.      {
    6.           if(a[i][j] == 1)
    7.           {
    8.               Có đỉnh j chính là đỉnh kề với đỉnh i. In j ra ngoài;
    9.               sodinhke++;
    10.           }
    11.      }
    12.      if (sodinhke==0)
    13.           in số 0 ra ngoài // tức là để hiểu đỉnh i là đỉnh cô lập;
    14.      Xuống dòng;
    15.  }
    Mấy cái này thì có gì là ghê gớm của đồ thị gì đâu. Chung quy lại cũng chỉ là xử lý mảng 2 chiều. Chấm hết
    Đã được chỉnh sửa lần cuối bởi clchicken : 13-02-2012 lúc 04:05 AM.
    Um Mani Padme Hum...!!

  6. #6
    Ngày gia nhập
    02 2012
    Bài viết
    1

    Mặc định cho mình hỏi phần mềm lập trình C tìm ở đâu vậy ?

    mình mới học lập trình cơ bản nên mới biết tới lập trình C nên muốn tìm nó về nghiên cứu mà tìm không có thấy, ai biết chỉ dùm mình....

  7. #7
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Đầu tiên học ngôn ngữ tự nhiên cho thạo đã
    Ngôn ngữ tự nhiên viết còn lủng cà lủng củng thế kia thì viết với ngôn ngữ lập trình như nào

    Sau đó mua cuốn sách về đọc
    Um Mani Padme Hum...!!

  8. #8
    Ngày gia nhập
    02 2012
    Bài viết
    3

    Thanks các bạn, Mình định duyệt matran bằng BFS hoặc DFS, như khi duyệt được rồi, thì mình chuyển từ kiểu bit (0,1) sang dạng số thập phân, dùng hàm gì được nhỉ:
    Ví dụ: chuyển các số 0,1 từ matran thành (hay là mình điền số đỉnh ra luôn nhỉ ) ?
    Danh sach canh:
    1 2
    1 3
    2 4
    3 5
    Đã được chỉnh sửa lần cuối bởi tunglm : 13-02-2012 lúc 10:11 PM. Lý do: Sửa cho chính xác

  9. #9
    Ngày gia nhập
    10 2011
    Bài viết
    552

    Phải hiểu mấy con số đó là cái gì.
    Xem lại thuật toán của tui đưa
    + Nhìn vào cái ma trận, chỗ nào có giá trị 1 thì dóng lên nhìn cột bao nhiêu, hàng bao nhiêu . Từ đó ngộ ra vấn đề

    Đổi nhị phân sang thập phân cái gì đây mà đổi ?
    Um Mani Padme Hum...!!

  10. #10
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Trích dẫn Nguyên bản được gửi bởi tunglm Xem bài viết
    Thanks các bạn, Mình định duyệt matran bằng BFS hoặc DFS, như khi duyệt được rồi, thì mình chuyển từ kiểu bit (0,1) sang dạng số thập phân, dùng hàm gì được nhỉ:
    Ví dụ: chuyển các số 0,1 từ matran thành (hay là mình điền số đỉnh ra luôn nhỉ ) ?
    Danh sach canh:
    1 2
    1 3
    2 4
    3 5
    Bạn làm được đến trình độ đó là cao rồi. Chỗ còn lại đâu có gì rắc rối.
    Chỉ tại bạn học đốt giai đoạn căn bản của C. Chỉ cần về lục sách vở ra đọc lại cho kỹ các phần căn bản. Các phần này tuy rất dễ nhưng cũng rất lỉnh kỉnh cho nên hỏi tốn thời gian gấp mấy lần đọc.
    Hay là bạn cho rằng mình là nhân tài chỉ cần hỏi một biết mười?

Các đề tài tương tự

  1. Kỹ thuật C ý tưởng chuyển từ danh sách kề sang danh sách cạnh, ma trận kề
    Gửi bởi koko trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 05-08-2012, 09:29 AM
  2. Lập trình C++ chuyển đổi từ danh sách cạnh sang ma trận kề
    Gửi bởi th_it trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 17-07-2011, 05:21 PM
  3. Chuyển danh sách kề sang ma trận kề. Help
    Gửi bởi van.duc0409 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 18-05-2011, 12:48 PM
  4. Bài tập C++ Chuyển đồ thị từ dạng danh sách kề sang ma trận kề?
    Gửi bởi chi.ptit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 21-03-2011, 08:59 AM
  5. Chuyển đổi các cách biểu diễn đồ thị(ma trận kề -->danh sách kề)
    Gửi bởi johanncruyf trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 05-03-2011, 10:12 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn