int min(int a,int b)
{
return a>b?b:a
}
int fun(int **a,int n,int begin,int end)
{
int m=~(1<<31),i
if(begin==end)
return 0
else
{
for(i=0i<ni++)
if(a[begin][i]!=-1&&a[begin][i]!=0)
m=min(fun(a,n,i,end),m)
return m
}
}
int main()
{
int n,i,js=0
char begin,end
int a[26][26],b[26]={0}
scanf("%d",&n)
for(i=0i<ni++)
for(j=0j<nj++)
{
scanf("%d,&a[i][j]")
if(i>j&&a[i][j]!=-1)
b[i]++
}
getchar()
scanf("%c %c",&begin,&end)
for(i=0i<ni++)
s=s+b[i]
printf("%d\n",s)
for(i=0i<ni++)
printf("%d\n",b[i])
fun(a,n,begin-'A',end-'A')
return 0
}
/*程序1:邻接表的dfs,bfs
其中n是点的个数,m是边的个数,你需要输入m条有向边,如果要无向只需要反过来多加一遍即可。
*/
#include <stdio.h>
#include <string.h>
#define MAXM 100000
#define MAXN 10000
int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail
void input_data()
{
scanf("%d%d",&n,&m)
int i,x,y
for (i=1i<=mi++)
{
int x,y
scanf("%d%d",&x,&y)
next[i]=first[x]
first[x]=i
en[i]=y
}
}
void pre()
{
memset(flag,0,sizeof(flag))
pd=0
}
void dfs(int x)
{
flag[x]=1
if (!pd)
{
pd=1
printf("%d",x)
}else
printf(" %d",x)
int p=first[x]
while (p!=0)
{
int y=en[p]
if (!flag[y]) dfs(y)
p=next[p]
}
}
void bfs(int k)
{
head=0tail=1
flag[k]=1dl[1]=k
while (head<tail)
{
int x=dl[++head]
if (!pd)
{
pd=1
printf("%d",x)
}else printf(" %d",x)
int p=first[x]
while (p!=0)
{
int y=en[p]
if (!flag[y])
{
flag[y]=1
dl[++tail]=y
}
p=next[p]
}
}
}
int main()
{
input_data()//读入图信息。
pre()//初始化
printf("图的深度优先遍历结果:")
int i
for (i=1i<=ni++)//对整张图进行dfs 加这个for主要是为了防止不多个子图的情况
if (!flag[i])
dfs(i)
printf("\n-------------------------------------------------------------\n")
pre()//初始化
printf("图的广度优先遍历结果为:")
for (i=1i<=ni++)
if (!flag[i])
bfs(i)
printf("\n----------------------end------------------------------------\n")
return 0
} /*
程序2:邻接矩阵
图的广度优先遍历和深度优先遍历
*/
#include <stdio.h>
#include <string.h>
#define MAXN 1000
int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN]
void input_data()
{
scanf("%d%d",&n,&m)
int i
for (i=1i<=mi++)
{
int x,y
scanf("%d%d",&x,&y)
w[x][0]++
w[x][w[x][0]]=y
}
}
void pre()
{
memset(flag,0,sizeof(flag))
pd=0
}
void dfs(int x)
{
flag[x]=1
if (!pd)
{
pd=1
printf("%d",x)
}else printf(" %d",x)
int i
for (i=1i<=w[x][0]i++)
{
int y=w[x][i]
if (!flag[y]) dfs(y)
}
}
void bfs(int t)
{
int head=0,tail=1
dl[1]=tflag[t]=1
while (head<tail)
{
int x=dl[++head]
if (!pd)
{
pd=1
printf("%d",x)
}else printf(" %d",x)
int i
for (i=1i<=w[x][0]i++)
{
int y=w[x][i]
if (!flag[y])
{
flag[y]=1
dl[++tail]=y
}
}
}
}
int main()
{
input_data()
printf("图的深度优先遍历结果:")
pre()
int i
for (i=1i<=ni++)
if (!flag[i])
dfs(i)
printf("\n---------------------------------------------------------------\n")
printf("图的广度优先遍历结果:")
pre()
for (i=1i<=ni++)
if (!flag[i])
bfs(i)
printf("\n-----------------------------end--------------------------------\n")
return 0
}
对每个结点所对应的那一列,中的所有1加起来,就是出度。(邻接矩阵中存的是0, 1)入度的计算也是类似的。
V : 结点集合。v_i (i = 0, n-1), n = |V|.
E : 边集合。表示为n*n的邻接矩阵。
E[i, j] = { if v_i ->v_j 存在有向边,1。else 0 }
求结点v_i的出度(伪码):
for (i = 0i <n-1i++) {
degree_sum = 0
for (j = 0j <n-1j++) {
if (E[i][j] == 1)
degree_sum++
}
}