Biểu diễn Danh sách kề sang Ma trận kề

// thêm -1 ở cuối mỗi dòng chỉ là thủ thuật nhỏ mà thôi, nếu muốn giữ nguyên input (không có -1) thì bạn phải chuyển dữ liệu nhập vào sang kiểu char rồi xử lý.

Cho danh sách kề như sau, biểu diễn đồ thị có 5 đỉnh (vertex)

v1 connect to 2, 3;

v2 -> 1, 3, 5

v3 -> 1, 2, 5

v4 -> 5

v5 -> 2, 3, 4

5
2 3 -1
1 3 5 -1
1 2 5 -1
5 -1
2 3 4 -1

…….. solution:

#include <fstream>
#include<iostream>
#include <vector>
#define MAX 1000
#define FI "DanhSachKe.INP"
#define FO "GRAPH.out"
using namespace std;
int A[MAX][MAX];//Ma tran ke
vector<vector<int>> matrix;
int N;//so dinh
ifstream fi;//doc file
ofstream fo;//xuat file
vector<int> vec;
void Input(){
 fi.open(FI);
 fi >> N;
 matrix.resize(N);
 for(int i=0; i<N; i++){
 int ver;
 do 
 {
 fi >> ver;
 if(ver != -1){
 matrix[i].push_back(ver);
 }
 } while (ver != -1);
 }
 fi.close();
}
void setMatrix(int x){
}
void Xuat(){
 fo.open(FO);
 // matrix.resize(N+1);
 for(int i=0; i<matrix.size(); i++){
 for(int j=0; j<matrix[i].size(); j++){
 cout << matrix[i][j] << " ";
 }
 cout << endl;
 }
 fo.close();
}
void DSK2MTK(){
 for(int i=0; i<N; i++){
 for(int j=0; j<N; j++){
 A[i][j] = 0;
 }
 }
 for(int i=0; i<N; i++){
 for(int j=0; j<matrix[i].size(); j++){
 A[i][matrix[i][j]-1] = 1;
 }
 }
}
void xuatMTK(){
 for(int i=0; i<N; i++){
 for(int j=0; j<N; j++){
 cout << A[i][j] << " ";
 }
 cout << endl;
 }
}
int main(){
 // nhapDSK();
 Input();
 Xuat();
 DSK2MTK();
 xuatMTK();
 return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s