图的操作算法(4)

*/

void BFSTraverse(ALGraph ag,int start) { LinkNode* Queue = (LinkNode*)malloc(sizeof(LinkNode)); //链表头结点，用做队列 LinkNode* pQueue = (LinkNode*)malloc(sizeof(LinkNode)); //对队列操作的指针 LinkNode* temp; //临时存储 LinkNode* last; //指向最后一个元素的指针 ArcNode* p; int i; if(!Queue || !pQueue) return; printf(\输出广度优先遍历次序:\ printf(\ p = ag.vertices[start].firstarc; Visited[start] = 1; while(1) //正常情况下执行一次循环 { //EnQueue pQueue->parc = p; Queue->next = pQueue; pQueue->next = NULL; last = pQueue; //指向最后一个元素的指针 //EnQueue over while(p && Queue->next) { while(p) { if(!Visited[p->adjvex]) { Visited[p->adjvex] = 1; printf(\//Visit Function //EnQueue pQueue = (LinkNode*)malloc(sizeof(LinkNode)); if(!pQueue) return; pQueue->parc = p; pQueue->next = NULL; last->next = pQueue; last = last->next; //指向最后一个元素的指针 //EnQueue over } p = p->nextarc; } //DeQueue

temp = Queue->next; p = ag.vertices[temp->parc->adjvex].firstarc; Queue ->next = temp->next; //DeQueue over } for(i=0; i

int main() { ALGraph ag; int i,n,m; int choose; //选择遍历结点 int start,end; //边的起点与终点的位置 printf(\说明: 采用邻接表的存储结构，生成无向图\\n 输入数据请回车确认\\n\\n\ while(1) //结点个数有效性验证 { printf(\请输入图的结点个数,并回车: \ scanf(\ if(n0) break; else printf(\请注意结点个数不能大于20,并且不能为0!\\n\ } ag.vexnum = n; printf(\初始化图的结点，输入字符并回车:\\n\ for(i=0; i

printf(\请输入边的数量: \ fflush(stdin); scanf(\ if(i<=m && i>=0) break; else printf(\请注意边的数量不能大于%d,并且不能小于1!\\n\}

ag.arcnum = i;

printf(\初始化图的边，结点从0开始计，最大为%d\\n\for(i=1; i<=ag.arcnum; i++) { while(1) //起点有效性验证 { printf(\第<%d>条边的起点: \ fflush(stdin); scanf(\ if(start=0) break; else printf(\重新输入 \ } while(1) //终点有效性验证 { printf(\第<%d>条边的终点: \ fflush(stdin); scanf(\ if(end=0 && end!=start) break; else printf(\重新输入 \ } printf(\ CreateGraph(&ag,start,end); }

printf(\开始进行图的遍历!\\n\while(1) //起始点有效性验证 { printf(\请输入深度优先遍历的开始结点:\ fflush(stdin); scanf(\ if(choose>=0 && choose

DFSTraverse(ag,choose); //深度优先遍历

i = 0; //重新初始化Visited数组 while(Visited[i]!='\\0') { Visited[i] = 0; i++; } while(1) //起始点有效性验证 { printf(\请输入广度优先遍历的开始结点:\ fflush(stdin); scanf(\ if(choose>=0 && choose

（4） 拓扑排序程序： #include #include #include #include #include using namespace std; #define MAX 9999 stackmystack; int indegree[MAX]; struct node { int adjvex; node* next; }adj[MAX];

int Create(node adj[],int n,int m)//邻接表建表函数，n代表定点数，m代表边数 { int i; node *p; for(i=0;i<=n-1;i++) { adj[i].adjvex=i; adj[i].next=NULL; } for(i=0;i<=m-1;i++) { cout<<\请输入第\条边:\

int u,v; cin>>u>>v; p=new node; p->adjvex=v; p->next=adj[u].next; adj[u].next=p; } return 1; }

void topsort(node adj[],int n) { int i; node *p;

memset(indegree,0,sizeof(indegree)); for(i=1;i<=n-1;i++) { p=adj[i].next; while(p!=NULL) { indegree[p->adjvex]++; p=p->next; } } for(i=1;i<=n-1;i++) { if(indegree[i]==0) mystack.push(i); } int count=0; while(mystack.size()!=0) { i=mystack.top(); mystack.pop(); cout<next) { int k=p->adjvex; indegree[k]--; if(indegree[k]==0) mystack.push(k); } } cout<

{ int n; int m; cout<<\请输入顶点数及边数:\ cin>>n>>m; Create(adj,n,m); cout<<\拓扑排序结果为:\ topsort(adj,n); system(\ return 0; }