有限期作業排序和判斷無向圖的關節點算法設計源代碼

　　//判斷無向圖的關節點

　　#include

　　#include

　　#define Vnum

　　typedef struct arcnode

　　{

　　int adjvex;

　　struct arcnode *nextarc;

　　}arcnode;

　　typedef struct vexnode

　　{

　　int vertex;

　　arcnode *firstarc;

　　}adjlist[Vnum];

　　typedef struct graphs

　　{

　　adjlist adjlist;

　　int vexnumarcnum;

　　}graph;

　　void create(graph *g)

　　{

　　int neijk;

　　arcnode *p;

　　cout<<創建一個圖:\t;

　　cout<<頂點數;

　　cin>>n;

　　cout<<\t\t邊數;

　　cin>>e;

　　g>vexnum=n;

　　g>arcnum=e;

　　for(i=;i

　　{

　　g->adjlist[i].vertex=i;

　　g->adjlist[i].firstarc=NULL;

　　}

　　for(k=0;k

　　{

　　cout<<"第"<

　　cin>>i>>j;

　　p=(arcnode *)malloc(sizeof(arcnode));

　　p->adjvex=j;

　　p->nextarc=g->adjlist[i].firstarc;

　　g->adjlist[i].firstarc=p;

　　}

　　}

　　void disp(graph *g)

　　{

　　int i,have;

　　arcnode *p;

　　cout<<"輸出圖："<

　　for(i=0;ivexnum;i++)

　　{

　　p=g->adjlist[i].firstarc;

　　have=0;

　　while(p!=NULL)

　　{

　　cout<<"("<adjvex<<")";

　　p=p->nextarc;

　　have=1;

　　}

　　if(have==1)

　　cout<

　　}

　　}

　　void dfs(graph g,int v,int visited[])

　　{

　　arcnode *p;

　　cout<

　　cin>>v;

　　cout<<"深度優先序列：";

　　dfs(g,v,visited);

　　cout<

　　}

　　//有限期的作業排序

　　#include

　　#include "iomanip.h"

　　void JOB_S(int n,int *D);

　　void main()

　　{

　　int *D,*P; //定義變量數組，采用動態分配內存

　　int i,n;

　　cout<<"請輸入要處理的作業數n:";

　　cin>>n;

　　D=new int[n+1]; //作業的截止期限數組

　　P=new int[n+1]; //作業的效益數組

　　cout<<"請輸入作業i的期限值D(1-"<

　　for(i=1;i<=n;i++) //按非增順序輸入

　　{

　　cout<<"作業"<

　　cin>>D[i];

　　}

　　cout<

　　cout<<"請輸入作業i的效益值P(1-"<

　　for(i=1;i<=n;i++) //按非增順序輸入

　　{

　　cout<<"作業"<

　　cin>>P[i];

　　}

　　cout<

　　JOB_S(n,D);

　　}

　　void JOB_S(int n,int *D)

　　{

　　int i,k,r;

　　int *J=new int[n+1];

　　k=1;

　　D[0]=0;

　　J[0]=0;

　　J[1]=1;

　　for(i=2;i<=n;i++)

　　{

　　r=k;

　　while(D[J[r]]>D[i] && D[J[r]]!=r)

　　r=r-1;

　　if(D[J[r]]<=D[i] && D[i]>r)

　　{

　　for(int x=k;x>=r+1;x--)

　　J[x+1]=J[x];

　　J[r+1]=i;

　　k++;

　　}

　　}

　　cout<<"該作業的最優處理順序為:";

　　for(i=1;i<=k;i++)

　　cout<

　　cout<

　　}

From:http://tw.wingwit.com/Article/program/sjjg/201311/23577.html