回復 arou65271
都網路上面找的,
應該不難改
Adj. Matrix
- /* Program for creation of adjacency matrix */
- #include <stdlib.h>
- #include <stdio.h>
- #define max 20
- int adj[max][max]; /*Adjacency matrix */
- int n; /* Denotes number of nodes in the graph */
- void main()
- {
- int max_edges,i,j,origin,destin;
- char graph_type;
- p rintf("Enter number of nodes : ");
- scanf("%d",&n);
- p rintf("Enter type of graph, directed or undirected (d/u) : ");
- fflush(stdin);
- scanf("%c",&graph_type);
- if(graph_type=='u')
- max_edges=n*(n-1)/2;
- else
- max_edges=n*(n-1);
- for(i=1;i<=max_edges;i++)
- {
- p rintf("Enter edge %d( 0 0 to quit ) : ",i);
- scanf("%d %d",&origin,&destin);
- if( (origin==0) && (destin==0) )
- break;
- if( origin > n || destin > n || origin<=0 || destin<=0)
- {
- p rintf("Invalid edge!\n");
- i--;
- }
- else
- {
- adj[origin][destin]=1;
- if( graph_type=='u')
- adj[destin][origin]=1;
- }
- }/*End of for*/
- p rintf("The adjacency matrix is :\n");
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- p rintf("%4d",adj[i][j]);
- p rintf("\n");
- }
- }/*End of main()*/
複製代碼
BFS and DFS
- /*TO FIND THE BFS AND DFS OF THE GIVEN GRAPH*/
- #define size 20
- int a[10][10],vertex[10],n,e;
- /*STACK FUNCTIONS*/
- #define bottom -1
- int stack[size],top=bottom;
- int stackempty()
- {
- return(top=bottom) ? 1:0;
- }
- int stackfull()
- {
- return(top==size-1) ? 1:0;
- }
- void push(int item)
- {
- if(stackfull())
- p rintf("7
- STACK IS FULL");
- else
- stack[++top]=item;
- }
- int pop()
- {
- if(stackempty())
- {
- p rintf("7
- STACK IS EMPTY");
- return -1;
- }
- else
- return stack[top--];
- }
- int peep()
- {
- if(stackempty())
- {
- p rintf("7
- STACK IS EMPTY");
- return -1;
- }
- else
- return stack[top];
- }
- /* QUEUE FUNCTIONS */
- #define start -1
- int q[size];
- int f=start,r=start;
- int qempty(){ return(f==r)?1:0; }
- int qfull(){ return(r==size-1)?1:0;}
- void addq(int c)
- {
- if(qfull())
- p rintf("7
- QUEUE IS FULL");
- else
- q[++r]=c;
- }
- int delq()
- {
- if(qempty())
- {
- p rintf("7
- QUEUE IS EMPTY");
- return -1;
- }
- else
- return q[++f];
- }
- // j is unvisited adjecent vertex to i
- int adjvertex(int i)
- {
- int j;
- for(j=0;j
- if(a[i][j]==1&&vertex[j]==0)
- return j;
- return n;
- }
- int visitall()
- {
- int i;
- for(i=0;i
- if(vertex[i]==0)
- return 0;
- return 1;
- }
- /*FUNCTION FOR BFS*/
- void bfs()
- {
- int i,j,k,cur=0;//current vertex is startting vertex
- for(i=0;i
- vertex[i]=0;//not visited
- p rintf("
- BFS path => V%d ",cur+1);
- addq(cur);
- vertex[cur]=1;//marking visited vertex
- while(!visitall())
- {
- if(qempty())
- {
- p rintf("7
- GRAPH IS DISCONNECTED");
- break;
- }
- cur=delq();
- //visit all vertices which are adjecent to current vertex
- for(j=0;j
- {
- //adjecent are not visited
- if(a[cur][j]==1&&vertex[j]==0)
- {
- p rintf("V%d ",j+1);
- addq(j);
- //marking visited vertex
- vertex[j]=1;
- }
- }
- }
- }
- /*FUNCTION FOR DFS*/
- void dfs()
- {
- int i,j,k,cur=0;//current vertex is startting vertex
- for(i=0;i
- vertex[i]=0;//not visited
- p rintf("
- DFS path => V%d ",cur+1);
- push(cur);
- vertex[cur]=1;//marking visited vertex
- while(!visitall())
- {
- do
- {
- cur=adjvertex(peep());
- if(cur==n) pop();
- }
- while(cur==n&&!stackempty());
- if(stackempty())
- {
- p rintf("7
- GRAPH IS DISCONNECTED");
- break;
- }
- if(cur!=n)
- {
- p rintf(" V%d ",cur+1);
- push(cur);
- vertex[cur]=1;//marking visited vertex
- }
- }
- }
- /*MAIN PROGRAM*/
- void main()
- {
- int i,j,k;
- clrscr();
- for(i=0;i<10;i++)
- for(j=0;j<10;j++)
- a[i][j]=0;
- p rintf("
- ENTER NO OF VERTICES & EDGES OF UNDIRECTED GRAPH : ");
- scanf("%d%d",&n,&e);
- p rintf("
- ENTER EDGES AS PAIR OF VERTICES
- ");
- for(k=1;k<=e;k++)
- {
- p rintf("EDGE %d =>",k);
- scanf("%d%d",&i,&j);
- //for undirected graph
- a[i-1][j-1]=1;
- }
- dfs();
- bfs();
- getch();
- }
複製代碼 ... |