拓撲排序
實作鄰接鏈表和逆鄰接鏈表兩種求頂點入度的演算法，并在拓撲排序演算法中應用
有：利用逆鄰接表求出各頂點的入度存入陣列indegree中
也有：正鄰接表求頂點的入度
//演算法6.12 拓撲排序
#include <iostream>
using namespace std;
#define MVNum 100 //最大頂點數
#define OK 1
#define ERROR 0
typedef char VerTexType;
//- - - - -圖的鄰接表存盤表示- - - - -
typedef struct ArcNode{ //邊結點
int adjvex; //該邊所指向的頂點的位置
struct ArcNode *nextarc; //指向下一條邊的指標
}ArcNode;
typedef struct VNode{
VerTexType data; //頂點資訊
ArcNode *firstarc; //指向第一條依附該頂點的邊的指標
}VNode, AdjList[MVNum]; //AdjList表示鄰接表型別
typedef struct{
AdjList vertices; //鄰接表
AdjList converse_vertices; //逆鄰接表
int vexnum, arcnum; //圖的當前頂點數和邊數
}ALGraph;
//- - - - - - - - - - - - - - - -
//- - - - -順序堆疊的定義- - - - -
typedef struct{
int *base;
int *top;
int stacksize;
}spStack;
//- - - - - - - - - - - - - - - -
int indegree[MVNum]; //陣列indegree存放個頂點的入度
spStack S;
//------------堆疊的相關操作----------------------
void InitStack(spStack &S){
//初始化堆疊
S.base = new int[MVNum];
if(!S.base)
exit(1);
S.top = S.base;
S.stacksize = MVNum;
}//InitStack
void Push(spStack &S , int i){
//進堆疊
if(S.top - S.base == S.stacksize)
return;
*S.top++ = i;
}//Push
void Pop(spStack &S , int &i){
//出堆疊
if(S.top == S.base)
return;
i = *--S.top;
}//Pop
bool StackEmpty(spStack S){
//判斷堆疊是否為空
if(S.top == S.base)
return true;
return false;
}//StackEmpty
//-------------------------------------------------
int LocateVex(ALGraph G , VerTexType v){
//確定點v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vertices[i].data =https://www.cnblogs.com/ygjzs/p/= v)
return i;
return -1;
}//LocateVex
int CreateUDG(ALGraph &G){
//創建有向圖G的鄰接表、逆鄰接表
int i , k;
cout <<"請輸入總頂點數，總邊數，以空格隔開:";
cin >> G.vexnum >> G.arcnum; //輸入總頂點數，總邊數
cout << endl;
cout << "輸入點的名稱，如a" << endl;
for(i = 0; i < G.vexnum; ++i){ //輸入各點，構造表頭結點表
cout << "請輸入第" << (i+1) << "個點的名稱:";
cin >> G.vertices[i].data; //輸入頂點值
G.converse_vertices[i].data = https://www.cnblogs.com/ygjzs/p/G.vertices[i].data;
//初始化表頭結點的指標域為NULL
G.vertices[i].firstarc=NULL;
G.converse_vertices[i].firstarc=NULL;
}//for
cout << endl;
cout <<"輸入邊依附的頂點，如a b" << endl;
for(k = 0; k < G.arcnum;++k){ //輸入各邊，構造鄰接表
VerTexType v1 , v2;
int i , j;
cout << "請輸入第" << (k + 1) << "條邊依附的頂點:";
cin >> v1 >> v2; //輸入一條邊依附的兩個頂點
i = LocateVex(G, v1); j = LocateVex(G, v2);
//確定v1和v2在G中位置，即頂點在G.vertices中的序號
ArcNode *p1=new ArcNode; //生成一個新的邊結點*p1
p1->adjvex=j; //鄰接點序號為j
p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//將新結點*p1插入頂點vi的邊表頭部
ArcNode *p2=new ArcNode; //生成一個新的邊結點*p1
p2->adjvex=i; //逆鄰接點序號為i
p2->nextarc = G.converse_vertices[j].firstarc; G.converse_vertices[j].firstarc=p2;
//將新結點*p1插入頂點vi的邊表頭部
}//for
return OK;
}//CreateUDG
// void FindInDegree(ALGraph G){
// //利用逆鄰接表求出各頂點的入度存入陣列indegree中
// int i , count;
//
// for(i = 0 ; i < G.vexnum ; i++){
// count = 0;
// ArcNode *p = G.converse_vertices[i].firstarc;
// if(p){
// while(p){
// p = p->nextarc;
// count++;
// }
// }
// indegree[i] = count;
// }
// }//FindInDegree
void FindInDegree(ALGraph G)
{ // 正鄰接表求頂點的入度
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; // 賦初值
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p = p->nextarc;
}
}
}
int TopologicalSort(ALGraph G , int topo[]){
//有向圖G采用鄰接表存盤結構
//若G無回路，則生成G的一個拓撲序列topo[]并回傳OK，否則ERROR
int i , m;
FindInDegree(G); //求出各頂點的入度存入陣列indegree中
InitStack(S); //堆疊S初始化為空
for(i = 0; i < G.vexnum; ++i)
if(!indegree[i]) Push(S, i); //入度為0者進堆疊
m = 0; //對輸出頂點計數，初始為0
while(!StackEmpty(S)){ //堆疊S非空
Pop(S, i); //將堆疊頂頂點vi出堆疊
topo[m]=i; //將vi保存在拓撲序列陣列topo中
++m; //對輸出頂點計數
ArcNode *p = G.vertices[i].firstarc; //p指向vi的第一個鄰接點
while(p){
int k = p->adjvex; //vk為vi的鄰接點
--indegree[k]; //vi的每個鄰接點的入度減1
if(indegree[k] ==0) Push(S, k); //若入度減為0，則入堆疊
p = p->nextarc; //p指向頂點vi下一個鄰接結點
}//while
}//while
if(m < G.vexnum) return ERROR; //該有向圖有回路
else return OK;
}//TopologicalSort
int main(){
cout << "************演算法6.12 拓撲排序**************" << endl << endl;
ALGraph G;
CreateUDG(G);
int *topo = new int [G.vexnum];
cout << endl;
cout << "有向圖的鄰接表、逆鄰接表創建完成!" << endl << endl;
if(TopologicalSort(G , topo)){
cout << "該有向圖的拓撲有序序列為：";
for(int j = 0 ; j < G.vexnum; j++){
if(j != G.vexnum - 1)
cout << G.vertices[topo[j]].data << " , ";
else
cout << G.vertices[topo[j]].data << endl << endl;
}//for
}
else
cout << "網中存在環，無法進行拓撲排序！" <<endl << endl;
return OK;
}//main
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/115732.html
標籤：其他