/*
編寫一個程式algo8-1.cpp,實作不帶權圖和帶權圖的鄰接矩陣與鄰接表的互相
轉換算法、輸出鄰接矩陣與鄰接表的算法,并在此基礎上設計一個程式exp8-1.cpp
實作如下功能:
1)建立如圖有向圖G的鄰接矩陣,并輸出;
2)由有向圖G的鄰接矩陣産生鄰接表,并輸出;
3)再由2)鄰接表産生對應的鄰接矩陣,并輸出。
*/
#include<iostream>
#define MAX 6
using namespace std;
class VertexType //頂點類型
{
public:
int no; //頂點編号
char info;
};
class MGraph
{
public:
int edges[MAX][MAX]; //鄰接矩陣的變數組,使用int類型記錄,主要記錄為0、1,帶權的則為其權值
int n,e; // 頂點數,邊數
VertexType vexs[MAX]; //存放頂點資訊
MGraph():n(0),e(0){
for (int x = 0 ; x < MAX ; x++)
for(int y = 0 ; y < MAX ; y ++)
edges[x][y] = 0;
for (int i =0; i < MAX; i++)
this ->vexs[i].info = -1;
}
};// 完整的圖鄰接矩陣類型
class ArcNode
{
public:
ArcNode():adjvex(0),nextarc(NULL){}
int adjvex; //該邊的終點編号
ArcNode * nextarc;
char info; //邊的資訊
};
class VNode //起點資訊
{
public :
VNode():data(0),firstarc(NULL){}
void Reset()
{
adjvex = -1;
data = 0;
firstarc = NULL;
}
int adjvex;
char data; //起點資訊
ArcNode * firstarc;
};
typedef VNode AdjList[MAX] ; //eg:"typedef char Line[81]; //Line是char[81] (而不是說char是line[81])"
class ALGraph
{
public:
ALGraph():n (0),e (0){ //鄰接表初始化
for(int i = 0;i < MAX ; i ++)
adjlist[i].Reset();
}
AdjList adjlist;
int n,e;
}; //完整的圖鄰接表的類型
void CreatMGraph(MGraph * G) //圖的構造函數,不帶權帶向
{
cout << "輸入圖的頂點個數: ";
cin >> G ->n ;
cout << "輸入圖的邊數:";
cin >> G ->e ;
int x,y;
for(x = 0 ; x < G ->n ; x++)
for ( y = 0 ; y < G ->n ; y++)
G->edges[x][y] = 0; //預設設定為 0
for (int i = 0 ; i < G ->e ; i++)
{
int weight; // 權值
cout << "請輸入第" << (i+1) << "條邊的前後節點。" << endl;
cout << "出發點:" ;
cin >> x;
cout << "接收點:" ;
cin >> y;
/* cout << "輸入權值:";
cin >> weight;*/
G ->edges[x][y] = 1;
}
}
void OutputMGraph(MGraph * G)
{
cout << "----------現在輸出鄰接矩陣------------" << endl;
for(int i = 0 ; i < G ->n ; i ++)
{
for (int j = 0 ; j < G ->n ; j ++)
cout << G ->edges[i][j] << " " ;
cout << endl;
}
cout << "--------------------------------------" <<endl;
}
void OutputALGraph(ALGraph * G) //輸出鄰接表
{
cout << "--------------現在輸出鄰接表---------------" << endl;
for(int i = 0; i < G ->n ; i ++)
{
if(G ->adjlist[i].adjvex == -1) break; //不存在頂點時退出循環
cout << G ->adjlist[i].adjvex ;
while(G ->adjlist [i].firstarc != NULL)
{
ArcNode * temp = G ->adjlist[i].firstarc;
while(temp != NULL)
{
cout << "---->" << temp->adjvex;
if(temp ->nextarc == NULL) break;
temp = temp ->nextarc;
}if(temp ->nextarc == NULL) break; //再跳出
}
cout << endl;
}
cout << "---------------鄰接表輸出結束---------------" << endl;
}
void MatToList(MGraph * g,ALGraph *&G)
{
ArcNode * p;
G = new ALGraph();
for(int i = 0; i < g ->n ;i ++) //初始化鄰接表,使其寫上頂點編号
G ->adjlist[i].adjvex = i; // 0 1 2 3 4 5 ,n的值應該為6
for(int i = 0;i < g ->n;i++)
for(int j = 0; j < g ->n;j++)
if(g ->edges[i][j] != 0) //不帶權的有向或無向鄰接矩陣轉鄰接表
{ p = new ArcNode();
p ->adjvex = j;
p ->nextarc = G ->adjlist[i].firstarc;
G ->adjlist[i].firstarc = p;
}
G ->n = g ->n;
G ->e = g ->e;
}
void ListToMat(ALGraph * g,MGraph * &G) //鄰接表轉鄰接矩陣
{
int i;
ArcNode * p;
for( i =0; i< g ->n;i++)
{
p = g ->adjlist[i].firstarc;
while(p != NULL)
{
G ->edges[i][p ->adjvex] = 1;
p = p ->nextarc;
}
}
G ->e = g ->e;
G ->n = g ->n;
}
int main()
{
MGraph * G = new MGraph();
CreatMGraph(G);
OutputMGraph(G);
ALGraph * J;
MatToList(G,J);
OutputALGraph(J);
MGraph * g = new MGraph();
ListToMat(J,g);
OutputMGraph(g);
return 0;
}