在C语言编程中,图的创建和遍历:
#include<stdio.h>
#define N 20
#define TRUE 1
#define FALSE 0
int visited[N]
typedef struct /*队列的定义*/
{
int data[N]
int front,rear
}queue
typedef struct /*图的邻接矩阵*/
{
int vexnum,arcnum
char vexs[N]
int arcs[N][N]
}
graph
void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/
void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/
void tdfs(graph *g) /*深度优先搜索整个图*/
void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/
void tbfs(graph *g) /*广度优先搜索整个图*/
void init_visit() /*初始化访问标识数组*/
void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/
{ int i,j
char v
g->vexnum=0
g->arcnum=0
i=0
printf("输入顶点序列(以#结束):
")
while((v=getchar())!='#')
{
g->vexs[i]=v /*读入顶点信息*/
i++
}
g->vexnum=i /*顶点数目*/
for(i=0i<g->vexnumi++) /*邻接矩阵初始化*/
for(j=0j<g->vexnumj++)
g->arcs[i][j]=0
printf("输入边的信息:
")
scanf("%d,%d",&i,&j) /*读入边i,j*/
while(i!=-1) /*读入i,j为-1时结束*/
{
g->arcs[i][j]=1
g->arcs[j][i]=1
scanf("%d,%d",&i,&j)
}
}
void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/
{
int j
printf("%c",g->vexs[i])
visited[i]=TRUE
for(j=0j<g->vexnumj++)
if((g->arcs[i][j]==1)&&(!visited[j]))
dfs(j,g)
}
void tdfs(graph *g) /*深度优先搜索整个图*/
{
int i
printf("
从顶点%C开始深度优先搜索序列:",g->vexs[0])
for(i=0i<g->vexnumi++)
if(visited[i]!=TRUE)
dfs(i,g)
}
void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/
{
int i,j
queue qlist,*q
q=&qlist
q->rear=0
q->front=0
printf("%c",g->vexs[k])
visited[k]=TRUE
q->data[q->rear]=k
q->rear=(q->rear+1)%N
while(q->rear!=q->front)
{
i=q->data[q->front]
q->front=(q->front+1)%N
for(j=0j<g->vexnumj++)
if((g->arcs[i][j]==1)&&(!visited[j]))
{
printf("%c",g->vexs[j])
visited[j]=TRUE
q->data[q->rear]=j
q->rear=(q->rear+1)%N
}
}
}
void tbfs(graph *g) /*广度优先搜索整个图*/
{
int i
printf("
从顶点%C开始广度优先搜索序列:",g->vexs[0])
for(i=0i<g->vexnumi++)
if(visited[i]!=TRUE)
bfs(i,g)
printf("
")
}
void init_visit() /*初始化访问标识数组*/
{
int i
for(i=0i<Ni++)
visited[i]=FALSE
}
int main()
{
graph ga
int i,j
createGraph(&ga)
printf("无向图的邻接矩阵:
")
for(i=0i<ga.vexnumi++)
{
for(j=0j<ga.vexnumj++)
printf("%3d",ga.arcs[i][j])
printf("
")
}
init_visit()
tdfs(&ga)
init_visit()
tbfs(&ga)
return 0
}
C语言编程,顾名思义,就是用C语言来进行计算机编程工作。
C语言是国际上广泛流行的,很有发展前途的计算机高级语言.它适合作为系统描述语言,即可用来编写系统软件,也可用来编写应用软件.
C语言是一种引用广泛,并且实现灵活的一种计算机编程语言,用C语言编出来的程序,可以在很多平台上运行,可移植性强。具体的C语言编程内容请参加C或者C++等。
算法这里有,程序你应该自己写!http://courseware.ecnudec.com/zsb/zsx/zsx07/zsx079/zsx079000.htm
伪代码的程序,以及源程序,网上也能找到。
你自己只需要额外写一些输入各节点
以及计算每两个点之间的距离的代码了
不难的啊
#include <stdio.h>
#define INFINITY 32767
#define MAXN 4
typedef struct
{
int vnum
int arcs[MAXN][MAXN]
}graph
void creat_graph(graph *p)
{
int i,j,n
int v1,v2,w
printf("vertex number of the graph:")
scanf("%d",&n)
//if(n<1) return 0
p->vnum=n
for(i=0i<n++i)
for(j=0j<n++j)
if(i==j)
p->arcs[i][j]=0
else
p->arcs[i][j]=INFINITY
do
{
printf("edge(vertex1,vertex2,weight):")
scanf("%d,%d,%d",&v1,&v2,&w)
if(v1>=0&&v1<n&&v2>=0&&v2<n)
{
p->arcs[v1][v2]=w
p->arcs[v2][v1]=w
}
}while(!(v1==-1&&v2==-1))
}
int prim(graph G,int v, int tree[][3])
{
int i,j,k,p,min,c
int lowcost[MAXN],closest[MAXN]
for(i=0i<G.vnum++i)
{
closest[i]=v
lowcost[i]=G.arcs[v][i]
}
c=0
p=0
for(i=0i<G.vnum-1++i)
{
min=INFINITY
for(j=0j<G.vnum++j)
if(lowcost[j]!=0&&lowcost[j]<min)
{
min=lowcost[j]
k=j
}
tree[p][0]=closest[k]
tree[p][1]=k
tree[p][2]=min
p++
c+=min
lowcost[k]=0
for(j=0j<G.vnum++j)
if(G.arcs[k][j]!=0&&G.arcs[k][j]<lowcost[j])
{
lowcost[j]=G.arcs[k][j]
closest[j]=k
}
}
return c
}
void main()
{
int i
int tree[MAXN][3]
int cost
graph G
// double dist[MAXN]
creat_graph(&G)
cost=prim(G,1,tree)
printf("Minimum-cost spanning tree(prim):\n")
printf("edge\t weight\t\n")
for(i=0i<G.vnum-1++i)
printf("v%d-v%d\t%d\n",tree[i][0],tree[i][1],tree[i][2])
printf("Cost : %d\n",cost)
}
上面的源码引用于:http://bosswang2886.bokee.com/viewdiary.12193998.html