第13週プロジェクト5
7313 ワード
/*
* Copyright (c)2015,
* All rights reserved.
* ： 5.cbp
* ：
* ：2015 12 12
* ：v1.0
* ：
* ：
* ：
*/#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#define MAXV 100 //
#define INF 32767 //INF ∞
typedef int InfoType;
//
typedef struct
{
int no; //
InfoType info; // ，
} VertexType; //
typedef struct //
{
int edges[MAXV][MAXV]; //
int n,e; // ，
VertexType vexs[MAXV]; //
} MGraph; //
//
typedef struct ANode //
{
int adjvex; //
struct ANode *nextarc; //
InfoType info; // ,
} ArcNode;
typedef int Vertex;
typedef struct Vnode //
{
Vertex data; //
int count; // ,
ArcNode *firstarc; //
} VNode;
typedef VNode AdjList[MAXV]; //AdjList
typedef struct
{
AdjList adjlist; //
int n,e; // n e
} ALGraph; //
// ： ，
// ：Arr - ， ， Arr （ int ）
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g); //
void ArrayToList(int *Arr, int n, ALGraph *&); //
void MatToList(MGraph g,ALGraph *&G);// g G
void ListToMat(ALGraph *G,MGraph &g);// G g
void DispMat(MGraph g);// g
void DispAdj(ALGraph *G);// G
void TopSort(ALGraph *G);
#endif // GRAPH_H_INCLUDED
#include<stdio.h>
#include"head.h"
int main()
{
ALGraph *G;
int A[7][7]=
{
{0,0,1,0,0,0,0},
{0,0,0,1,1,0,1},
{0,0,0,1,0,0,0},
{0,0,0,0,1,1,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0}
};
ArrayToList(A[0], 7, G);
DispAdj(G);
printf("
");
printf(" :");
TopSort(G);
printf("
");
return 0;
}
#include <stdio.h>
#include <malloc.h>
#include "head.h"
// ： ，
// ：Arr - ， ， Arr （ int ）
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g)
{
int i,j,count=0; //count ， 0
g.n=n;
for (i=0; i<g.n; i++)
for (j=0; j<g.n; j++)
{
g.edges[i][j]=Arr[i*n+j]; // Arr n×n ，Arr[i*n+j] Arr[i][j]，
if(g.edges[i][j]!=0 && g.edges[i][j]!=INF)
count++;
}
g.e=count;
}
void ArrayToList(int *Arr, int n, ALGraph *&G)
{
int i,j,count=0; //count ， 0
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
G->n=n;
for (i=0; i<n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<n; i++) //
for (j=n-1; j>=0; j--)
if (Arr[i*n+j]!=0) // ， Arr n×n ，Arr[i*n+j] Arr[i][j]
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=Arr[i*n+j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->e=count;
}
void MatToList(MGraph g, ALGraph *&G)
// g G
{
int i,j;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0; i<g.n; i++) //
G->adjlist[i].firstarc=NULL;
for (i=0; i<g.n; i++) //
for (j=g.n-1; j>=0; j--)
if (g.edges[i][j]!=0) //
{
p=(ArcNode *)malloc(sizeof(ArcNode)); // *p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; // *p
G->adjlist[i].firstarc=p;
}
G->n=g.n;
G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
// G g
{
int i,j;
ArcNode *p;
g.n=G->n; // “ ” 。g.n ，
g.e=G->e;
for (i=0; i<g.n; i++) //
for (j=0; j<g.n; j++)
g.edges[i][j]=0;
for (i=0; i<G->n; i++) // ，
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
}
void DispMat(MGraph g)
// g
{
int i,j;
for (i=0; i<g.n; i++)
{
for (j=0; j<g.n; j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("
");
}
}
void DispAdj(ALGraph *G)
// G
{
int i;
ArcNode *p;
for (i=0; i<G->n; i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("-->%d/%d ",p->adjvex,p->info);
p=p->nextarc;
}
printf("
");
}
}
void TopSort(ALGraph *G)
{
int i,j;
int St[MAXV],top=-1; // St top
ArcNode *p;
for (i=0; i<G->n; i++) // 0
G->adjlist[i].count=0;
for (i=0; i<G->n; i++) //
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
G->adjlist[p->adjvex].count++;
p=p->nextarc;
}
}
for (i=0; i<G->n; i++)
if (G->adjlist[i].count==0) // 0
{
top++;
St[top]=i;
}
while (top>-1) //
{
i=St[top];
top--; //
printf("%d ",i); //
p=G->adjlist[i].firstarc; //
while (p!=NULL)
{
j=p->adjvex;
G->adjlist[j].count--;
if (G->adjlist[j].count==0)// 0
{
top++;
St[top]=j;
}
p=p->nextarc; //
}
}
}
：
<img src="http://img.blog.csdn.net/20151214165302834?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />
知識ポイントのまとめ:
AOVネットワークによってトポロジーシーケンスを構築するトポロジーソートアルゴリズムは,入度0の頂点が存在しないまで,主に次の2ステップをループ実行する.
(1)入度0の頂点を選択して出力する.
(2)この頂点とすべてをネットから削除
アウトエッジ
.
ループ終了後、出力する頂点数がネット上の頂点数より小さい場合は、「
ループ
出力された頂点シーケンスはトポロジーシーケンスです
.