图的操作算法(3)

int i,j,k,weight,m,n; int ch1,ch2; char a,b;

printf(\输入图的顶点数和边数（中间由空格隔开）\ scanf(\ //输入顶点数,边数 for(i=0;in;i++) { getchar(); printf(\请输入第%d个顶点:\ scanf(\ //输入¨顶点 } for(i=0;in;i++) for(j=0;jn;j++) G->edgs[i][j]=0;

printf(\输入边的权重：格式如 i（边的起始顶点）格隔开】\\n\ for(k=0;ke;k++) {

printf(\请输入第%d条边的顶点权值):\ getchar(); scanf(\ m=0; n=0; for( m=0;G->vexs[m]!=a;m++); for( n=0;G->vexs[n]!=b;n++); ch1=m;ch2=n; G->edgs[ch1][ch2]=weight; G->edgs[ch2][ch1]=weight; } }

void prim(MGraph *G, int v) { int i,j,k,min; struct { int adjvex; int lowcost; } closedge[10]; for (i=0;in;i++) { closedge[i].lowcost=G->edgs[v][i]; closedge[i].adjvex=v; } closedge[v].lowcost=TURE; for (i=1;in;i++) { min=100;

j（边的终点） w（边的权重）\\n【中间由空 for(j=0;jn;j++) if (closedge[j].lowcost!=TURE && closedge[j].lowcost!=0) { if (closedge[j].lowcostn;j++) if (closedge[j].lowcost!=TURE) if(G->edgs[k][j]edgs[k][j]; closedge[j].adjvex=k; } } }

int main(void) { MGraph *G,a; char ch1; G=&a; printf(\建立图的邻接矩阵\\n\ GreateMGraph(G); getchar(); ch1=1;

printf(\

printf(\最小生成树 \

printf(\算法输出为a：\ prim(G,0);

system(\ }

（3）

存储链表和深度优先搜索、广度优先搜索的程序： /*

*采用邻接表的存储结构 *构建无向图 */

#include #include #include

#define MAX_VERTEX_NUM 20

typedef struct ArcNode{ int adjvex; struct ArcNode* nextarc; //InfoType* info; }ArcNode;

/********************************* *链表结点的结构用于创建栈或是队列 ********************************/ typedef struct LinkNode{ ArcNode* parc; //存储指针地址 struct LinkNode* next; //指向一下个结点 }LinkNode;

typedef struct VNode{ char cData; //顶点元素值 ArcNode* firstarc; //指向第一条依附于该点的边 }VNode,AdjList[MAX_VERTEX_NUM];

typedef struct { AdjList vertices; int vexnum; //图的当前顶点数和弧数 int arcnum; }ALGraph;

int Visited[MAX_VERTEX_NUM]; /************************** *采用前插法创建邻接表

*************************/

int CreateGraph(ALGraph* pag,int start,int end) { ArcNode* arcNodes = (ArcNode*)malloc(sizeof(ArcNode)); ArcNode* arcNodee = (ArcNode*)malloc(sizeof(ArcNode)); ArcNode* p; if(!arcNodes || !arcNodee) return 0; //从start->end生成关系 arcNodes->adjvex = end; //下一结点的位置 p = pag->vertices[start].firstarc; if(!p) //第一个结点单独构造 { arcNodes->nextarc = pag->vertices[start].firstarc; pag->vertices[start].firstarc = arcNodes; } else{

while(p->nextarc) p = p->nextarc; p->nextarc = arcNodes; arcNodes->nextarc = NULL; } //end->start 的关系生成 arcNodee->adjvex = start; //下一结点的位置 p = pag->vertices[end].firstarc; if(!p) //第一个结点单独构造 { arcNodee->nextarc = pag->vertices[end].firstarc; pag->vertices[end].firstarc = arcNodee; } else{ while(p->nextarc) p = p->nextarc; p->nextarc = arcNodee; arcNodee->nextarc = NULL; } return 1; } /*

*深度优先遍历,非递归方式 */

void DFSTraverse(ALGraph ag,int start) { LinkNode* Stack = (LinkNode*)malloc(sizeof(LinkNode)); //链表头结点，用做栈 LinkNode* pStack = (LinkNode*)malloc(sizeof(LinkNode)); //对栈操作的指针 LinkNode* temp; //临时存储 ArcNode* p; int i; if(!pStack||!Stack) return; Stack->next = NULL; p = ag.vertices[start].firstarc; Visited[start]=1; //Flag printf(\输出深度优先遍历顺序:\ printf(\ //访问第一个点 while(1) //正常情况下执行一次，为了打印孤立结点 { //push stack pStack->parc = p; pStack->next = Stack->next; //将p接入链式栈中 Stack->next = pStack;

//push over while(p && (Stack->next)) //当并且栈不为空时 { while(p) { if(Visited[p->adjvex]) p = p->nextarc; else { Visited[p->adjvex]=1; printf(\//Visit Function //push stack pStack = (LinkNode*)malloc(sizeof(LinkNode)); if(!pStack) return; //结点建立不成功 pStack->parc = p; pStack->next = Stack->next; Stack->next = pStack; //push over p = ag.vertices[p->adjvex].firstarc; } } //pop stack temp = Stack->next; Stack->next = temp->next; p = temp->parc->nextarc; free(temp); //pop over } for(i=0; i

*广度优先遍历,非递归方式