編寫算法：根據(jù)含有n個頂點(diǎn)的有向圖鄰接表，構(gòu)造相應(yīng)的逆鄰接表。
1.算法的思想：
鄰接表和逆鏈接表的頂點(diǎn)信息是相同的，直接復(fù)制即可。把出邊信息轉(zhuǎn)換成入邊信息，則需要逐一訪問鄰接表的各結(jié)點(diǎn)的出邊表，把邊結(jié)點(diǎn)通過頭插法插入相應(yīng)的入邊表中。
2.算法的實(shí)現(xiàn)：文章來源：http://www.zghlxwxcb.cn/news/detail-508679.html
typedef struct node{ /*邊表結(jié)點(diǎn)*/
int adjvex; /*鄰接點(diǎn)域*/
struct node * next; /*指向下一個鄰接點(diǎn)的指針域*/
}EdgeNode; /*若要表示邊上信息，則應(yīng)增加一個數(shù)據(jù)域info*/
typedef struct ArcNode{
int adjvex; //該邊所指向的結(jié)點(diǎn)的位置
ArcNode *nextarc; //指向下一條邊的指針
}ArcNode;
typedef struct vnode{ /*頂點(diǎn)表結(jié)點(diǎn)*/
char vertex [20]; /*頂點(diǎn)域*/
EdgeNode *firstedge; /*邊表頭指針*/
ArcNode *firstarc; //指向第一條邊的指針
}VertexNode;
/*AdjList是鄰接表類型*/
typedef VertexNode AdjList[MaxVerNum];
typedef struct {
AdjList adjlist; /*鄰接表*/
int n,e; /*頂點(diǎn)數(shù)和邊數(shù)*/
}ALGraph;
//將有向圖的出度鄰接表改為按入度建立的逆鄰接表
void InvertAdjList(AdjList ginAdjList gout)
{
int j;
ArcNode *s;
for(i=1;i<=n;i++) //設(shè)有向圖有n個頂點(diǎn)，建逆鄰接表的頂點(diǎn)
{
gin[i].vertex==gout[i].vertex; //鄰接表和逆鏈接表的頂點(diǎn)信息是相同的，直接復(fù)制即
gin.firstarc=null; //指向第一條邊的指針為空
}
for(i=1;i<=n;i++) //鄰接表轉(zhuǎn)為逆鄰接表
{
p=gout[i].firstarc; //取指向鄰接表的指針
while(p!=null){
j=p->adjvex; //該邊所指向的結(jié)點(diǎn)的位置
s=(rcNode*)malloc(sizeof(ArcNode)); //申請結(jié)點(diǎn)空間
s->adjvex=i; //把邊結(jié)點(diǎn)通過頭插法 插入到相應(yīng)的入邊表
s->next=gin[j].firstarc; gin[j].firstarc=s;
p=p->next; //下一個鄰接點(diǎn)
}
}
}
舉個栗子：
鄰接表：
逆鄰接表：
注：
一個稀疏圖頂點(diǎn)個數(shù)為n，邊數(shù)為e。為了解決在存儲稀疏圖鄰接矩陣（使用存儲空間 n2 ）浪費(fèi)空間的這一劣勢，引入鄰接表（ n+2e）來減少存儲空間的浪費(fèi)。
鄰接表雖然在空間上有很大的優(yōu)勢，但是對于有向圖來說，若需查找入度的個數(shù)就需要遍歷整個鄰接表，所以也不方便，效率有點(diǎn)低哦，解決這個問題有兩種方法：
1：十字交叉鏈表
2：逆鄰接表（與鄰接表共同使用，達(dá)到更好的效果）文章來源地址http://www.zghlxwxcb.cn/news/detail-508679.html
- 鄰接表:某頂點(diǎn)鏈表的結(jié)點(diǎn)個數(shù)是發(fā)出去的弧的數(shù)量，也就是出度。
- 逆鄰接表:某頂點(diǎn)鏈表的結(jié)點(diǎn)個數(shù)是進(jìn)入的弧的數(shù)量，也就是入度。
- 鄰接表反映的是結(jié)點(diǎn)的出度鄰接情況，逆鄰接表反映的是結(jié)點(diǎn)的入度鄰接情況。
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】算法題：鄰接表構(gòu)造相應(yīng)的逆鄰接表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
